修乃華2014年3月6日稀疏優化與低秩矩陣優化內容提要模型與基本概念稀疏優化與壓縮感知應用實例理論與算法分析與思考一、模型與基本概念稀疏優化問題是指在某種線性約束條件下，求一個決策變量使其非零元素個數達到極小.它的基本數學模型是：其中，b是一個m維向量,m<n.矩陣秩極小（或低秩矩陣恢復）問題是指在某種線性約束條件下，求一個決策矩陣使其秩達到極小.它的基本數學模型是：其中

是從到的線性變換，b是一個d維向量.一、模型與基本概念在一般情況下，模型（1）是一個NP-困難的組合優化問題,因為（1）等價于在如下有限個特殊集合與集合中選一個解.由此可知，所有這些模型在一般情況下都是NP-困難問題.◆如何松弛（近似）易求解？→理論研究；◆如何設計算法？→算法研究；◆如何應用到實際部門？→應用研究.

二、稀疏優化與壓縮感知壓縮感知是國際上近期出現的一種信息科學理論，它首先由著名華裔數學家、2006年菲爾茲獎得主陶哲軒

&Candes、美國國家科學院院士Donoho獨立提出,被評為2007年度美國十大科技進展之一,其基本內容是：如果原始信號具有稀疏性的特征，那么通過少量的觀測信息就能夠恢復原始信號.這個理論突破了香農定理對信號采樣頻率的限制，能夠以較少的采樣資源，較高的采樣速度和較低的軟硬件復雜度獲得原始信號.

二、稀疏優化與壓縮感知假設原始信號為向量（維數大），測量信息為向量（維數小），且它們滿足線性關系，則其數學模型就是一個欠定線性方程組.如果原始信號

具有稀疏性，則其數學意義就是零元素多，即非零元素少,于是可以轉化為稀疏優化模型：

二、稀疏優化與壓縮感知假設原始信號為矩陣X（維數大），測量信息為矩陣B（維數小），且它們滿足線性關系，則其數學模型就是一個線性矩陣方程組A(X)=B.如果原始信號矩陣X具有低秩性，則其數學意義就是期望矩陣X的秩rank(X)極小.于是可以轉化為矩陣秩極小問題：如果原始信號海量高維，呈現出復雜性、限制性等，則可以根據其各種特性建立更為細致的優化模型.三、應用實例例1、帶選擇限制的投資組合優化問題

我們知道，諾貝爾經濟學獎獲得者Markowitz于1952年提出投資組合選擇理論，開創了金融風險理論的先河.它的數學模型是一個線性約束的二次優化問題，如果投資者發現證券種類太多，想把他的這筆資金投資在限定的幾種證券之中，那么就在原來的基礎上增加約束條件.從而得到稀疏優化模型：三、應用實例例3(上)、低秩協方差矩陣估計

協方差矩陣估計就是從采樣數據矩陣中估計出真實的低秩協方差矩陣.它是多元統計分析中最為基本的內容之一，大量的統計學方法包括聚類分析、主成分分析、線性和二次判別分析、回歸分析都需要它.隨著大數據時代的到來，要求從海量高維數據中分析出深刻的量化指標和預測，協方差矩陣估計被應用在越來越多的學科領域和生產實際中，如氣象預報、基因表達、功能MR成像、風險管理和套利優化、社交網絡.三、應用實例例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#）？凸松弛算法.◆文再文與印臥濤，Goldfarb和張寅：不動點積極集算法，（軟件FPC_AS下載已經超過2000次）；◆馬士謙與Goldfarb和Scheinberg：交替線性化方法的迭代復雜度分析（交替方向法的復雜度分析最早和最主要的成果之一）；◆何炳生、袁曉明和楊俊鋒等：交替方向增廣拉格朗日函數法.

四、理論與算法非凸松弛理論和算法非凸松弛模型：即用p-范數代替0-范數.即如下優化模型：非凸松弛理論：

◆我國黃正海、孔令臣在這個方面有好的工作；

◆周聲龍得到與1-范數松弛一樣好的RIP界.

四、理論與算法■凸差松弛理論和算法凸差松弛就是用(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）對于低秩半定矩陣恢復問題，提出一類

正則不動點迭代方法，并應用在圖像處理[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,IEEETransactionsonImageProcessing,2013.五、工作、分析與思考思考：對于非負稀疏優化問題，提出一類L1-Lp不動點算法，