稀疏優(yōu)化與低秩矩陣優(yōu)化課件

修乃華2014年3月6日稀疏優(yōu)化與低秩矩陣優(yōu)化內(nèi)容提要模型與基本概念稀疏優(yōu)化與壓縮感知應(yīng)用實(shí)例理論與算法分析與思考一、模型與基本概念稀疏優(yōu)化問題是指在某種線性約束條件下，求一個(gè)決策變量使其非零元素個(gè)數(shù)達(dá)到極小.它的基本數(shù)學(xué)模型是：其中，b是一個(gè)m維向量,m<n.矩陣秩極?。ɑ虻椭染仃嚮謴?fù)）問題是指在某種線性約束條件下，求一個(gè)決策矩陣使其秩達(dá)到極小.它的基本數(shù)學(xué)模型是：其中

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

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

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

二、稀疏優(yōu)化與壓縮感知假設(shè)原始信號為向量（維數(shù)大），測量信息為向量（維數(shù)?。?，且它們滿足線性關(guān)系，則其數(shù)學(xué)模型就是一個(gè)欠定線性方程組.如果原始信號

具有稀疏性，則其數(shù)學(xué)意義就是零元素多，即非零元素少,于是可以轉(zhuǎn)化為稀疏優(yōu)化模型：

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

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

協(xié)方差矩陣估計(jì)就是從采樣數(shù)據(jù)矩陣中估計(jì)出真實(shí)的低秩協(xié)方差矩陣.它是多元統(tǒng)計(jì)分析中最為基本的內(nèi)容之一，大量的統(tǒng)計(jì)學(xué)方法包括聚類分析、主成分分析、線性和二次判別分析、回歸分析都需要它.隨著大數(shù)據(jù)時(shí)代的到來，要求從海量高維數(shù)據(jù)中分析出深刻的量化指標(biāo)和預(yù)測，協(xié)方差矩陣估計(jì)被應(yīng)用在越來越多的學(xué)科領(lǐng)域和生產(chǎn)實(shí)際中，如氣象預(yù)報(bào)、基因表達(dá)、功能MR成像、風(fēng)險(xiǎn)管理和套利優(yōu)化、社交網(wǎng)絡(luò).三、應(yīng)用實(shí)例例4(上)、NetflixPrize

2006年10月Netflix電影公司為了有效發(fā)展自己的推薦系統(tǒng)而發(fā)起的長達(dá)5年的競賽，要求參賽者根據(jù)48萬余用戶對1萬7千部電影的不完全評分記錄推測出另外近300萬條電影評分記錄的數(shù)值.任何組織或個(gè)人只要能提交比Netflix現(xiàn)有電影推薦系統(tǒng)Cinematch效果好10%的新方法，就可以獲得誘人的7位數(shù)獎金.不僅如此，每年它還會為此提供5萬美元的年度進(jìn)步獎.三、應(yīng)用實(shí)例例4(下)、NetflixPrize

如果我們把用戶的評分?jǐn)?shù)據(jù)看作一個(gè)矩陣，矩陣的行表示1萬7千部電影，矩陣的列表示不同的用戶，上述NetflixPrize問題用數(shù)學(xué)語言描述就是，已知矩陣的某些元素來求這個(gè)完整矩陣.最終,2009年9月，科研團(tuán)隊(duì)BellKor’sPragmaticChaos獲得此獎，所建立的數(shù)學(xué)模型就是矩陣極小問題：

（6）三、應(yīng)用實(shí)例例5、多維標(biāo)度問題（管理學(xué)、統(tǒng)計(jì)學(xué)）已知12個(gè)城市中兩兩城市之間的距離，請你標(biāo)出這12個(gè)城市的平面坐標(biāo)位置.類似地，已知一個(gè)傳感器網(wǎng)絡(luò)，通過互相收發(fā)信號可以確定傳感器之間的距離，請確定傳感器的平面坐標(biāo)位置.此外，有100種白酒，品嘗家可以對每兩種白酒進(jìn)行品嘗對比，給出一種相近程度的得分（越相近得分越高，相差越遠(yuǎn)得分越低），我們希望從這些得分?jǐn)?shù)據(jù)中得到這100種白酒之間的排序表,所建立的數(shù)學(xué)模型就是一個(gè)矩陣秩極小問題：

(7)

這里，是一個(gè)特定的線性算子.三、應(yīng)用實(shí)例例6、Sparse-VisoCTCT是醫(yī)學(xué)診斷的主要工具之一，其成像的數(shù)學(xué)原理是Ax=b,其中x是一個(gè)未知向量，表示人體待檢查部位的圖像，維數(shù)512*512代表像素個(gè)數(shù)，b是一個(gè)測量值，其維數(shù)為1160*672代表射線的條數(shù)（1160代表圓周劃分的角度），A是（1160*672，512*512）階矩陣，由物理規(guī)律得到.由于其行數(shù)大于列數(shù)，一般情況下該方程無解.更為可怕的是行數(shù)多意味著“吃線”多，對人的身體危害極大.期望：“吃線少、時(shí)間短、圖像清晰”.現(xiàn)在，假設(shè)人體待檢查部位的圖像稀疏，那么應(yīng)用稀疏優(yōu)化理論和算法，可以進(jìn)行研究。

四、理論與算法凸松弛理論和算法凸松弛就是把稀疏優(yōu)化中的0-范數(shù)用1-范數(shù)代替，把矩陣秩極小問題的秩函數(shù)用核范數(shù)代替.從而模型（1）和（2）分別變成如下線性規(guī)劃（1#）和半定規(guī)劃(2#)，簡單易求解.

四、理論與算法■凸松弛理論和算法-算法如何求解（1#）？凸松弛算法.◆文再文與印臥濤，Goldfarb和張寅：不動點(diǎn)積極集算法，（軟件FPC_AS下載已經(jīng)超過2000次）；◆馬士謙與Goldfarb和Scheinberg：交替線性化方法的迭代復(fù)雜度分析（交替方向法的復(fù)雜度分析最早和最主要的成果之一）；◆何炳生、袁曉明和楊俊鋒等：交替方向增廣拉格朗日函數(shù)法.

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

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

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

四、理論與算法■凸差松弛理論和算法凸差松弛就是用(1范數(shù)-q范數(shù))代替0-范數(shù)，從圖像可以看出，它更接近稀疏優(yōu)化問題，能更好得區(qū)分無關(guān)項(xiàng)和相關(guān)項(xiàng)，從而有助于得到較精確的逼近.■光滑松弛理論和算法光滑松弛就是用一個(gè)光滑函數(shù)代替0-范數(shù)或者秩函數(shù)，從而得到光滑優(yōu)化.■加權(quán)1-范數(shù)松弛理論和算法加權(quán)1-范數(shù)松弛就是用加權(quán)1-范數(shù)代替0-范數(shù)，從而得到一個(gè)凸優(yōu)化.實(shí)踐表明很好，但是理論結(jié)果欠缺（待研究）。五、工作、分析與思考

理念：1、一幅待處理的圖像，如果用其向量x表示，則可以認(rèn)為

必須x>=0；

有時(shí)||x||_0<=s.2、一幅待處理的圖像，如果用其矩陣X表示，則可以認(rèn)為必須X>=0；

有時(shí)rank（X）<=r,半正定.我們的研究重點(diǎn)：1、非負(fù)稀疏優(yōu)化理論與算法；2、低秩半定矩陣優(yōu)化理論與算法。五、工作、分析與思考非凸低階正則方法（交大團(tuán)隊(duì)）：（1）對于低秩半定矩陣恢復(fù)問題，提出一類

正則不動點(diǎn)迭代方法，并應(yīng)用在圖像處理[5、6];（2）對于非負(fù)稀疏優(yōu)化問題，提出一類光滑投影算法，并應(yīng)用在成像技術(shù)[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.五、工作、分析與思考思考：對于非負(fù)稀疏優(yōu)化問題，提出一類L1-Lp不動點(diǎn)算法，