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

稀疏優(yōu)化與低秩矩陣優(yōu)化第1頁，共25頁，2023年，2月20日，星期一內(nèi)容提要模型與基本概念稀疏優(yōu)化與壓縮感知應(yīng)用實(shí)例理論與算法分析與思考第2頁，共25頁，2023年，2月20日，星期一一、模型與基本概念稀疏優(yōu)化問題是指在某種線性約束條件下，求一個(gè)決策變量使其非零元素個(gè)數(shù)達(dá)到極小.它的基本數(shù)學(xué)模型是：其中，b是一個(gè)m維向量,m<n.矩陣秩極小（或低秩矩陣恢復(fù)）問題是指在某種線性約束條件下，求一個(gè)決策矩陣使其秩達(dá)到極小.它的基本數(shù)學(xué)模型是：其中

是從到的線性變換，b是一個(gè)d維向量.第3頁，共25頁，2023年，2月20日，星期一一、模型與基本概念【注】1、模型（2）是模型（1）的一個(gè)推廣；2、可以把零范數(shù)和秩函數(shù)放在約束中，變成

非凸

約束優(yōu)化模型；3、如果問題是高維復(fù)雜的，則可在模型中增加其他約束條件或者目標(biāo)函數(shù),如非負(fù)稀疏優(yōu)化、低秩半定矩陣矩陣優(yōu)化.第4頁，共25頁，2023年，2月20日，星期一一、模型與基本概念在一般情況下，模型（1）是一個(gè)NP-困難的組合優(yōu)化問題,因?yàn)椋?）等價(jià)于在如下有限個(gè)特殊集合與集合中選一個(gè)解.由此可知，所有這些模型在一般情況下都是NP-困難問題.◆如何松弛（近似）易求解？→理論研究；◆如何設(shè)計(jì)算法？→算法研究；◆如何應(yīng)用到實(shí)際部門？→應(yīng)用研究.第5頁，共25頁，2023年，2月20日，星期一

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

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

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

具有稀疏性，則其數(shù)學(xué)意義就是零元素多，即非零元素少,于是可以轉(zhuǎn)化為稀疏優(yōu)化模型：第7頁，共25頁，2023年，2月20日，星期一

二、稀疏優(yōu)化與壓縮感知假設(shè)原始信號(hào)為矩陣X（維數(shù)大），測(cè)量信息為矩陣B（維數(shù)?。宜鼈儩M足線性關(guān)系，則其數(shù)學(xué)模型就是一個(gè)線性矩陣方程組A(X)=B.如果原始信號(hào)矩陣X具有低秩性，則其數(shù)學(xué)意義就是期望矩陣X的秩rank(X)極小.于是可以轉(zhuǎn)化為矩陣秩極小問題：如果原始信號(hào)海量高維，呈現(xiàn)出復(fù)雜性、限制性等，則可以根據(jù)其各種特性建立更為細(xì)致的優(yōu)化模型.第8頁，共25頁，2023年，2月20日，星期一

二、稀疏優(yōu)化與壓縮感知文獻(xiàn)計(jì)量分析：至2011年10月，壓縮感知共涉及29個(gè)學(xué)科領(lǐng)域,主要應(yīng)用于工程技術(shù)(50.917%)、計(jì)算機(jī)科學(xué)(21.865%)、數(shù)學(xué)應(yīng)用(16.667%)、放射核醫(yī)學(xué)成像(13.761%)、物理(10.398%)、光學(xué)設(shè)計(jì)(9.021%)、成像科學(xué)攝影技術(shù)(4.587%)、電信技術(shù)(4.128%)、地球化學(xué)物理學(xué)(3.823%)、生物分子學(xué)(2.446%)等領(lǐng)域。

第9頁，共25頁，2023年，2月20日，星期一三、應(yīng)用實(shí)例例1、帶選擇限制的投資組合優(yōu)化問題

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

眾說周知，二人矩陣博弈模型、具有生產(chǎn)和投資的經(jīng)濟(jì)均衡模型、交通流均衡模型等，都可以轉(zhuǎn)化為互補(bǔ)問題.如果這個(gè)互補(bǔ)問題有多個(gè)解，則在這個(gè)解集中尋找一個(gè)最為稀疏的解：第11頁，共25頁，2023年，2月20日，星期一三、應(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ù)測(cè)，協(xié)方差矩陣估計(jì)被應(yīng)用在越來越多的學(xué)科領(lǐng)域和生產(chǎn)實(shí)際中，如氣象預(yù)報(bào)、基因表達(dá)、功能MR成像、風(fēng)險(xiǎn)管理和套利優(yōu)化、社交網(wǎng)絡(luò).第12頁，共25頁，2023年，2月20日，星期一三、應(yīng)用實(shí)例例3(下)、低秩協(xié)方差矩陣估計(jì)

給定對(duì)稱矩陣

，用

表示半正定性.從最優(yōu)化的角度分析，如果低秩性視為一個(gè)目標(biāo)，那么低秩協(xié)方差矩陣估計(jì)問題可以描述為，已知對(duì)稱矩陣

，求解如下的多目標(biāo)優(yōu)化：

（5）

這是一個(gè)矩陣秩極小問題.第13頁，共25頁，2023年，2月20日，星期一三、應(yīng)用實(shí)例例4(上)、NetflixPrize

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

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

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

(7)

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

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

四、理論與算法凸松弛理論和算法-理論模型（1）與（1#）是什么關(guān)系？凸松弛理論：RIP性質(zhì)、NSP性質(zhì)、RSP性質(zhì)、S-good性質(zhì).●孔令臣研究了在若當(dāng)代數(shù)意義下稀疏優(yōu)化的幾種性質(zhì).第19頁，共25頁，2023年，2月20日，星期一

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

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

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

◆周聲龍得到與1-范數(shù)松弛一樣好的RIP界.第21頁，共25頁，2023年，2月20日，星期一

四、理論與算法非凸松弛理論和算法非凸松弛算法：◆陳小君、徐鳳敏和葉蔭宇：非光滑非凸非Lipschitz優(yōu)化（建立了其局部最小值點(diǎn)的一階、二階必要和充分條件，給出了可度量的穩(wěn)定點(diǎn)定義）；◆徐宗本等：1/2正則理論和方法（在圖像處理領(lǐng)域取得了很好的效果）；◆陳小君、牛凌峰和袁亞湘：光滑信賴域算法（收斂于非Lipschitz優(yōu)化二階穩(wěn)定點(diǎn)）；◆邊偉、陳小君和葉蔭宇：二階算法（收斂于非Lipschitz優(yōu)化二階穩(wěn)定點(diǎn)，給出了其最壞復(fù)雜性分析）.第22頁，共25頁，2023年，2月20日，星期一

四、理論與算法■凸差松弛理論和算法凸差松弛就是用(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é)果欠缺（待研究）。第23頁，共25頁，2023年，2月20日，星期一五、工作、分析與思考

理念：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)化理論與算法。第24頁，共25頁，2023年，2月20日，星期一五、工作、分析與思考基本理論（交大團(tuán)隊(duì)）：（1）建立了在若當(dāng)代數(shù)意義下的壓縮感知松弛理論，即RIP性質(zhì)、NSP性質(zhì)、S-goodness[1]；（2）對(duì)于1/2松弛(3/4）[2]，目前最好的RIP界為（3）證明廣義Z-矩陣、Lya