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

蔡云 石瑩

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

關鍵詞：稀疏恢復? 框架? 恢復模型? D-RIP條件

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

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

1? 經典的壓縮感知問題

經典的壓縮感知（稀疏恢復）問題主要考慮下列的恢復模型：

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

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

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

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

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

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

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

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

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

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

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

3? 恢復模型

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

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

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

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

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

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

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

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

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

參考文獻

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

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

[3] 林俊宏.框架表示下的稀疏恢復[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.