【文章內(nèi)容簡介】 相關(guān)性。（2）為小波基，是noiselet。這里，noiselet和Haar小波基間的相關(guān)系數(shù)是，noiselet和Daubechies 。這也可以擴(kuò)展到高維情況。noiselets也和尖峰信號(hào)及傅立葉基高度不相關(guān)。人們對(duì)noiselets感興趣基于以下兩個(gè)事實(shí)：1）它們和為圖像數(shù)據(jù)和其它類型的數(shù)據(jù)提供稀疏表示的系統(tǒng)不相關(guān)；2）它們具有快速算法。noiselet變換的時(shí)間復(fù)雜度為O(N)，而且類似于傅立葉變換，noiselet矩陣不需要存儲(chǔ)。這一點(diǎn)對(duì)于高效的數(shù)字計(jì)算是至關(guān)重要的。如果沒有高效的計(jì)算，CS的實(shí)用性就會(huì)大打折扣。（3）為隨機(jī)矩陣，則可以是任何固定的基。此時(shí)它們之間具有極大不相關(guān)。例如，可以通過在單位球面上獨(dú)立均勻地采樣并做規(guī)范正交化得到，此時(shí)，和間的相關(guān)性以很高的概率為。各項(xiàng)服從獨(dú)立同分布的隨機(jī)波形，例如高斯分布或者，也表現(xiàn)出和任何固定基具有很小的相關(guān)性。研究者們通過大量的實(shí)驗(yàn)分析，得出如下結(jié)論：精確重構(gòu)所需要的觀測值個(gè)數(shù)依賴于稀疏變換基和觀測基之間的不相關(guān)性。不相關(guān)性越強(qiáng)，所需的個(gè)數(shù)越少；反之，相關(guān)性越強(qiáng)，例如，則需要采樣所有的系數(shù)才能保證精確重構(gòu)。 三個(gè)關(guān)鍵技術(shù)從以上壓縮感知理論的介紹中我們可以看出，壓縮感知理論主要包括以下三個(gè)方面的內(nèi)容：（1）信號(hào)稀疏表示；（2）信號(hào)的編碼測量即觀測矩陣的設(shè)計(jì)；（3）信號(hào)重構(gòu)算法的設(shè)計(jì)。信號(hào)的稀疏表示是指當(dāng)將信號(hào)投影到某個(gè)正交變換基時(shí)，一般情況下絕大多數(shù)的變換系數(shù)的絕對(duì)值都是很小的，得到的變換向量也是稀疏的或者是近似稀疏的，這是原始信號(hào)的一種簡潔的表達(dá)方式，也是壓縮傳感理論的先驗(yàn)條件。信號(hào)必須得在某種變換下才可以進(jìn)行稀疏表示。通常我們可以選取的變換基有離散傅里葉變換基（DFT）、離散余弦變換基（DCT）、離散小波變換基（DWT）、Curvelet 變換基、Gabor 變換基還有冗余字典等。在信號(hào)的編碼測量即觀測矩陣的設(shè)計(jì)過程中，要選擇穩(wěn)定的觀測矩陣，觀測矩陣的選取必須滿足受限等距特性(Restricted Isometry Property，RIP)準(zhǔn)則，才能保證信號(hào)的投影能夠保持原始信號(hào)的結(jié)構(gòu)特征。通過原始信號(hào)與觀測矩陣相乘我們可以獲得原始信號(hào)的線性投影值。最后設(shè)計(jì)合適的重構(gòu)算法從所得到的觀測值和原來的觀測矩陣來重構(gòu)原始始號(hào)。所以對(duì)壓縮感知理論的研究也主要是基于這三個(gè)方面的內(nèi)容：（1）信號(hào)的稀疏表示。即對(duì)于信號(hào) ，如何找到一個(gè)合適的正交基或者緊框架Ψ，以使得原始信號(hào)在Ψ上的表示是稀疏的。（2）觀測矩陣的設(shè)計(jì)。即如何設(shè)計(jì)一個(gè)平穩(wěn)且滿足受限等距特性條件或者與變換基Ψ 滿足不相關(guān)約束條件的M N 維觀測矩陣Φ，以保證信號(hào)稀疏表示后的向量Θ能從原來的N 維降到M 維時(shí)所包含的重要信息沒有受到破壞，從而保證原始信號(hào)的準(zhǔn)確重構(gòu)。這個(gè)過程也就是壓縮感知理論中信號(hào)的低速采樣過程。（3）重構(gòu)算法的設(shè)計(jì)。即如何設(shè)計(jì)快速有效且穩(wěn)定的重構(gòu)算法，從所得到的低維觀測向量中準(zhǔn)確地恢復(fù)原始信號(hào)。下面我們對(duì)壓縮感知理論的這三個(gè)關(guān)鍵技術(shù)做一個(gè)詳細(xì)的總結(jié)和分析，以為后文對(duì)壓縮感知理論在圖像重構(gòu)方面的研究打下基礎(chǔ)。從傅立葉變換到小波變換再到后來興起的多尺度幾何分析（Ridgelet，Curvelet，Bandelet，Contourlet），科學(xué)家們的研究目的均是為了研究如何在不同的函數(shù)空間為信號(hào)提供一種更加簡潔、直接的分析方式，所有這些變換都旨在發(fā)掘信號(hào)的特征并稀疏表示它，進(jìn)一步研究用某空間的一組基函數(shù)表示信號(hào)的稀疏程度或分解系數(shù)的能量集中程度。文獻(xiàn)[23]給出稀疏的定義：信號(hào)X在正交基下的變換系數(shù)向量為，假如對(duì)于0p2和R 0，這些系數(shù)滿足： （）則說明系數(shù)向量在某種意義下是稀疏的。文獻(xiàn)[34]給出另一種定義：如果變換系數(shù)的支撐域的勢小于等于K，則可以說信號(hào)X 是K 項(xiàng)稀疏。如何找到信號(hào)最佳的稀疏域？這是壓縮感知理論應(yīng)用的基礎(chǔ)和前提，只有選擇合適的基表示信號(hào)才能保證信號(hào)的稀疏度，從而保證信號(hào)的恢復(fù)精度。在研究信號(hào)的稀疏表示時(shí)，可以通過變換系數(shù)衰減速度來衡量變換基的稀疏表示能力。Cand232。s 和Tao通過研究發(fā)現(xiàn)，滿足冪定律衰減的信號(hào)，可利用壓縮感知理論進(jìn)行恢復(fù)，并且重構(gòu)誤差滿足： （）其中r=1/p1/2，0p1。文獻(xiàn)[30]指出光滑信號(hào)的Fourier系數(shù)、小波系數(shù)、有界變差函數(shù)的全變差范數(shù)、振蕩信號(hào)的Gabor系數(shù)及具有不連續(xù)邊緣的圖像信號(hào)的Curvelet系數(shù)等都具有足夠的稀疏性，可以通過壓縮感知理論恢復(fù)信號(hào)。如何找到或構(gòu)造適合一類信號(hào)的正交基，以求得信號(hào)的最稀疏表示，這是一個(gè)有待進(jìn)一步研究的問題。Gabriel Peyr233。把變換基是正交基的條件擴(kuò)展到了由多個(gè)正交基構(gòu)成的正交基字典。即在某個(gè)正交基字典里，自適應(yīng)地尋找可以逼近某一種信號(hào)特征的最優(yōu)正交基，根據(jù)不同的信號(hào)尋找最適合信號(hào)特性的一組正交基，對(duì)信號(hào)進(jìn)行變換以得到最稀疏的信號(hào)表示。最近幾年，對(duì)稀疏表示研究的另一個(gè)熱點(diǎn)是信號(hào)在過完備字典下的稀疏分解。字典的選擇應(yīng)盡可能好地符合被逼近信號(hào)的結(jié)構(gòu)，其構(gòu)成可以沒有任何限制。從從過完備字典中找到具有最佳線性組合的K項(xiàng)原子來表示一個(gè)信號(hào)，稱作信號(hào)的稀疏逼近或高度非線性逼近。過完備庫下的信號(hào)稀疏表示方法最早由Mallat和Zhang于1993年首次提出， 并引入了MP算法。文獻(xiàn)以淺顯易懂的表達(dá)說明了過完備字典對(duì)信號(hào)表示的必要性，同時(shí)還指出字典的構(gòu)成應(yīng)盡量符合信號(hào)本身所固有的特性。目前信號(hào)在過完備字典下的稀疏表示的研究集中在兩個(gè)方面：（1）如何構(gòu)造一個(gè)適合某一類信號(hào)的過完備字典；（2）如何設(shè)計(jì)快速有效的稀疏分解算法。這兩個(gè)問題也一直是該領(lǐng)域研究的熱點(diǎn)，學(xué)者們對(duì)此已做了一些探索，其中，以非相干字典為基礎(chǔ)的一系列理論證明得到了進(jìn)一步改進(jìn)。從非線性逼近角度來講，信號(hào)的稀疏逼近包含兩個(gè)層面：一是根據(jù)目標(biāo)函數(shù)從一個(gè)給定的基庫中挑選好的或最好的基；二是從這個(gè)好的基中挑選最好的K項(xiàng)組合。從過完備字典的構(gòu)成角度來講，文獻(xiàn)[38]中提出使用局部Cosine基來刻畫聲音信號(hào)的局部頻域特性；利用bandlet基來刻畫圖像中的幾何邊緣。還可以把其它的具有不同形狀的基函數(shù)歸入字典，如適合刻畫紋理的Gabor基、適合刻畫輪廓的Curvelet基等等。從稀疏分解算法角度來講，在音視頻信號(hào)處理方面，基于貪婪迭代思想的MP算法表現(xiàn)出極大的優(yōu)越性，但不是全局最優(yōu)解。Donoho等人另辟蹊徑，提出了BP算法。BP算法具有全局最優(yōu)的優(yōu)點(diǎn)，但計(jì)算復(fù)雜度極高，例如對(duì)于長度為8192的信號(hào)，采用小波字典分解，等價(jià)于求解一個(gè)長度為8192*212992的線性規(guī)劃。MP算法雖然收斂速度較BP快，但不具備全局最優(yōu)性，且計(jì)算復(fù)雜度仍然很大。之后又出現(xiàn)了一系列同樣基于貪婪迭代思想的改進(jìn)算法，如正交匹配追蹤算法（OMP），樹形匹配追蹤（TMP），分段匹配追蹤（StOMP）算法等。 觀測矩陣設(shè)計(jì)觀測部分的設(shè)計(jì)其實(shí)就是設(shè)計(jì)高效的觀測矩陣，換句話說，就是要設(shè)計(jì)一個(gè)能捕捉稀疏信號(hào)中有用信息的高效的觀測（即采樣）協(xié)議，從而將該稀疏信號(hào)壓縮成少量的數(shù)據(jù)。這些協(xié)議是非自適應(yīng)的，僅僅需要用少量的固定波形和原信號(hào)聯(lián)系起來，這些固定波形和為信號(hào)提供簡潔表示的基不相關(guān)。此外，觀測過程獨(dú)立于信號(hào)本身。進(jìn)一步講，使用優(yōu)化方法可以收集到的少量的觀測值中重構(gòu)信號(hào)。壓縮感知理論中，通過變換得到信號(hào)的稀疏系數(shù)向量后，需要設(shè)計(jì)觀測部分，它圍繞觀測矩陣展開。觀測器的設(shè)計(jì)目的是如何采樣得到M個(gè)觀測值，并保證從中能重構(gòu)出長度為N的信號(hào)X或者基下等價(jià)的稀疏系數(shù)向量。顯然，如果觀測過程破壞了X中的信息，重構(gòu)是不可能的。觀測過程實(shí)際就是利用觀測矩陣的M個(gè)行向量對(duì)稀疏系數(shù)向量進(jìn)行投影，即計(jì)算和各個(gè)觀測向量之間的內(nèi)積，得到M個(gè)觀測值，記觀測向量，即 （）（b）（a） 觀測矩陣的圖形表示（a）是（）的形象描述。這里，采樣過程是非自適應(yīng)的，也就是說，無須根據(jù)信號(hào)X 而變化，觀測的不再是信號(hào)的點(diǎn)采樣而是信號(hào)的更一般的線性泛函。（a）隨機(jī)高斯矩陣作為觀測矩陣，稀疏域選擇DCT變換域，對(duì)信號(hào)X進(jìn)行DCT變換后再進(jìn)行觀測。（b）是（a）圖的另一種表達(dá)，變換后的系數(shù)向量是稀疏的，K=3，觀測得到的Y是非零系數(shù)對(duì)應(yīng)的四個(gè)列向量的線性組合。對(duì)于給定的Y從（）中求出是一個(gè)線性規(guī)劃問題，但由于M N，即方程的個(gè)數(shù)少于未知數(shù)的個(gè)數(shù)，這一欠定問題一般來講無確定解。然而，如果具有K 項(xiàng)稀疏性（KM），則該問題有望求出確定解。此時(shí)，只要設(shè)法確定出中的K個(gè)非零系數(shù)的合適位置，由于觀測向量Y是這些非零系數(shù)對(duì)應(yīng)的K個(gè)列向量的線性組合，從而可以形成一個(gè)的線性方程組來求解這些非零項(xiàng)的具體值。對(duì)此，有限等距性質(zhì)（restricted isometry property， RIP）給出了存在確定解的充要條件。這個(gè)充要條件和Cand232。s、Tao等人提出的稀疏信號(hào)在觀測矩陣作用下必須保持的幾何性質(zhì)相一致。即，要想使信號(hào)完全重構(gòu)，必須保證觀測矩陣不會(huì)把兩個(gè)不同的K項(xiàng)稀疏信號(hào)映射到同一個(gè)采樣集合中，這就要求從觀測矩陣中抽取的每M個(gè)列向量構(gòu)成的矩陣是非奇異的。從中可以看出，問題的關(guān)鍵是如何確定非零系數(shù)的位置來構(gòu)造出一個(gè)可解的線性方程組。然而，判斷給定的是否具有RIP性質(zhì)是一個(gè)組合復(fù)雜度問題。為了降低問題的復(fù)雜度，能否找到一種易于實(shí)現(xiàn)RIP條件的替代方法成為構(gòu)造觀測矩陣F 的關(guān)鍵。文獻(xiàn)[24]指出如果保證觀測矩陣和稀疏基不相干，則在很大概率上滿足RIP性質(zhì)。不相干是指向量不能用稀疏表示。不相干性越強(qiáng)，互相表示時(shí)所需的系數(shù)越多；反之，相關(guān)性則越強(qiáng)。通過選擇高斯隨機(jī)矩陣作為即可高概率保證不相干性和RIP性質(zhì)。例如，可以生成多個(gè)零均值、方差為1/ N 的隨機(jī)高斯函數(shù)，將它們作為觀測矩陣的元素，使得以很高的概率具有RIP性質(zhì)。隨機(jī)高斯矩陣具有一個(gè)有用的性質(zhì)：對(duì)于一個(gè)的隨機(jī)高斯矩陣，可以證明當(dāng)時(shí)在很大概率下具有RIP性質(zhì)（其中c是一個(gè)很小的常數(shù)）。因此可以從M個(gè)觀測值中以很高的概率去恢復(fù)長度為N的K項(xiàng)稀疏信號(hào)?？傊S機(jī)高斯矩陣與大多數(shù)固定正交基構(gòu)成的矩陣不相關(guān)，這一特性決定了選它作為觀測矩陣，其它正交基作為稀疏變換基時(shí)，滿足RIP性質(zhì)。為進(jìn)一步簡化觀測矩陣，在某些條件下，以隨機(jī)為元素構(gòu)成的Rademacher矩陣也可以證明具有RIP性質(zhì)和普適性。 目前，對(duì)觀測矩陣的研究是壓縮感知理論的一個(gè)重要方面。在該理論中，對(duì)觀測矩陣的約束是比較寬松的，Donoho在文獻(xiàn)[23]中給出了觀測矩陣所必需具備的三個(gè)條件，并指出大部分一致分布的隨機(jī)矩陣都具備這三個(gè)條件，均可作為觀測矩陣，如：部分Fourier集、部分Hadamard集、一致分布的隨機(jī)投影（uniform Random Projection）集等，這與對(duì)RIP條件進(jìn)行研究得出的結(jié)論相一致。但是，使用上述各種觀測矩陣進(jìn)行觀測后，都僅僅能保證以很高的概率去恢復(fù)信號(hào)，而不能保證百分之百地精確重構(gòu)信號(hào)。對(duì)于任何穩(wěn)定的重構(gòu)算法是否存在一個(gè)真實(shí)的確定性的觀測矩陣仍是一個(gè)有待研究的問題。文獻(xiàn)[56]則從信息論角度描述了信息論與CS之間的聯(lián)系。它指出，在模擬系統(tǒng)中，觀測噪聲也是影響觀測次數(shù)的重要因素，為說明這一點(diǎn)，作者從信息論的角度研究了稀疏信號(hào)的率失真函數(shù)，給出了觀測噪聲對(duì)信號(hào)重建效果的影響。 稀疏信號(hào)的重構(gòu)壓縮感知理論的核心問題是從觀測得到的有限的MN個(gè)觀測樣本中重構(gòu)出N長的原信號(hào)，即未知量個(gè)數(shù)比觀測量要多得多。由于觀測數(shù)量M 遠(yuǎn)小于信號(hào)長度N，因此不得不面對(duì)求解欠定方程組的問題，需要列舉出空間的個(gè)稀疏空間，在計(jì)算上是相當(dāng)復(fù)雜的。乍一看，我們幾乎不可能期望從Y 恢復(fù)每個(gè)。然而，文獻(xiàn)[2326，28]的近期研究結(jié)果表明如果信號(hào)X 是稀疏的，那么（1）精確恢復(fù)是可能的；（2）真實(shí)信號(hào)實(shí)際上就是一個(gè)簡單凸優(yōu)化問題的解。但是，文獻(xiàn)[30]和[23]均指出由于信號(hào)X 是稀疏的或可壓縮的，這個(gè)前提從根本上改變了問題，使得問題可解，而觀測矩陣具有RIP性質(zhì)也為從M 個(gè)觀測值中精確恢復(fù)信號(hào)提供了理論保證。為更清晰地描述壓縮感知理論的信號(hào)重構(gòu)問題， 首先定義向量的p范數(shù)為 （）當(dāng)p=0時(shí)得到0范數(shù)，它實(shí)際上表示X中非零項(xiàng)的個(gè)數(shù)。在信號(hào)X 稀疏或可壓縮的前提下，求解欠定方程組的問題轉(zhuǎn)化為最小0范數(shù)問題： . （） 但是，它需要列出X中所有非零項(xiàng)位置的種可能的線性組合，才能得到最優(yōu)解。因此，求解（）式的數(shù)值計(jì)算極不穩(wěn)定而且是NP難問題?？梢?，壓縮感知和稀疏分解問題從數(shù)學(xué)意義上講是同樣的優(yōu)化問題。于是稀疏分解的已有算法可以應(yīng)用到CS重構(gòu)中。Chen，Donoho和Saunders指出，求解一個(gè)更加簡單的1范數(shù)最小優(yōu)化問題會(huì)產(chǎn)生同等的解（要求和不相關(guān)）： . （）稍微的差別使得問題變成了一個(gè)凸優(yōu)化問題，于是可以方便地化簡為線性規(guī)劃問題，典型算法代表：BP算法。不過，1范數(shù)最小化不是尋找稀疏解的唯一方法；其它方法，例如貪婪算法也已被提出。由以上討論我們可以得出結(jié)論：（1）相關(guān)性在CS中起著至關(guān)重要的作用：和相關(guān)性越小，需要采樣的數(shù)目就越少。（2）僅僅觀測比信號(hào)長度小得多的任何M 個(gè)系數(shù)的集合，不會(huì)損失信息。（3）最小化帶線性方程約束的1范數(shù)可以很容易地被轉(zhuǎn)化為線性規(guī)劃問題，于是可以找到更高效的求解算法。已經(jīng)證明，如果，那么重構(gòu)成功的概率超過。 重構(gòu)算法由前面的分析可知，過完備庫下的稀疏分解問題和壓縮感知理論的重構(gòu)問題都是線性約束下的0范數(shù)求解問題。因此這兩類問題的求解本質(zhì)上是一樣的。于是用于過完備庫下稀疏分解的方法都可以用于求解壓縮感知理論的重構(gòu)計(jì)算。定理2已證明：對(duì)于一個(gè)K項(xiàng)稀疏（KN）長度為N的信號(hào)僅僅需要投影到另一個(gè)不相關(guān)基上的K+1個(gè)系數(shù)就可以以高概率被重構(gòu)。然而，求得最小的0范數(shù)解需要進(jìn)行組合搜索，計(jì)算復(fù)雜度相當(dāng)高。Cand232。s 和Donoho 近來提出一種可行的基于線性規(guī)劃的重構(gòu)方法，論證了只使用對(duì)信號(hào)的cK（c =3或者4）個(gè)觀測值，利用線性規(guī)劃的方法就可以得到和