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

修乃华北京交通大学理学院2014年3月6日稀疏优化与低秩矩阵优化内容提要模型与基本概念稀疏优化与压缩感知应用实例理论与算法分析与思考一、模型与基本概念稀疏优化问题是指在某种线性约束条件下，求一个决策变量使其非零元素个数达到极小.它的基本数学模型是：其中，b是一个m维向量,m<n.矩阵秩极小（或低秩矩阵恢复）问题是指在某种线性约束条件下，求一个决策矩阵使其秩达到极小.它的基本数学模型是：其中

是从到的线性变换，b是一个d维向量.一、模型与基本概念【注】1、模型（2）是模型（1）的一个推广；2、可以把零范数和秩函数放在约束中，变成

非凸约束优化模型；3、如果问题是高维复杂的，则可在模型中增加其他约束条件或者目标函数,如非负稀疏优化、低秩半定矩阵矩阵优化.一、模型与基本概念在一般情况下，模型（1）是一个NP-困难的组合优化问题,因为（1）等价于在如下有限个特殊集合与集合中选一个解.由此可知，所有这些模型在一般情况下都是NP-困难问题.◆如何松弛（近似）易求解？→理论研究；◆如何设计算法？→算法研究；◆如何应用到实际部门？→应用研究.

二、稀疏优化与压缩感知压缩感知是国际上近期出现的一种信息科学理论，它首先由著名华裔数学家、2006年菲尔兹奖得主陶哲轩

&Candes、美国国家科学院院士Donoho独立提出,被评为2007年度美国十大科技进展之一,其基本内容是：如果原始信号具有稀疏性的特征，那么通过少量的观测信息就能够恢复原始信号.这个理论突破了香农定理对信号采样频率的限制，能够以较少的采样资源，较高的采样速度和较低的软硬件复杂度获得原始信号.

二、稀疏优化与压缩感知文献计量分析：至2011年10月，压缩感知共涉及29个学科领域,主要应用于工程技术(50.917%)、计算机科学(21.865%)、数学应用(16.667%)、放射核医学成像(13.761%)、物理(10.398%)、光学设计(9.021%)、成像科学摄影技术(4.587%)、电信技术(4.128%)、地球化学物理学(3.823%)、生物分子学(2.446%)等领域。

三、应用实例例1、带选择限制的投资组合优化问题

我们知道，诺贝尔经济学奖获得者Markowitz于1952年提出投资组合选择理论，开创了金融风险理论的先河.它的数学模型是一个线性约束的二次优化问题，如果投资者发现证券种类太多，想把他的这笔资金投资在限定的几种证券之中，那么就在原来的基础上增加约束条件.从而得到稀疏优化模型：三、应用实例例2、互补问题的稀疏解

众说周知，二人矩阵博弈模型、具有生产和投资的经济均衡模型、交通流均衡模型等，都可以转化为互补问题.如果这个互补问题有多个解，则在这个解集中寻找一个最为稀疏的解：三、应用实例例3(上)、低秩协方差矩阵估计

协方差矩阵估计就是从采样数据矩阵中估计出真实的低秩协方差矩阵.它是多元统计分析中最为基本的内容之一，大量的统计学方法包括聚类分析、主成分分析、线性和二次判别分析、回归分析都需要它.随着大数据时代的到来，要求从海量高维数据中分析出深刻的量化指标和预测，协方差矩阵估计被应用在越来越多的学科领域和生产实际中，如气象预报、基因表达、功能MR成像、风险管理和套利优化、社交网络.三、应用实例例3(下)、低秩协方差矩阵估计

给定对称矩阵

，用

表示半正定性.从最优化的角度分析，如果低秩性视为一个目标，那么低秩协方差矩阵估计问题可以描述为，已知对称矩阵

，求解如下的多目标优化：

（5）

这是一个矩阵秩极小问题.三、应用实例例4(上)、NetflixPrize

2006年10月Netflix电影公司为了有效发展自己的推荐系统而发起的长达5年的竞赛，要求参赛者根据48万余用户对1万7千部电影的不完全评分记录推测出另外近300万条电影评分记录的数值.任何组织或个人只要能提交比Netflix现有电影推荐系统Cinematch效果好10%的新方法，就可以获得诱人的7位数奖金.不仅如此，每年它还会为此提供5万美元的年度进步奖.三、应用实例例4(下)、NetflixPrize

如果我们把用户的评分数据看作一个矩阵，矩阵的行表示1万7千部电影，矩阵的列表示不同的用户，上述NetflixPrize问题用数学语言描述就是，已知矩阵的某些元素来求这个完整矩阵.最终,2009年9月，科研团队BellKor’sPragmaticChaos获得此奖，所建立的数学模型就是矩阵极小问题：

（6）三、应用实例例5、多维标度问题（管理学、统计学）已知12个城市中两两城市之间的距离，请你标出这12个城市的平面坐标位置.类似地，已知一个传感器网络，通过互相收发信号可以确定传感器之间的距离，请确定传感器的平面坐标位置.此外，有100种白酒，品尝家可以对每两种白酒进行品尝对比，给出一种相近程度的得分（越相近得分越高，相差越远得分越低），我们希望从这些得分数据中得到这100种白酒之间的排序表,所建立的数学模型就是一个矩阵秩极小问题：

(7)

这里，是一个特定的线性算子.三、应用实例例6、Sparse-VisoCTCT是医学诊断的主要工具之一，其成像的数学原理是Ax=b,其中x是一个未知向量，表示人体待检查部位的图像，维数512*512代表像素个数，b是一个测量值，其维数为1160*672代表射线的条数（1160代表圆周划分的角度），A是（1160*672，512*512）阶矩阵，由物理规律得到.由于其行数大于列数，一般情况下该方程无解.更为可怕的是行数多意味着“吃线”多，对人的身体危害极大.期望：“吃线少、时间短、图像清晰”.现在，假设人体待检查部位的图像稀疏，那么应用稀疏优化理论和算法，可以进行研究。

四、理论与算法凸松弛理论和算法凸松弛就是把稀疏优化中的0-范数用1-范数代替，把矩阵秩极小问题的秩函数用核范数代替.从而模型（1）和（2）分别变成如下线性规划（1#）和半定规划(2#)，简单易求解.

四、理论与算法凸松弛理论和算法-理论模型（1）与（1#）是什么关系？凸松弛理论：RIP性质、NSP性质、RSP性质、S-good性质.●孔令臣研究了在若当代数意义下稀疏优化的几种性质.

四、理论与算法■凸松弛理论和算法-算法如何求解（1#）？凸松弛算法.◆文再文与印卧涛，Goldfarb和张寅：不动点积极集算法，（软件FPC_AS下载已经超过2000次）；◆马士谦与Goldfarb和Scheinberg：交替线性化方法的迭代复杂度分析（交替方向法的复杂度分析最早和最主要的成果之一）；◆何炳生、袁晓明和杨俊锋等：交替方向增广拉格朗日函数法.

四、理论与算法非凸松弛理论和算法非凸松弛模型：即用p-范数代替0-范数.即如下优化模型：非凸松弛理论：

◆我国黄正海、孔令臣在这个方面有好的工作；

◆周声龙得到与1-范数松弛一样好的RIP界.

四、理论与算法非凸松弛理论和算法非凸松弛算法：◆陈小君、徐凤敏和叶荫宇：非光滑非凸非Lipschitz优化（建立了其局部最小值点的一阶、二阶必要和充分条件，给出了可度量的稳定点定义）；◆徐宗本等：1/2正则理论和方法（在图像处理领域取得了很好的效果）；◆陈小君、牛凌峰和袁亚湘：光滑信赖域算法（收敛于非Lipschitz优化二阶稳定点）；◆边伟、陈小君和叶荫宇：二阶算法（收敛于非Lipschitz优化二阶稳定点，给出了其最坏复杂性分析）.

四、理论与算法■凸差松弛理论和算法凸差松弛就是用(1范数-q范数)代替0-范数，从图像可以看出，它更接近稀疏优化问题，能更好得区分无关项和相关项，从而有助于得到较精确的逼近.■光滑松弛理论和算法光滑松弛就是用一个光滑函数代替0-范数或者秩函数，从而得到光滑优化.■加权1-范数松弛理论和算法加权1-范数松弛就是用加权1-范数代替0-范数，从而得到一个凸优化.实践表明很好，但是理论结果欠缺（待研究）。五、工作、分析与思考

理念：1、一幅待处理的图像，如果用其向量x表示，则可以认为

必须x>=0；

有时||x||_0<=s.2、一幅待处理的图像，如果用其矩阵X表示，则可以认为必须X>=0；

有时rank（X）<=r,半正定.我们的研究重点：1、非负稀疏优化理论与算法；2、低秩半定矩阵优化理论与算法。五、工作、分析与思考基本理论（交大团队）：（1）建立了在若当代数意义下的压缩感知松弛理论，即RIP性质、NSP性质、S-goodness[1]；（2）对于1/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,SparseRecoveryonEuclideanJordanAlgebras,Submitted,2013.【2】S.L.Zhou,L.C.Kong,Z.Y.Luo,N.H.Xiu,NewRICBoundsviaLq-minimizationwith0<q<=1inCompressedSensing,2013.【3】Z.Y.Luo,L.Y.Qin,L.C.Kong,N.H.Xiu,TheNonnegativeZeroNormMinimizationunderGeneralizedZ-matrixMeasurement,JOTA,2013.【4】Z.Y.Luo,N.H.Xiu,

OnMinimalRankSolutionstoSymmetricLyapunovEquations,Optimization,2013.五、工作、分析与思考非凸低阶正则方法（交大团队）：（1）对于低秩半定矩阵恢复问题，提出一类

正则不动点迭代方法，并应用在图像处理[5、6];（2）对于非负稀疏优化问题，提出一类光滑投影算法，并应用在成像技术[7]。【5】D.T.Peng,N.H.Xiu,J.Yu,1/2RegularizationandFixedPointAlgorithmforLow-RankMatrixRecovery,

Submitted,2013.【6】Y.Q.Chen,N.H.XiuandD.T.Peng,“Globalsolutionofnon-LipschitzS2-Spminimizationoverthepositivesemidefinitecones”,toappearinOptimizationLetters,2013.【7】X.Chen,M.K.Ng,C.Zhang,Non-LipschitzLp-regularizationandboxconstrainedmodelforimagerestoration,IEEETransactio