壓縮感知理論及應用(附重建算法詳述)

壓縮感知理論與應用Compressedsensing:theoremandApplications一.壓縮感知背景知識二.壓縮感知理論三.壓縮感知重建方法四.壓縮感知應用內(nèi)容概覽一.壓縮感知背景知識Nyquist-Shannon采樣定理

1928年由美國電信工程師H.奈奎斯特首先提出 1933年由蘇聯(lián)工程師科捷利尼科夫首次用公式嚴

格地表述這一定理 1949年信息論的創(chuàng)始人香農(nóng)對該定理加以明確

地說明并正式作為定理引用，因此在許多文

獻中又稱為香農(nóng)采樣定理HarryNyquist

ClaudeShannon

插值重建數(shù)字信號的獲取----Nyquist-Shannon采樣定理信號采樣非帶限信號香農(nóng)定理的數(shù)學表示香農(nóng)采樣定理后采樣理論的發(fā)展Nyquist-Shannon采樣定理局限性問題1:真實信號沒有真正帶限的；問題2:理想的低通濾波器不存在；獲取的大量數(shù)字信號為處理、存儲、傳輸?shù)能浻布黾恿撕芏嘭摀叻直媛蚀罅康膫鞲衅鲌D像數(shù)據(jù)庫，照相陣列，分布式無線傳感網(wǎng)越來越多的成像形式X-Ray，GammaRay,PET，MRI,紅外，超聲波，毫米波SAR成像海量的數(shù)據(jù)問題3:當信號的帶寬過寬時，采樣率過高難于實現(xiàn)

限制了超寬帶通信和超寬帶雷達的發(fā)展；限制醫(yī)學圖像成像的發(fā)展，比如MRI；等等。多種成像形式采樣壓縮傳輸/存儲NK小波系數(shù)局部放大大量采樣數(shù)據(jù)有無必要性？1M25K項系數(shù)近似原始圖像近似后的圖像2004~2006，

ECandes（加州理工大學）

D.Donoho(斯坦福大學)

（Ridgelet和Curvelet的創(chuàng)始人）

一種新的采樣方法

以不確定準則為基礎Romberg(佐治亞理工大學)

Tao（加州大學洛杉磯分校）CS提出者用更一般的測量值代替信號樣本值壓縮感知或壓縮采樣直接獲取壓縮后的信號；壓縮采樣傳輸/存儲NM接收重建二.壓縮感知理論2.1壓縮感知問題描述

三種線性方程組根據(jù)變量個數(shù)和方程個數(shù)來確定是欠定、適定還是超定方程組欠定方程組，無窮多解適定方程組，有唯一解超定方程組，無解良態(tài)問題1923年Hadamard提出了良態(tài)問題（Well-posedproblem）的概念，根據(jù)其定義，如果下述條件滿足，稱為良態(tài)問題（1）方程的解是存在的；（2）解是唯一的；（3）解連續(xù)地依賴于數(shù)據(jù)（觀測矩陣或數(shù)據(jù)微小變化導致解很大變動）病態(tài)問題

如果良態(tài)問題的三個條件任意一個不能滿足，就稱問題是病態(tài)的（ill-posedproblem）

良態(tài)與病態(tài)問題：病態(tài)問題舉例系數(shù)矩陣A或者觀測項(常數(shù)項)y的微小變化引起解的巨大變化,該問題為病態(tài)問題

病態(tài)問題求解：用規(guī)整化（Regularization）理論處理病態(tài)問題目的是修改一個病態(tài)問題為一個良態(tài)問題，使得問題的解在物理上合理，并且解連續(xù)依賴于數(shù)據(jù)?；舅枷胧抢藐P于解的先驗知識，構(gòu)造附加約束或改變求解策略，使得逆問題的解變得確定且穩(wěn)定。即對解進行約束J(x)約束信號x為平滑的應用Lagrange乘子，將P2問題約束轉(zhuǎn)換為無約束問題

2.如何設計測量矩陣，讓其作用于信號后

能保持信號的所有信息不丟失？

（對應于香農(nóng)采樣定理中對采樣率的要求）3.如何從測量中重建原信號？

（對應依據(jù)香農(nóng)采樣定理采樣后內(nèi)插實現(xiàn)重建）信號應滿足什么要求，方可重建？（對應香農(nóng)采樣定理中對信號的帶寬要求）CS關注的問題信號表示將信號表示為一組正交基的線性組合

如果合理選擇基底，處理系數(shù)序列比直接處理信號簡單；如果系數(shù)序列具有稀疏結(jié)構(gòu)，可以從實質(zhì)上降低信號處理的成本，提高壓縮效率。二.壓縮采樣理論2.2信號的稀疏與可壓縮性信號的稀疏（Sparsity）與可壓縮性(Compressibility)光滑信號其Fourier變換,Wavelet變換系數(shù)呈現(xiàn)冪次衰減趨勢其全變差（TotalVariation）呈現(xiàn)冪次衰減趨勢有界變差函數(shù)

給定一個定義于有界開集Ω上的可微函數(shù)f，其全變差（thetotalvariation）

為對于圖像x而言，其TV范數(shù)為Cameraman原圖4層小波分解傅里葉幅頻MRI圖像4層小波分解傅里葉幅頻原圖垂直水平全變差

根據(jù)信號x的先驗知識，可以設計規(guī)整化項為

R2空間，一維子空間用lp范數(shù)進行約束的解2.3.1不確定原理（測不準原理

UncertaintyPrinciple,UP）物理學中經(jīng)典的測不準原理兩個共軛的物理量，如微觀粒子的位置和動量，不能同時測準，其中一個量越確定，另一個量的不確定程度就越大

2.3測量離散時間不確定準則（DiscreteTimeUncertaintyPrinciple）注：集的勢：集合元素的個數(shù)2.3.2部分Fourier變換已知的信號重建與RobustUncertaintyPrinciplesCS提出的最初研究：2004年，EmmanuelCandes,JustinRomberg和TerenceTao對以下問題進行了研究MRI圖像Fourier采樣，22線Fourier幅度M>=logN.S定理與UP的關系，以及RUP（RobustUncertaintyPrinciple）2.3.3隨機采樣與重建

定義2.1互相干

互

定理2.3

幾點說明：2.信號表示越稀疏、兩組基之間的互相干性越小，所需

要的樣本數(shù)就越少3.常用的測量矩陣有高斯和伯努利分布，因為其與

大多數(shù)的稀疏表示基相干性小。測量結(jié)果稀疏信號x隨機投影（測量）矩陣壓縮采樣的情況1:信號本身稀疏

信號是時域稀疏的，頻域測量結(jié)果含有信號的所有信息；信號測量原信號M=50；S=19；N=100重建信號時域信號頻域1-維信號信號是頻域稀疏的，時域測量結(jié)果；壓縮采樣的情況2信號可以用一組基稀疏表示2-維圖像信號2.3.4一致不確定準則（UniformUncertainty

Principle,UUP）

嚴格重建準則（ExactReconstructionPrinciple,ERP）可壓縮信號（近似稀疏信號）的重建（P1）

定理2.4保證信號不在測量的零空間，信號的范數(shù)近似保持定義2.3

定理2.5定理2.62.3.6魯棒測量定理2.9測量A的零空間如果想從測量中重建所有的稀疏信號x，則對任意一對不同的信號x和x’，必然有Ax與Ax’。如果來觀測Ax=Ax’，則得到x-x’是2K稀疏的，因此，A能唯一表示所有，則中不能含有的向量。有許多方式可以表征這種性質(zhì)，其中之一為A的Spark定義Spark：一給定矩陣A的Spark是其最少的線性相關列的個數(shù)。

2.3.7最小化問題的唯一解P0問題的唯一解

P1問題的唯一解

稱A有則A具有k階零空間性質(zhì)

MRI圖像Fourier采樣，22線令能量最小，未采樣的Fourier系數(shù)置0CS重建，令圖像的TV范數(shù)最小

利用計算機解決實際問題，通常要按以下步驟進行：（1）建立數(shù)學模型，即把實際問題抽象為一個數(shù)學問題，可以是一個方程組、一個函數(shù)、一個微分方程等。

（2）選擇數(shù)值方法，要考慮所能達到的精度，計算量，方法對數(shù)據(jù)微小擾動的靈敏度。

（3）編寫程序，上機計算。第二部分CS中的信號重建兩類主要方法：一、貪婪搜索（MatchedPursuit,匹配追蹤）二、基追蹤（BasisPursuit，基追蹤）

稱為基追蹤問題，（BasisPursuit，BP）匹配追蹤（MatchedPursuit，MP）一、匹配追蹤（MatchedPursuit，簡稱MP）MP算法的步驟正交匹配追蹤（OrthogonalMatchedPursuit，簡稱OMP）

OMP算法步驟

t=t+1;5：如果

t>S,則停止迭代，否則重復步驟1體現(xiàn)正交思想由多元函數(shù)的微分學知，上式的解一定是駐點線性規(guī)劃問題的標準形式s.t.其中為M×N階矩陣

二、基追蹤問題（BP）約束條件以及目標函數(shù)都是決策變量的線性函數(shù)的規(guī)劃問題稱為線性規(guī)劃(LinearProgramming)s.t.

線性規(guī)劃問題解的概念：

(1)可行解。滿足約束條件的解

可行解集稱為線性規(guī)劃問題的可行域。

(2)最優(yōu)解。使目標函數(shù)達到最優(yōu)值的可行解稱為最優(yōu)解，最優(yōu)解常用表示。

(3)基。若Ｂ是Ａ中M×M階非奇異矩陣，即|Ｂ|≠0，則稱Ｂ是線性規(guī)劃問題的一個基。s.t.

基向量，基變量

若Ｂ是線性規(guī)劃問題的一個基，那么Ｂ一定是由M個線性無關的列向量組成，不失一般性，可設

稱為基向量，

與基向量相對應的變量稱為基變量。

基的個數(shù)一個線性規(guī)劃的基通常不是唯一的，但是基的個數(shù)也不會超過個。一旦線性規(guī)劃的基確定了，那么相應的基向量、基變量和非基變量也就確定了。(4)基本解。設B是線性規(guī)劃的一個基，若令n-m個非基變量等于0，則所得的方程組ＡＸ=b的解稱為線性規(guī)劃問題的一個基本解（簡稱基解）。有一個基就可以求得一個基本解。由基的有限性可知，基本解的個數(shù)也不會超過個。由于基本解中的非零分量可能是負數(shù)，所以基本解不一定是可行的。(5)基本可行解。滿足非負條件的基本解稱為基本可行解（簡稱基可行解）。與基本可行解對應的基稱為可行基?；究尚薪獾姆橇阆蛄康膫€數(shù)小于等于m，并且都是非負的。由于基本可行解的數(shù)目一般少于基本解的數(shù)目，因此可行基的數(shù)目也要少于基的數(shù)目。

當基本可行解中有一個或多個基變量是取零值時，稱此解為

退化的基本可行解。可行解

基本解求解線性規(guī)劃：圖解法單純形法內(nèi)點算法70單純形法的一般步驟如下：（1）尋找一個初始的基本可行解。（2）檢查現(xiàn)行的基本可行解是否最優(yōu)，如果為最優(yōu)，則停止迭代，已找到最優(yōu)解，否則轉(zhuǎn)一步。（3）移至目標函數(shù)值有所改善的另一個基本可行解，然后轉(zhuǎn)回到步驟（2）。

其基本思路是從一個初始的基本可行解出發(fā)，尋找一條達到最優(yōu)基本可行解的最佳途徑。

1947年，Dantzig提出的單純形法把尋優(yōu)的目標集中在所有基本可行解（即可行域頂點）中。單純形法Lasso問題

s.t.BPDN（BasisPursuitDenoising）BP（BasisPursuit）s.t.(1)約束問題(2)約束問題問題(2)的解要么是x=0,要么是問題(3)的解,因此說BPDN問題與LASSO等價(3)無約束問題3.1無約束最優(yōu)化方法無約束問題定義：設函數(shù)f(x)存在一階偏導數(shù)，x∈Rn

，向量?)(xf=Tnxfxfxf????è???????,,,21為f(x)在點x處的梯度。…定義設函數(shù)存在二階偏導數(shù)，x∈R，則稱矩陣)(xfnúúúúúúúú?ùêêêêêêêê?é????????????????????????2222122222212212212212nnnnnxfxxfxxfxxfxfxxfxxfxxfxfLLL為在點x處的Hesse矩陣。)(xf)(2xf?=………三、BPDN問題定理:(一階必要條件）

凸集和凸函數(shù)在非線性規(guī)劃的理論中具有重要作用，下面給出凸集和凸函數(shù)的一些基本知識。設，若對D中任意兩點，連接的線段仍屬于D；換言之，對,

則稱D為凸集。稱為的凸組合。定義:凸集對凸的一元函數(shù)的幾何意義為：在曲線上任取兩點P1(x1,),P2(x2,)弦位于弧之上（見圖）。)(xf)(1xf(x2)f21PP21PPx1x2x(x,y)p1p2)(xf設D為RN

中非空凸集，若對,

恒有則稱f(x)為D上的凸函數(shù)；進一步，若時，上式僅〝<〞成立,則稱f(x)為D上嚴格凸函數(shù)。定義:凸函數(shù)定義:凸規(guī)劃設D為RN

中非空凸集，f(x)是定義在D上的凸函數(shù)，則稱規(guī)劃問題為凸規(guī)劃。若規(guī)劃???íì===ljhmigtsfji,,2,1,0)(,,2,1,0)(..)(minxxx……中,和

為凸函數(shù),是線性函數(shù),則上述問題為凸規(guī)劃。)(xf)(xig)(xih

凸規(guī)劃是非線性規(guī)劃中的一種重要特殊情形，它具有很好的性質(zhì)。定理:(1)凸規(guī)劃的任意局部極小點就是整體極小點，且極小點集合是凸集。

(2)如果凸規(guī)劃的目標函數(shù)是嚴格凸函數(shù)，又存在極小點，則它的極小點還是唯一的。多數(shù)問題由條件得到的是一個非線性方程組，求解非常困難，甚至無法得到解析解，因此求解非線性規(guī)劃問題一般都采用數(shù)值計算的迭代方法。即從已知點出發(fā)，按照某種算法產(chǎn)生后繼點，形成點列非線性規(guī)劃迭代方法的基本思想是：要求迭代所采用的算法，使得當是有窮點列時，其最后一點是該問題的最優(yōu)解；當為無窮點列時，有極限點，并且該極限點是問題的最優(yōu)解。

定理：設f：具有二階連續(xù)偏導數(shù)。則：

Taylor展開式還可寫成如下形式：

多元函數(shù)的Taylor展開公式其中算法的收斂性

如果算法構(gòu)造出的點列{xk}在有限步之內(nèi)得到問題的最優(yōu)解x*

，或者點列{xk}有極限點，并且其極限點是最優(yōu)解

x*

，則稱這種算法是收斂的。

如果只有當

x0充分接近最優(yōu)解

x*時，由算法產(chǎn)生的點列才收斂于

x*

，則該算法稱為局部收斂。

如果對于任意初始點

x0

，由算法產(chǎn)生的點列都收斂于最優(yōu)解

，則這個算法稱為全局收斂?？紤]問題式中函數(shù)具有一階連續(xù)偏導數(shù)，具有極小點若現(xiàn)在已求得的第k次近似值，為求得第k+1次近似值，需要選定方向p將f(x)在xk處進行一階泰勒展開，得到如果忽略高階無窮小項，因為3.1.1最速下降法有說明搜索方向應該與梯度的點積小于0,因為說明夾角為180o時目標函數(shù)下降最快，稱為負梯度方向

負梯度方向使目標函數(shù)

下降最快，又稱之為最速下降方向。算法：最速下降法

在相繼兩次迭代中，搜索方向是相互正交的?？梢姡钏傧陆捣ū平鼧O小點的路線是鋸齒形的，而且越靠近極小點步長越小，即越走越慢。

最速下降法具有整體收斂性，但由于其收斂速度慢，所以它不是好的實用算法。然而一些有效算法是通過對它進行改進或利用它與其他收斂快的算法相結(jié)合而得到的。是基本算法之一。3.1.2牛頓法(Newton)算法：牛頓法

牛頓法的優(yōu)缺點3.1.3共軛梯度法(ConjugateGradient)1.共軛方向及其性質(zhì)定理：設矩陣A為對稱正定，求解方程組

的解等價于求二次泛函

f(x)

的極小點共軛梯度法的基本思想是

在共軛方向法和最速下降法之間建立某種聯(lián)系，為了節(jié)省存儲單元和計算量，在迭代過程中逐步形成共軛方向。即用迭代點處的負梯度向量為基礎產(chǎn)生一組共軛方向的方法，叫做共軛梯度法。下面具體介紹對于正定二次函數(shù)規(guī)劃問題的共軛梯度法

共軛梯度法特點是介于最速下降法與牛頓法之間的一個方法，它僅需利用一階導數(shù)信息，但克服了最速下降法收斂慢的缺點，又避免了牛頓法需要存儲和計算Hesse矩陣并求逆的缺點，共軛梯度法不僅是解決大型線性方程組最有用的方法之一，也是解大型非線性最優(yōu)化最有效的算法之一。在各種優(yōu)化算法中，共軛梯度法是非常重要的一種。

CG是一個典型的共軛方向法，它的每一個搜索方向是互相共軛的，而這些搜索方向僅僅是負梯度方向與上一次迭代的搜索方向的組合，因此，存儲量少，計算方便所需存儲量小，穩(wěn)定性高，而且不需要任何外來參數(shù)。用共軛梯度法求得的

有如下的誤差估計其中PCG（PreconditionedConjugateGradient）

當矩陣A僅有少數(shù)幾個互不相同的特征值或者非常良態(tài)時，共軛梯度法就會收斂的非常之快。當矩陣A是病態(tài)的，想辦法將其轉(zhuǎn)化為一個良態(tài)的等價方程組，然后再應用共軛梯度法于轉(zhuǎn)化后的方程組其中，這里的C對陣正定，目的是通過選擇C，使得是良態(tài)的，然后再應用CG算法考慮約束非線性規(guī)劃問題

其中

，可行域記為，

，，是上的連續(xù)函數(shù)。

基本思想有，構(gòu)造廣義拉格朗日函數(shù)，懲罰范數(shù)使得約束問題轉(zhuǎn)換為無約束問題；將非線性問題線性化，然后通過解線性規(guī)劃問題求原問題的解等；3.2約束問題求解定義（1）式的廣義拉格朗日函數(shù)為則存在向量，（此條件叫Kuhn-Tucker約束規(guī)范）3.2.1外點法構(gòu)造一個由目標函數(shù)與約束函數(shù)組成的懲罰函數(shù)，對懲罰函數(shù)實行極小化。先考慮只含有不等式約束的問題：

s.t

構(gòu)造一個函數(shù)：

將

作為t，顯然當

時，

，

當

時，

構(gòu)造函數(shù)：

求解無約束問題

若(5)式問題有解，設其最優(yōu)解為，則由(3)式和(4)式應有：

這就是說

因此不僅是問題(5)式的極小解，也是問題(2)式的極小解。因此將問題(2)式的求解化為無約束問題(5)式的求解。

上述函數(shù)的函數(shù)性態(tài)不好，它在t=0點不連續(xù)，也沒有導數(shù)。希望構(gòu)造出一個在任意點t處函數(shù)及其導數(shù)都連續(xù)的輔助函數(shù)?？蛇x擇如下的函數(shù)：

函數(shù)(6)式在t為任意值時，與都連續(xù)，且當時仍有

當時為了使輔助函數(shù)能更快地滿足要求，將引入一個充分大的正數(shù)M(>0)，修改為

求解問題(5)式就變?yōu)榍蠼鉄o約束問題(8)式稱函數(shù)為懲罰函數(shù)（或罰函數(shù)），其中第二項為懲罰項。稱M為罰因子。懲罰函數(shù)只對不滿足約束條件的點實行懲罰。當

時，滿足各個，故罰項等于0，不受懲罰；當時，必有，故罰項>0，對極小化罰函數(shù)的問題，就要受懲罰。在實際計算中，罰因子M的值選得過小或過大都不好。如果選得過小，則罰函數(shù)的極小點遠離約束問題的最優(yōu)解，計算效率很差；如果M過大，則給罰函數(shù)的極小化增加計算上的困難。因此，一般策略是取一個趨向無窮大的嚴格遞增正數(shù)列，從某個

開始，對每個求解：當趨向于正無窮大時，點列就從可行域外部趨于原問題的極小點，“外點法”正是因此而得名第1步：給定初始點，初始罰因子（例如），放大系數(shù)（如取或10），允許誤差。令。

第2步：求解罰函數(shù)的無約束極小化問題。

以為初始點，選擇適當?shù)姆椒ㄇ蠼?，得其極小點。

第3步：判斷精度。

在點，若罰項，則停止計算，得到原問題的近似極小點；否則令，置

，返回第2步。外點法考慮非線性規(guī)劃

s.t

記為可行域內(nèi)部。即是可行域中所有嚴格內(nèi)點（即不包括可行域邊界上的點）的集合。

3.2.2內(nèi)點法

與外點法不同，內(nèi)點法要求整個迭代過程始終在可行域內(nèi)部進行，初始點是一個嚴格的內(nèi)點，再在可行域邊界上設置一道“障礙”，以阻止搜索點到可行域邊界上去。構(gòu)造障礙函數(shù)（取倒數(shù)或?qū)?shù)函數(shù)）：

或

其中是很小的正數(shù)，通常稱為障礙因子，稱或為障礙項。

障礙函數(shù)應具備的功能：可行域內(nèi)部或離邊界較遠處，障礙函數(shù)與原目標函數(shù)盡可能接近，而在邊界上時，應變成很大的值，因此滿足該要求的障礙函數(shù)其極小值不會在可行域的邊界上達到。內(nèi)點法計算步驟第1步：給定嚴格內(nèi)點為初始點，初始障礙因子（如?。s小系數(shù)（如取或0.2），允許誤差，置。第2步：構(gòu)造障礙函數(shù)，障礙函數(shù)可取(14)式形式，也可取(15)式形式。第3步：求解障礙函數(shù)的無約束極小化問題。以為初始點，求解

得其極小點。是可行域中所有嚴格內(nèi)點的集合。第4步：判斷精度。

若收斂準則得到滿足，則迭代停止，取作為原問題極小點的近似值。否則取，置，轉(zhuǎn)第3步。內(nèi)點法的優(yōu)缺點優(yōu)點：由于迭代總是在可行域內(nèi)進行，每一個中間結(jié)果都是可行解，可以作為近似解。缺點：選取初始可行點較困難，且只適用于含有不等式約束的非線性規(guī)劃問題。3.3其他算法

3.3.1

ISTA(IterativeShrinkage-ThresholdingAlgorithm）1.考慮無約束的最小化連續(xù)可微函數(shù)f(x),解決這個問題的最簡單方法就是用梯度算法產(chǎn)生x序列這個公式可以等價為如下二次形式把這種梯度算法應用到非光滑l1正則化問題中那么x的迭代序列為將公式(5)的第二項和第三項結(jié)合，并去掉常數(shù)項，則公式(5)可表示為

L1范數(shù)是可分離的那么(5)式的計算就簡化為求解一維最小化問題，通過CHAMBOLLE,R.A.DEVORE等人的證明x迭代步驟可以寫成如下形式收縮算子定義為如下形式確保x收斂的關鍵條件是步長的設置

2.一般問題的近似模型

對于任何L>0,F(x)=f(x)+g(x)在y點的二次近似模型為它的唯一最小解為與(5)式同理，忽略掉常數(shù)項的影響，可以表示為前面講的g(x)為l1范數(shù)是這個一般問題的特例那么基本的ISTA步驟即為3.3.2