稀疏优化 算法部分 课程提纲与参考文献

2010年优化与应用国际暑期学校
中国科学院科学与工程计算国家重点实验室

算法相关的这部分课程中,我们将侧重讨论压缩感知中的一些优化算法及其在矩阵复原和稀疏逆协方差估计等中的应用。当然我们的目的并不局限于压缩感知,实际上这些算法框架很多是通用的,可以用来解决其它很多问题。

第一课: (slides)
前半部分介绍稀疏优化中一些典型问题,后半部分讨论 spectral projected gradient (SPG) method 及它在算法GPSRSPGL1 中的应用。

参考文献:
1. (非单调线搜索 ) Hongchao Zhang and William  Hager, A nonmonotone line search technique and its application to unconstrained optimization
2. (保证收敛性的BB 算法) Marcos Raydan, The Barzilar and Borwein gradient method for the large scale unconstrained minimization problem
3.  Ernesto G. Birgin, Jose Martinez,  Marcos Raydan, Nonmonotone projected gradient methods on convex sets
4. Mario A. T. Figueiredo, Robert D. Nowak, Stephen J. Wright, Gradient Projection for Sparse Reconstruction: Application to Compressed Sensing and Other Inverse Problems
5. Ewout Van Den Berg, Michael Friedlander, Probing the pareto frontier for basis pursuit solutions

第二课: (slides)
讨论一个运算很简单的算子”Shrinkage”和两个算法FPCFPC_AS

参考文献:
1. Elaine Hale, Wotao Yin, Yin Zhang, Fixed-point continuation for l1-minimzation: methodology and convergence
2. Zaiwen Wen, Wotao Yin, Donald Goldfarb, Yin Zhang,  A fast algorithm for sparse reconstruction based on shrinkage, subspace optimization and continuation

第三课: (slides)
讨论交替方向法(Alternating direction method, ADM),算子分解法,以及交替方向法的一些收敛性证明

参考文献:
1. Wotao Yin, Stanley Osher, Donald Goldfarb,  Jerome Darbon, Bregman Iterative Algorithms for l1-Minimization with Applications to Compressed Sensing
2. Junfeng Yang, Yin Zhang, Alternating direction algorithms for l1-problems in Compressed Sensing
3. Tom Goldstein, Stanely Osher, The Split Bregman Method for L1-Regularized Problems
4. B.S. He, H. Yang, S.L. Wang, Alternating Direction Method with Self-Adaptive Penalty Parameters for Monotone Variational Inequalities

第四课: (slides1) (slides2)
前半部分继续讨论交替方向法以及Proximal point算法,后半部分介绍Nesterov的针对无约束问题的一阶最优算法。

参考文献:
1. Xiaoqun Zhang, Martin Burgerz, Stanley Osher,  A unified primal-dual algorithm framework based on Bregman iteration
2. Yurii Nesterov, Introductory lectures on convex optimization, a basic course

第五课: (slides)
讨论基于shrinkage算法的复杂度,怎么运用Nesterov最优算法对shrinkage进行加速和解Basis Pursuit问题

参考文献:
1. Amir Beck and Marc Teboulle,  A fast iterative shrinkage-thresholding algorithm for linear inverse problems
2. Paul Tseng, On accelerated proximal gradient methods for convex-concave optimization
3. Paul Tseng,  Approximation accuracy, gradient methods and error bound for structured convex optimization
4. N. S. Aybat and G. Iyengar,  A first-order augmented Lagrangian method for compressed sensing

第六课: (slides)
前半部分讨论矩阵复原,后半部分讨论稀疏逆协方差估计

参考文献:
1. Jianfeng Cai, Emmanuel Candes, Zuowei Shen,  Singular value thresholding algorithm for matrix completion
2. Shiqian Ma, Donald Goldfarb, Lifeng Chen, Fixed point and Bregman iterative methods for matrix rank minimization
3. Zaiwen Wen, Wotao Yin, Yin Zhang,  Solving a low-rank factorization model for matrix completion by a nonlinear successive over-relaxation algorithm
4. Onureena Banerjee, Laurent El Ghaoui, Alexandre d’Aspremont, Model Selection Through Sparse Maximum Likelihood Estimation for Multivariate Gaussian or Binary Data
5. Zhaosong Lu, Smooth optimization approach for sparse covariance selection

(相关文献还有很多,我们这里只列出课程里重点讨论的文献)

Advertisements
This entry was posted in 稀疏优化---2010年优化与应用国际暑期学校. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s