稀疏优化与低秩矩阵优化课件

1、修乃华北京交通大学理学院2014 年 3 月 6 日稀疏优化与低秩矩阵优化 内容提要模型与基本概念稀疏优化与压缩感知应用实例理论与算法分析与思考 一、模型与基本概念稀疏优化问题是指在某种线性约束条件下，求一个决策变量使其非零元素个数达到极小.它的基本数学模型是：其中 ，b 是一个 m 维向量,m=0； 有时|x|_0=0； 有时rank（X）=r, 半正定.我们的研究重点：1、非负稀疏优化理论与算法；2、低秩半定矩阵优化理论与算法。五、工作、分析与思考基本理论（交大团队）：（1）建立了在若当代数意义下的压缩感知松弛理论，即RIP性质、NSP性质、S-goodness 1；（2）对于1/2松弛(

2、3/4）2，目前最好的RIP界为 （3）证明广义Z-矩阵、Lyapunov变换、欧氏距离阵三类线性变换下非负稀疏优化或低秩半定矩阵秩优化是多项式可解的3,4；（4）对于某些非负稀疏或者低秩半定矩阵优化，采样量可降低至与稀疏度或者秩同阶3,4.【1】 L.C. Kong, J. Sun, J.Y. Tao, N.H. Xiu, Sparse Recovery on Euclidean Jordan Algebras, Submitted, 2013.【2】S.L. Zhou, L.C. Kong, Z.Y. Luo, N.H. Xiu, New RIC Bounds via Lq-minimiz

3、ation with 0 q= 1 in Compressed Sensing, 2013.【3】Z.Y. Luo, L.Y. Qin, L.C. Kong, N.H. Xiu, The Nonnegative Zero Norm Minimization under Generalized Z-matrix Measurement, JOTA, 2013.【4】 Z.Y. Luo, N.H. Xiu, On Minimal Rank Solutions to Symmetric Lyapunov Equations, Optimization, 2013.五、工作、分析与思考非凸低阶正则方法

4、（交大团队）：（1）对于低秩半定矩阵恢复问题，提出一类 正则不动点迭代方法，并应用在图像处理5、6;（2）对于非负稀疏优化问题，提出一类光滑投影算法，并应用在成像技术7。【5】D.T. Peng, N.H. Xiu, J. Yu, 1/2 Regularization and Fixed Point Algorithm for Low-Rank Matrix Recovery, Submitted, 2013.【6】Y.Q. Chen, N.H. Xiu and D.T. Peng, “Global solution of non-Lipschitz S2-Sp minimization ov

5、er the positive semidefinite cones”,to appear in Optimization Letters, 2013.【7】X. Chen, M.K. Ng, C. Zhang, Non-Lipschitz Lp-regularization and box constrained model for image restoration, IEEE Transactions on Image Processing, 2013.五、工作、分析与思考思考：对于非负稀疏优化问题，提出一类L1-Lp不动点算法，进而低秩半定矩阵优化。推广到“损失函数+罚函数”（如人脸识别）不动点算法，并进行理论分析（如收敛性，解的渐近分布性、变量选择一致性）。稀疏（目标、约束）非线性优化理论与算法研究，如最优性条件、可行方向法、投影方法、见Beck的新文章。低秩（目标、约束）半定