壓縮感知理論綜述與展望

沈 益，朱 歌

（浙江理工大學(xué) 理學(xué)院，杭州 310018）

0 引言

2003年瑞典卡羅林斯卡醫(yī)學(xué)院授予美國(guó)科學(xué)家保羅·勞特布爾和英國(guó)科學(xué)家彼得·曼斯菲爾德生理學(xué)或醫(yī)學(xué)獎(jiǎng)以表彰他們?cè)诤舜殴舱癯上窦夹g(shù)領(lǐng)域的突破性成就。磁共振成像儀（見(jiàn)圖1）采用磁共振成像（Magnetic Resonance Image，MRI）技術(shù)，能夠在對(duì)身體沒(méi)有損害的前提下，快速獲得患者身體內(nèi)部結(jié)構(gòu)的高精確度立體圖像。它也能用于跟蹤患者體內(nèi)的癌變情況，為更好地治療癌癥奠定基礎(chǔ)。磁共振成像儀最終通過(guò)計(jì)算機(jī)系統(tǒng)提供的掃描區(qū)域的數(shù)字圖像，如圖2。

數(shù)學(xué)上用向量x＝（x1，x2，…，xn）表示該灰度級(jí)圖片，其中xi表示對(duì)應(yīng)像素點(diǎn)的值。那么磁共振成像儀是如何獲得x的呢？這里暫且拋開(kāi)原子核旋轉(zhuǎn)，磁場(chǎng)等物理機(jī)制，考慮磁共振成像儀中圖像的測(cè)量與解碼。受物理原理的限制，磁共振成像儀并不能直接地，逐點(diǎn)地獲得數(shù)字圖像x，而是通過(guò)測(cè)量方案獲得數(shù)字圖像的測(cè)量信息。假設(shè)測(cè)量方案為F，測(cè)量信息b可表示為

其中F為n×n的矩陣，數(shù)字圖像和測(cè)量信息可具體地表示為

圖1 磁共振成像儀

圖2 灰度級(jí)圖像

MRI成像儀所采集到的不是直接的圖像像素，而是圖像經(jīng)歷過(guò)全局傅里葉變換后的數(shù)據(jù)。因此，（1）式等價(jià)于：

磁共振成像儀內(nèi)的計(jì)算機(jī)系統(tǒng)在成像過(guò)程中需要求解一個(gè)大型線性方程組。傳統(tǒng)數(shù)學(xué)理論指出，當(dāng)測(cè)量獲得的數(shù)據(jù)維度與原始數(shù)字圖像的維度相同時(shí)，通過(guò)求解數(shù)學(xué)模型（1）可以獲得精確地原始圖像。對(duì)于磁共振成像儀，這一求解過(guò)程可通過(guò)Fourier逆變換實(shí)現(xiàn)，如圖3。

圖3 利用 F ourier逆變換恢復(fù)信號(hào)

圖4 利用F ourier 逆變換恢復(fù)稀疏信號(hào)

但磁共振成像儀在采集數(shù)據(jù)b的過(guò)程中，由于器官運(yùn)動(dòng)（如呼吸等非自主運(yùn)動(dòng)）或患者自主運(yùn)動(dòng)等因素造成圖像模糊，此時(shí)僅得到圖像的部分頻譜信息（如圖4），采用傳統(tǒng)模型和Fourier逆變換方法獲得的數(shù)字圖像不夠理想。

對(duì)于這樣的困難，數(shù)學(xué)家 David Donoho、Emamnuel Candès、Terence Tao等提出了壓縮感知原理［1-4］。這一原理的基本假設(shè)為，原始數(shù)字圖像具有稀疏表示?；诖思僭O(shè)，在信息缺失的情況下，通過(guò)求解凸優(yōu)化模型可以得到實(shí)際所需的圖像，如圖5。

這一理論的發(fā)現(xiàn)從數(shù)學(xué)上幾乎完美地解決了信息缺失的問(wèn)題。該理論極大地縮短了核磁共振成像儀的掃描時(shí)間，同時(shí)仍能獲得等同的數(shù)字圖像。這樣不僅能幫助醫(yī)生快速做出診斷，也能在單位時(shí)間內(nèi)完成更多病人的檢測(cè)，給磁共振成像儀帶來(lái)了新的變革。正是基于這樣的數(shù)值仿真實(shí)驗(yàn)，壓縮感知理論一經(jīng)提出就獲得了數(shù)學(xué)、信息科學(xué)、統(tǒng)計(jì)學(xué)、醫(yī)學(xué)等研究領(lǐng)域的廣泛關(guān)注。接下來(lái)，我們將從數(shù)學(xué)角度闡述這一理論的基本框架。

1 稀疏信號(hào)恢復(fù)

圖 求解優(yōu)化模型恢復(fù)稀疏信號(hào)5

現(xiàn)實(shí)中的信號(hào)往往是以時(shí)間（例如聲音）為變量的連續(xù)函數(shù)。為了獲得離散化數(shù)字信號(hào)，需要對(duì)原始信號(hào)進(jìn)行采樣。與傳統(tǒng)壓縮中先采樣后壓縮的方式不同，壓縮感知并不直接對(duì)信號(hào)進(jìn)行采樣，而是以線性投影的方式直接獲取壓縮后的數(shù)據(jù)，實(shí)現(xiàn)信號(hào)的編碼過(guò)程。數(shù)學(xué)上，這一過(guò)程可描述為：假設(shè)x為稀疏信號(hào)，A為m×n維的測(cè)量矩陣（m＜n），利用測(cè)量矩陣A對(duì)稀疏信號(hào)x進(jìn)行投影，得到壓縮后的數(shù)據(jù)b，即

其中，x＝( x1，x2，…，xn)T是長(zhǎng)度為 n的一維稀疏信號(hào)，b＝( b1，b2，…，bm)T是長(zhǎng)度為m的測(cè)量信息。由于m＜n，線性方程組（2）的解不唯一。即不能通過(guò)測(cè)量信息b求得原始信號(hào)x。

稀疏性的引入克服了解不唯一的問(wèn)題。關(guān)于稀疏假設(shè)的合理性，我們?cè)诤竺嬖僮鹘榻B。用‖x‖0表示向量x中不為零的分量個(gè)數(shù)。如果向量中不為零的分量個(gè)數(shù)‖x‖0不超過(guò)s個(gè)，則稱向量x是s稀疏的。如果測(cè)量矩陣的任意2s列是線性無(wú)關(guān)的，那么該方程組有唯一的s稀疏解。此時(shí)（2）式可以轉(zhuǎn)化為求解一個(gè)非凸的優(yōu)化模型

來(lái)恢復(fù)原始信號(hào)。從另一角度看，求解該模型等價(jià)于挑選出線性方程組所有可行解中最“稀疏”的解。這種遍歷的求解過(guò)程使得模型的求解成為一個(gè)NP難問(wèn)題。一個(gè)替代方案是通過(guò)求解凸的優(yōu)化模型來(lái)恢復(fù)原始信號(hào)，其中

1.1 測(cè)量矩陣

相較于非凸模型（3），凸優(yōu)化模型（4）的優(yōu)勢(shì)在于：可通過(guò)凸優(yōu)化算法快速求解。在數(shù)學(xué)上，如果一個(gè)實(shí)際問(wèn)題可以表示成凸優(yōu)化問(wèn)題，那么就認(rèn)為其能夠得到很好的解。在給出兩個(gè)模型等價(jià)性的數(shù)學(xué)描述之前，先考慮一個(gè)簡(jiǎn)單的幾何描述：設(shè)

那么線性方程組

的所有可行解在二維平面中為一條直線，如圖6所示。在x2軸附近，通過(guò)求解模型（3）模型（4）均能得稀疏解

這個(gè)例子表明了在二維情況下模型（3）與模型（4）的等價(jià)性。

為了討論高維情況下兩個(gè)模型的等價(jià)性，首先引入集合T? ｛1，…，n｝與其補(bǔ)集 Tc＝｛1，…，n｝T。對(duì)任意的 n維向量 h，定義n維向量hT滿足：hT中第i∈T個(gè)分量為hi，第i∈Tc個(gè)分量為0。對(duì)于s稀疏向量x，記其非零分量的坐標(biāo)集合為T，則有

圖6 極小化 l1范數(shù)稀疏解的幾何解釋

模型（3）與模型（4）的等價(jià)性刻畫為如下定理：

定理1（零空間性質(zhì)） 對(duì)于任意的s稀疏向量，模型（3）與模型（4）的解相等當(dāng)且僅當(dāng)矩陣A滿足s階零空間條件

對(duì)于任意的#T＝s成立。

驗(yàn)證一個(gè)測(cè)量矩陣A是否滿足零空間性質(zhì)是一個(gè)NP難問(wèn)題。這為測(cè)量矩陣的設(shè)計(jì)帶來(lái)一定的困難。隨機(jī)矩陣的引入較完美地解決了這困難。

稱矩陣A滿足s階約束等距性質(zhì)，如果存在正常數(shù)δs使得

對(duì)于任意的‖x‖0≤s成立。正常數(shù)δs稱為s階約束等距常數(shù)。當(dāng) δ2s＜1時(shí)，若 s稀疏向量 x′，x″均為線性方程組 b＝A x的解，則

因此，線性方程組b＝A x有唯一的s稀疏解。約束等距性質(zhì)由Emamnuel Candès、Terence Tao首先引入［3］，同時(shí)他們證明：

定理2［3］如果矩陣A滿足約束等距性質(zhì)且約束等距常數(shù)滿足

則矩陣A滿足零空間條件。

定理2中關(guān)于約束等距常數(shù)的條件（5）并不是最優(yōu)的。自2004年定理2的提出以來(lái)，很多學(xué)者都嘗試對(duì)這一結(jié)果進(jìn)行改進(jìn)（改進(jìn)這一條件并取得了一系列成果）。關(guān)于最優(yōu)界的估計(jì)目前已經(jīng)完全解決，具體可見(jiàn)參考文獻(xiàn)［2-3，5］等。定理2另一重要意義在于，很多類型的隨機(jī)矩陣都滿足約束等距性質(zhì)，如高斯隨機(jī)矩陣、部分Fourier隨機(jī)矩陣。

矩陣A稱為高斯隨機(jī)矩陣，如果矩陣A中每一元素ai，j均為獨(dú)立隨機(jī)變量且服從均值為0、方差為1／m的高斯分布，即

矩陣A稱為部分Fourier隨機(jī)矩陣，如果矩陣的每一行從離散Fourier矩陣

中等概率地隨機(jī)取得。

定理3［4］當(dāng)高斯隨機(jī)矩陣A∈ ?m×n的行列滿足

時(shí)，矩陣滿足s階約束等距性質(zhì)的概率不低于1-e-c(δs)m。

定理4［2］假設(shè)部分Fourier隨機(jī)矩陣A∈?m×n測(cè)量次數(shù)滿足m＝O( s ln6(n) ) 則測(cè)量矩陣A在大概率意義下滿足s階約束等距性質(zhì)。

注1.當(dāng)高斯隨機(jī)矩陣的測(cè)量次數(shù)滿足條件（6）時(shí)，通過(guò)求解模型（4）可以精確地恢復(fù)s稀疏信號(hào)［6］。

注2.部分Fourier隨機(jī)矩陣A∈?m×n的測(cè)量次數(shù)目前被改進(jìn)為O( s ln4(n) )［7］。很多學(xué)者猜測(cè)這一測(cè)量結(jié)果目前還有改進(jìn)的空間。理想的估計(jì)應(yīng)為O( s ln(n))。

如果向量x為非稀疏信號(hào)，取向量中絕對(duì)值最大的s個(gè)元素，對(duì)應(yīng)的坐標(biāo)集合記為T，則有

我們稱向量xT為向量x的最佳s項(xiàng)非線性逼近。非線性逼近思想在圖像壓縮中有著重要的作用。當(dāng)向量的元素按照絕對(duì)值從大到小排列后具有多項(xiàng)式的衰減速度，則稱這個(gè)向量是可壓縮的。生活中常見(jiàn)的數(shù)字圖像的小波系數(shù)往往是可壓縮的。例如，典型的1 024×2 048數(shù)字圖像對(duì)應(yīng)一個(gè)兩百多萬(wàn)維度的小波系數(shù)。但通常情況下，約十萬(wàn)個(gè)小波系數(shù)就足夠獲取圖像所有的可見(jiàn)細(xì)節(jié)，其余約一百九十萬(wàn)小波系數(shù)只貢獻(xiàn)少量的、大多數(shù)觀測(cè)者基本看不見(jiàn)的細(xì)節(jié)信息。這十萬(wàn)個(gè)小波系數(shù)事實(shí)上就是原始小波系數(shù)的非線性逼近。目前，微信的圖片傳輸正是采用這樣一個(gè)數(shù)據(jù)壓縮方案。

定理5［8］假設(shè)觀測(cè)值滿足

b＝A x+ω，

其中，ω是測(cè)量時(shí)的噪音，滿足‖ω‖2≤η。如果測(cè)量矩陣A滿足約束等距性質(zhì)且約束等距常數(shù)滿足條件（5），則基追蹤（basis pursuit）模型

其中，常數(shù)C1、C2依賴于約束等距常數(shù)。

定理5可以看成定理2在一般情況下的推廣，但是兩個(gè)定理對(duì)于約束等距常數(shù)的要求沒(méi)有差別。最優(yōu)的約束等距常數(shù)估計(jì)由文獻(xiàn)［9-10］給出。如果通過(guò)模型恢復(fù)的信號(hào)x＾和原始信號(hào)x之間的誤差估計(jì)滿足不等式（8），則稱這個(gè)模型可以得到穩(wěn)定解。對(duì)于稀疏信號(hào)的線性回歸問(wèn)題，基于l1范數(shù)的凸優(yōu)化模型還有Lasso和Danzig Selector［11］等，模型的解也被證明具有類似于不等式（8）的穩(wěn)定性估計(jì)。從凸分析的角度，模型（4）可轉(zhuǎn)化為一個(gè)線性規(guī)劃問(wèn)題，基追蹤模型（7）可轉(zhuǎn)化為一個(gè)二階錐規(guī)劃問(wèn)題。兩者均可使用相應(yīng)的優(yōu)化算法求解。

1.2 非凸模型

基于l1的凸優(yōu)化模型（4）恢復(fù)s稀疏的n維信號(hào)，要求測(cè)量次數(shù)滿足m＝O（s ln（n／s））。而基于l0的非凸模型（3），理論上要求測(cè)量次數(shù)滿足m＝O（s）。因此，兩個(gè)模型是有著本質(zhì)的不同的。從理論分析的角度出發(fā)，兩個(gè)模型之間需要建立更多的聯(lián)系。一個(gè)統(tǒng)一的模型是引入lp范數(shù)（0＜p≤1），信號(hào)恢復(fù)的模型為

pp很好地刻畫了信號(hào)的稀疏性。雖然求解Δp問(wèn)題仍為NP-Hard問(wèn)題，但是任意一個(gè)Δp的解為局部最優(yōu)解，求解Δp的局部最優(yōu)解只需多項(xiàng)式時(shí)間。因此，相比于求解Δ0，求解Δp擁有更快的計(jì)算速度。另一重要原因在于，相比求解Δ1問(wèn)題，Δp問(wèn)題可以通過(guò)較少的測(cè)量次數(shù)重構(gòu)稀疏信號(hào)。Chartrand等給出了理論證明［12］：對(duì)于由均值為零的獨(dú)立高斯分布生成的測(cè)量矩陣A，測(cè)量次數(shù)滿足

時(shí)，Δp問(wèn)題在概率下有唯一K項(xiàng)稀疏解，其中C1()p、C2()p為常數(shù)，并有l(wèi)imp→0pC2()p＝0。這一結(jié)果從理論上統(tǒng)一了 Δ0、Δp、Δ1中對(duì)測(cè)量次數(shù)的不同要求［13］。隨機(jī)矩陣滿足一定的約束等距性質(zhì)時(shí)，Δp( 0＜p＜1)模型的最優(yōu)解是穩(wěn)定的。模型的穩(wěn)定性也可以通過(guò)隨機(jī)約束等距矩陣的性質(zhì)刻畫。

定理6［14］對(duì)于任意的0＜p≤1，如果測(cè)量矩陣A滿足約束等距性質(zhì)且約束等距常數(shù)滿足

其中，η是方程

其中，常數(shù)C1、C2依賴于約束等距常數(shù)。

2 稀疏表示系統(tǒng)-緊框架

壓縮感知理論的一個(gè)重要假設(shè)為：測(cè)量的信號(hào)為稀疏信號(hào)。雖然現(xiàn)實(shí)生活中的大多數(shù)信號(hào)不滿足這一假設(shè)，但是它們的小波系數(shù)往往是可壓縮的。對(duì)于光滑的信號(hào)，最經(jīng)典也是使用最廣泛的緊支集小波（Daubechies正交小波和雙正交小波等）具有的消失矩性質(zhì)保證了其小波系數(shù)呈指數(shù)衰減。但是對(duì)于二維圖像的邊界特征，特別是光滑的圓弧邊界，Daubechies正交小波無(wú)法做到稀疏表示。因此 Curvelet［15］、對(duì)偶雙樹(shù)復(fù)小波［16］等緊小波框架被廣泛地應(yīng)用到圖像處理中。相較于正交小波，多方向緊小波框架［17］對(duì)二維圖像有更稀疏的表達(dá)，從而能獲得更優(yōu)的非線性逼近。

給定緊框架小波算子D∈?d×n及其共軛轉(zhuǎn)置算子DT，假設(shè)信號(hào)x在緊小波框架算子D下有稀疏表示c＝D x且D T D x＝x。理論研究和實(shí)驗(yàn)表明：對(duì)于非稀疏信號(hào)x∈?n，測(cè)量矩陣A滿足一定的條件（例如，E.Candès等提出的D-RIP條件［18］），即使測(cè)量次數(shù)m小于信號(hào)維度n，仍能通過(guò)求解帶約束的Analysis模型

其中，c1、c2是依賴于D-RIP條件的常數(shù)，向量 ( D x)[k]表示向量D x中絕對(duì)值最大的k個(gè)元素，并將其余元素取為0。針對(duì)不同的信號(hào)與測(cè)量矩陣，需要選擇不同的優(yōu)化模型。特別地，引入緊框架算子后，可選擇的模型更加廣泛。D-RIP條件的成立并不依賴于緊框架，但在給定測(cè)量矩陣的情況下，能否找到合適的緊框架使得信號(hào)在該緊框架下具有稀疏表示會(huì)直接影響信號(hào)的恢復(fù)程度。緊框架的引入不僅使得壓縮感知理論被更廣泛地應(yīng)用到實(shí)際問(wèn)題中，同時(shí)也推動(dòng)了理論本身的發(fā)展。目前對(duì)于Analysis模型及其衍生的優(yōu)化模型的研究最為廣泛。為方便求解，大多數(shù)算法先將模型轉(zhuǎn)化為無(wú)約束形式：

模型（13）稱為 ALASSO［19］，當(dāng)測(cè)量矩陣 A滿足一定的 D-RIP條件時(shí)，模型（13）的解是穩(wěn)定的［19-20］。

如果圖像或信號(hào)由幾類性質(zhì)相異的成分組成，如由不同樂(lè)器奏成的音樂(lè)，由神經(jīng)元的胞體、枝晶、脊柱組成的神經(jīng)生物學(xué)圖像等。例如圖7中分解為Cartoon部分xc和Texture部分xt的數(shù)字圖像，其中，Cartoon部分在緊小波框架表示下是稀疏的，Texture部分在局部余弦變換下是稀疏的［21-22］。

圖7 分解為 C artoon與 T exture成分的數(shù)字圖像

對(duì)于這種結(jié)構(gòu)復(fù)雜的圖像或信號(hào)，需要采用兩個(gè)或兩個(gè)以上的緊框架建立恢復(fù)圖像的優(yōu)化模型，例如

E.Candès等針對(duì)壓縮感知問(wèn)題提出了該模型［18］。該模型最早稱為形態(tài)學(xué)成分分析（morphological component analysis，MCA），用于分解圖像Cartoon和Texture兩類成分。模型的穩(wěn)定性分析見(jiàn)文獻(xiàn)［23］。不同之處在于MCA方法中算子A為恒等矩陣，而壓縮感知問(wèn)題中算子A為欠定矩陣。

3 正交匹配算法

最后介紹正交匹配算法（Orthogonal Matching Pursuit，OMP）［24］。OMP算法的基本思想為在每次迭代中選取一個(gè)指標(biāo)作為稀疏信號(hào)非零元素的坐標(biāo)。對(duì)于s稀疏信號(hào)，正交匹配算法一個(gè)自然的停止準(zhǔn)則是在迭代s次后停止。每次迭代時(shí)，OMP算法實(shí)際上是將所選測(cè)量矩陣的列依次進(jìn)行Schimidt正交化，然后將待分解信號(hào)減去正交化后矩陣列上的對(duì)應(yīng)分量，得到殘差。算法的提出可以追溯到1993年Mallat等學(xué)者的工作［25］。2004年，Tropp將 OMP算法成功地引入壓縮感知領(lǐng)域中［26］。當(dāng)測(cè)量矩陣的約束等距常數(shù)滿足時(shí)（此上界為最優(yōu)估計(jì)），OMP可在s步迭代后精確地恢復(fù)k稀疏信號(hào)［27］。即當(dāng)時(shí)，存在確定的測(cè)量矩陣使得OMP無(wú)法準(zhǔn)確地選取信號(hào)非零元素的坐標(biāo)［5］。正交匹配算法沒(méi)有參數(shù)選擇的需求，易實(shí)現(xiàn)且計(jì)算復(fù)雜度不高，因此被廣泛應(yīng)用到圖像壓縮、去噪、字典學(xué)習(xí)等問(wèn)題中［28］。稀疏表示是字典學(xué)習(xí)的核心思想。確定的字典包括小波基、冗余緊框架、Gabor框架等。確定字典的基本假設(shè)是信號(hào)可以由字典中的一個(gè)或幾個(gè)元素表示。但是給定的字典總是具有局限性，例如在小波分析中，一般假設(shè)信號(hào)具有一定的光滑性。另一種選擇字典的方法是自適應(yīng)的，字典學(xué)習(xí)考慮從數(shù)據(jù)本身出發(fā)，通過(guò)一定的方法，例如求解優(yōu)化模型，構(gòu)造適用于該數(shù)據(jù)或類似數(shù)據(jù)的表示系統(tǒng)。

4 總結(jié)與展望

壓縮感知恢復(fù)信號(hào)的方式是通過(guò)各種優(yōu)化方法從壓縮測(cè)量中恢復(fù)原始信號(hào)。當(dāng)原始信號(hào)稀疏或可壓縮時(shí)，且測(cè)量矩陣滿足一定條件，可通過(guò)求解凸優(yōu)化模型高概率地恢復(fù)原始信號(hào)。當(dāng)原始信號(hào)不稀疏，但在某組基或某組框架下可以得到信號(hào)的稀疏表達(dá)時(shí)，且測(cè)量矩陣滿足一定條件，通過(guò)求解凸優(yōu)化模型可以得到穩(wěn)定解。理論上，基于RIP條件的穩(wěn)定性分析的相關(guān)理論目前已經(jīng)取得較為完善的理論結(jié)果。在應(yīng)用上，壓縮感知理論已經(jīng)取得了標(biāo)志性的工業(yè)成果 Donoho，F(xiàn)rom Blackboard to Bedside：High-dimensional Geometry is Transforming the MRI Industry。

受壓縮感知理論的啟發(fā)，其他相關(guān)研究課題的理論成果及其應(yīng)用，例如低秩矩陣恢復(fù)、相位恢復(fù)、1-bit壓縮感知、超分辨分析、盲去卷積等也取得了較大的突破。壓縮感知理論系統(tǒng)地闡述數(shù)據(jù)的稀疏表示與恢復(fù)及其相關(guān)理論，L1范數(shù)的引入使得基于稀疏表示的數(shù)學(xué)建模具備了非常廣泛的應(yīng)用前景和理論支撐。特別是在人工智能，深度學(xué)習(xí)等領(lǐng)域，例如，稀疏自編碼直接把多個(gè)單層基于壓縮感知的稀疏編碼機(jī)疊加在一起形成了一個(gè)深度學(xué)習(xí)的模型。如何將壓縮感知這一研究領(lǐng)域的理論成果應(yīng)用到深度學(xué)習(xí)中，解釋深度學(xué)習(xí)的數(shù)學(xué)機(jī)制，是一個(gè)廣闊的研究方向。

致謝：論文在浙江大學(xué)李松教授的建議及鼓勵(lì)下完成，在此表示感謝。