框架表示下的壓縮感知問題研究

蔡云 石瑩

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

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

中圖分類號(hào)：O29 ? ?文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1672-3791（2019）10（a）-0173-02

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3? 恢復(fù)模型

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

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

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

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

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

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

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

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

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

參考文獻(xiàn)

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

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

[3] 林俊宏.框架表示下的稀疏恢復(fù)[D].浙江大學(xué)，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.