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

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

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

格地表述這一定理 1949年信息論的創始人香農對該定理加以明確

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

獻中又稱為香農采樣定理HarryNyquist

ClaudeShannon

插值重建數字信號的獲取----Nyquist-Shannon采樣定理信號采樣非帶限信號香農定理的數學表示香農采樣定理后采樣理論的發展Nyquist-Shannon采樣定理局限性問題1:真實信號沒有真正帶限的；問題2:理想的低通濾波器不存在；獲取的大量數字信號為處理、存儲、傳輸的軟硬件增加了很多負擔高分辨率大量的傳感器圖像數據庫，照相陣列，分布式無線傳感網越來越多的成像形式X-Ray，GammaRay,PET，MRI,紅外，超聲波，毫米波SAR成像海量的數據問題3:當信號的帶寬過寬時，采樣率過高難于實現

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

ECandes（加州理工大學）

D.Donoho(斯坦福大學)

（Ridgelet和Curvelet的創始人）

一種新的采樣方法

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

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

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

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

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

病態問題求解：用規整化（Regularization）理論處理病態問題目的是修改一個病態問題為一個良態問題，使得問題的解在物理上合理，并且解連續依賴于數據。基本思想是利用關于解的先驗知識，構造附加約束或改變求解策略，使得逆問題的解變得確定且穩定。即對解進行約束J(x)約束信號x為平滑的應用Lagrange乘子，將P2問題約束轉換為無約束問題

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

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

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

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

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

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

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

根據信號x的先驗知識，可以設計規整化項為

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

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

2.3測量離散時間不確定準則（DiscreteTimeUncertaintyPrinciple）注：集的勢：集合元素的個數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.信號表示越稀疏、兩組基之間的互相干性越小，所需

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

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

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

Principle,UUP）

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

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

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

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

P1問題的唯一解

稱A有則A具有k階零空間性質

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

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

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

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

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

OMP算法步驟

t=t+1;5：如果

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

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

線性規劃問題解的概念：

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

可行解集稱為線性規劃問題的可行域。

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

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

基向量，基變量

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

稱為基向量，

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

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

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

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

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

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

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

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

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

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

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

中非空凸集，若對,

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

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

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

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

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

定理：設f：具有二階連續偏導數。則：

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

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

如果算法構造出的點列{xk}在有限步之內得到問題的最優解x*

，或者點列{xk}有極限點，并且其極限點是最優解

x*

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

如果只有當

x0充分接近最優解

x*時，由算法產生的點列才收斂于

x*

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

如果對于任意初始點

x0

，由算法產生的點列都收斂于最優解

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

負梯度方向使目標函數

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

在相繼兩次迭代中，搜索方向是相互正交的。可見，最速下降法逼近極小點的路線是鋸齒形的，而且越靠近極小點步長越小，即越走越慢。

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

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

的解等價于求二次泛函

f(x)

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

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

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

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

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

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

其中

，可行域記為，

，，是上的連續函數。

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

s.t

構造一個函數：

將

作為t，顯然當

時，

，

當

時，

構造函數：

求解無約束問題

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

這就是說

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

上述函數的函數性態不好，它在t=0點不連續，也沒有導數。希望構造出一個在任意點t處函數及其導數都連續的輔助函數。可選擇如下的函數：

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

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

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

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

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

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

以為初始點，選擇適當的方法求解，得其極小點。

第3步：判斷精度。

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

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

s.t

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

3.2.2內點法

與外點法不同，內點法要求整個迭代過程始終在可行域內部進行，初始點是一個嚴格的內點，再在可行域邊界上設置一道“障礙”，以阻止搜索點到可行域邊界上去。構造障礙函數（取倒數或對數函數）：

或

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

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

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

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

3.3.1

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

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

2.一般問題的近似模型

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