蔡云 石瑩

摘? 要：壓縮感知問題考慮通過較少的測量值來精確恢復(fù)未知高維稀疏信號，而實際問題中許多信號在標準正交基上不稀疏，但在一組框架表示下是稀疏的。該文首先對框架表示下的稀疏恢復(fù)問題進行闡述，然后系統(tǒng)介紹3個恢復(fù)模型即分析基追蹤模型、分析LASSO模型和分析Danzig模型，并介紹基于D-RIP條件的最新恢復(fù)結(jié)果。

關(guān)鍵詞：稀疏恢復(fù)? 框架? 恢復(fù)模型? D-RIP條件

中圖分類號：O29 ? ?文獻標識碼：A 文章編號：1672-3791（2019）10（a）-0173-02

近年來稀疏信號恢復(fù)問題引起了國內(nèi)外研究者的極大關(guān)注，稀疏恢復(fù)也稱壓縮感知問題，即考慮從較少的觀測數(shù)據(jù)中以高概率精確恢復(fù)未知稀疏信號?，F(xiàn)實中絕大多數(shù)信號都具有一些特殊的規(guī)律如稀疏性，因此稀疏恢復(fù)問題已經(jīng)在許多方面有了廣泛的應(yīng)用，如核磁共振成像（MRI）、雷達、圖像處理、地震勘探、傳感器網(wǎng)絡(luò)設(shè)計和計算生物學等。稀疏恢復(fù)突破了傳統(tǒng)的香農(nóng)采樣定理，即不直接對信號值進行采樣，而是通過信號與測量函數(shù)的內(nèi)積獲得測量值。而且采樣時多使用隨機測量矩陣，然后通過各種優(yōu)化方法來恢復(fù)未知的稀疏信號[1]。因此，稀疏恢復(fù)問題一經(jīng)提出就引起了國內(nèi)外許多研究者們的高度關(guān)注，如菲爾茲獎獲得者T.Tao、美國科學院院士D.Donoho、小波分析理論專家Daubechies和美國科學院院士E.Candes等。同時國內(nèi)許多研究者也高度關(guān)注稀疏恢復(fù)問題，包括應(yīng)用數(shù)學、統(tǒng)計、計算機科學、圖像處理等領(lǐng)域的研究者，發(fā)表了許多重要的研究成果。

1? 經(jīng)典的壓縮感知問題

經(jīng)典的壓縮感知（稀疏恢復(fù)）問題主要考慮下列的恢復(fù)模型：

其中y∈Rm是測量向量，A∈Rm×n（m≤n）是線性測量矩陣，稀疏恢復(fù)的主要任務(wù)是通過觀測數(shù)據(jù)y和A來恢復(fù)未知x。顯然該方程組具有不確定性，也即有許多解。通常假設(shè)x是稀疏的，并假設(shè)測量矩陣具有一些良好的性質(zhì)，這時該線性方程組具有唯一解。當向量x中非零未知分量的個數(shù)最多為k個時，稱信號為k-稀疏信號。

最直接的求解上述線性方程組的方法是求解如下的l0最小化問題，也即l0最小化方法：

其中l(wèi)0范數(shù)定義為向x量的非零元素的個數(shù)。但是直接求解上述l0最小化問題是NP-難的，并且在計算上是不可行的。因此研究者們尋找了很多替代l0最小化方法的求解方法，最直接且簡單的方法是l0最小化方法的凸松弛方法即最l1小化方法，即為求解如下的凸優(yōu)化問題：

其中是向量x的l1范數(shù)。l1最小化問題是凸優(yōu)化問題，并且能用線性規(guī)劃的很多方法求解如半正定法。

研究者們關(guān)注在什么情況下上述兩個問題等價即求得的解相同，文獻中對測量矩陣提出了許多條件，最常用的條件主要有3個：列相干性條件（MIP）、零空間條件（NSP）和約束等距條件（RIP）[1]。其中最簡單常用的條件是RIP條件，定義如下。

定義1[1]：A∈Rm×n對于測量矩陣和正整數(shù)（k≤n），對所有的k-稀疏向量x∈Rn，矩陣A的k階約束等距常數(shù)（RIC）δk定義為滿足如下不等式的最小常數(shù)：

若有上述不等式成立，則稱測量矩陣A滿足k階RIP條件。

注意到RIP條件具有類似于正交矩陣的性質(zhì)，并且對于確定性的矩陣不好判斷是否滿足RIP條件，因此通常采用隨機測量矩陣。文獻表明高斯隨機測量矩陣、次高斯隨機測量矩陣以及部分隨機Fourier測量矩陣等都以大概率滿足RIP條件。有許多研究者們都對RIP條件做了大量的研究。其中，Candes首先指出當測量矩A陣滿足時，l1最小化能準確地恢復(fù)未知k-稀疏信號x。最新的研究結(jié)果是Cai和Zhang給出是最優(yōu)界。具體詳細內(nèi)容可以參見參考文獻[2-5]。

2? 框架表示下的壓縮感知問題

對于在一組標準正交基下稀疏的信號，上述的恢復(fù)方法和恢復(fù)條件是適用的。但是現(xiàn)實中也存在許多信號在標準正交基下不稀疏，但卻在一組框架表示下是稀疏的，也即未知信號f可以表示為f=Dx，其中D∈Rn×d（n≤d）是冗余的框架，x是稀疏或者逼近稀疏的d維向量。這樣的例子有很多，例如陣列信號處理中的信號模型、聲納信號和反射雷達以及圖像曲線等，具體可見文獻[3-4]。

這時線性測量模型y=Af可寫為y=ADx，顯然最直接的方法是可以利用經(jīng)典壓縮感知理論中的恢復(fù)模型先得到最優(yōu)的x*，然后再利用合成算子即f*=Dx*得到未知信號。這種方法稱為l1合成法。顯然該方法直接易懂，但該方法要求滿足經(jīng)典壓縮感知理論中的測量矩陣所滿足的條件如RIP條件，注意到當冗余框架D之間的列相干性較大時，AD一般不滿足經(jīng)典的RIP條件。于是研究者們又開始尋求其他的恢復(fù)模型，比較常用的是l1分析法，該種方法通過求解某個l1最小化問題來直接求解f。

3? 恢復(fù)模型

現(xiàn)實中測量模型通常含有噪聲，如l2范數(shù)有界噪聲、脈沖噪聲，以及Danzig Selector噪聲等。因此測量模型可寫為：

其中是觀測噪聲。最常用的恢復(fù)模型有3個：分析基追蹤（ABP）[4]、分析LASSO模型（ALASSO）和分析Danzig模型（ADS）[3]，分別表示如下：

其中ε、λ是噪音界，μ是調(diào)節(jié)參數(shù)。類似于經(jīng)典的壓縮感知問題，Candes等提出了基于框架下的約束等距條件（D-RIP）來研究框架表示下的壓縮感知問題。具體定義如下，也可見文獻[4]。

定義2（D-RIP）：對于測量矩陣D∈Rn×d和正整數(shù)k≤d，對所有的k-稀疏向量v∈Rd，矩陣的階D-約束等距常數(shù)（D-RIC）δk定義為滿足如下不等式的最小常數(shù)：

若有上述不等式成立，則稱測量A矩陣滿足k階D-RIP條件。

并且Candes等指出高斯以及次高斯隨機測量矩陣以高概率滿足D-RIP條件，而且運用Johnson-Lindenstrauss引理可知，隨機測量矩陣如果滿足經(jīng)典的RIP條件時，該矩陣也以高概率滿足D-RIP條件，因此部分隨機傅立葉測量矩陣以大概率滿足D-RIP條件[4]。利用D-RIP條件，文獻[3]和[4]給出了模型（1）（2）（3）的恢復(fù)結(jié)果，為完整起見，下面以定理形式給出3個模型的恢復(fù)結(jié)果，具體證明可參見文獻[3-4]。

定理1[4]：對恢復(fù)模型（1），當測量矩陣滿足δ2k﹤00.8且時，對于在緊框架D表示下的k稀疏信號f，C1為僅依賴于δ2k的常數(shù)，那么（1）的最優(yōu)解f*滿足。

定理2[3]：對恢復(fù)模型（2），當測量矩陣滿足，取參數(shù)μ使得時，對于在緊框架D表示下的k稀疏信號f，C1為依賴于δ3k的常數(shù)，那么（2）的最優(yōu)解fAL滿足：

定理3[3]：對恢復(fù)模型（3），當測量矩陣滿足，噪聲滿足時，對于在緊框架D表示下的k稀疏信號f，C3為依賴于δ3k的常數(shù)，那么（3）的最優(yōu)解fADS滿足：

參考文獻

[1] S.Foucart，H.Rauhut，A Mathematical Introduction to Compressed Sensing[M].Birkhauser，2013.

[2] 蔡云.稀疏逼近中幾個經(jīng)典算法的理論分析[D].浙江大學，2015.

[3] 林俊宏.框架表示下的稀疏恢復(fù)[D].浙江大學，2013.

[4] E.Candes，Y.Eldar，D.Needell，P.Randall，Compressed sensing with coherent and redundant dictionaries[J].Appl.Comput. Harmon.Anal，2011（31）：59-73.

[5] T.Cai，A.Zhang，Sparse representation of a polytope and recovery of sparse signals and low rank matrices[J].IEEE.Trans. Inf. Theory，2014，60（1）：122-132.