壓縮感知中RIP界的研究新進展

蔡云　石瑩　楊文國

摘? 要：該文對壓縮感知（稀疏恢復）問題的研究背景以及研究模型進行了詳細闡述，并對基于最小化的恢復模型準確恢復未知稀疏信號的恢復條件進行系統介紹，最后對基于約束等距條件（RIP）條件的恢復結果進行歸納總結。

關鍵詞：壓縮感知? 稀疏? RIP條件

中圖分類號：O29 ? ?文獻標識碼：A 文章編號：1672-3791（2019）09（c）-0237-02

現今社會處于大數據研究時代，海量數據帶來更多信息，但也帶來了數據信號存儲、傳輸和分析的困難。近年來，由菲爾茲獎獲得者T.Tao、美國科學院院士D.Donoho和美國科學院院士E.Candes等學者提出的壓縮感知理論為該問題的解決提供了全新的方法：當未知的高維信號是稀疏信號時，可以通過求解優化問題從較少的非自適應線性投影數據中以高概率精確重構原始未知信號。壓縮感知理論突破了傳統香農采樣定理中對信號采樣頻率的限制，給信號采樣理論帶來了新的變革，在核磁共振成像、雷達、圖像處理、地震勘探、傳感器網絡設計和計算生物學等領域都有著廣闊的應用前景[1]。壓縮感知已經成為國內外應用數學及其交叉學科極為熱門的研究前沿，激發了包括應用數學、統計、電氣工程、計算機科學和醫學等方面的研究人員極大的研究興趣和熱情。

1? 壓縮感知理論

壓縮感知的主要任務可歸結為求解如下線性方程組：

其中y∈Rm是觀測向量，A∈Rm×n（m≤n）是線性測量矩陣，壓縮感知的主要任務是從已知的觀測向量y和線性測量矩陣A中準確恢復未知信號。顯然，方程組是不確定性的，即它有無窮多解。但當假設未知信號具有某種特殊結構即稀疏性時，且測量矩陣A滿足良好的性質時，該方程有唯一的稀疏解。當向量中非零未知分量的個數最多為k個時，稱信號為k-稀疏信號。

求解該線性方程組最自然的方法是求解如下的l0最小化問題：

其中是向量的l0范數即向量的非零元素的個數。但由于求解上述l0最小化方法是NP難問題且計算不可行，因此研究者們尋找許多快速有效地求解最稀疏解的算法來替代l0最小化方法。其中，l1最小化方法是l0最小化方法的凸松弛方法，它在于求解如下的優化問題：

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

2? 約束等距條件（RIP條件）

l1最小化方法的解和l0最小化方法的解在什么情況下一致是數學家們極為關心的問題。探討這兩個問題等價的常用條件通常有3個：零空間條件（NSP）、非相干性條件（MIP）和約束等距條件（RIP條件）。在這3個條件之中最常用的條件為RIP條件，下面介紹RIP條件的具體定義[1]。

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

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

注意到，一個矩陣具有較小的RIP條件意味著矩陣A的每k個或者更少的列構成的子矩陣近似于一個正交矩陣。驗證某個確定性矩陣是否滿足RIP條件是較為困難的。因此，學者們通常構造滿足良好RIP條件的隨機性矩陣。并且有研究表明，當測量次數m滿足m≥Cδ-2klog（n/k）時，則高斯隨機矩陣以及次高斯隨機矩陣以高概率滿足RIP條件且δk﹤δ。另外，也有學者表明根據l1球寬度理論，測量次數m對于k和n的階數達到了最佳階數。RIP條件對于一大類結構隨機矩陣也滿足例如Gabor隨機矩陣和 Topellitz隨機矩陣[1]。當測量次數滿足m≥Cδ-2klog4n時，部分隨機傅立葉測量矩陣也以大概率滿足RIP條件且δk﹤δ。另外，有研究表明，如果隨機測量矩陣A滿足如下的集中不等式：對于任意給定的∈Rn和0﹤δ﹤1固定和常數，c，t﹥0。

那么當測量次數m≥cδ2nk，測量矩陣A以極大概率滿足RIP條件且RIC常數滿足δk≤δ。

3? 其他恢復方法

對于壓縮感知問題，除了可以使用l1最小化方法替代l0最小化方法之外，研究者們也常用一種非凸優化的方法來恢復未知稀疏信號，即lp（0﹤p﹤1）最小化方法，即考慮用非凸范數來逼近零范數：

測量矩陣A以極大概率滿足p-RIP條件時，lp（0﹤p﹤1）最小化方法能準確恢復未知稀疏信號。p-RIP條件定義如下[1]。

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

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

并且研究者表明高斯隨機測量矩陣以高概率滿足p-RIP條件，另外數值實驗也表明lp（0﹤p﹤1）最小化方法具有較好的可實現性和算法快速計算的優勢[2]。

除了用上述的凸優化和非凸優化方法直接求解未知稀疏向量，在數值算法方面，學者們主要用貪婪算法來求解稀疏界，例如匹配追蹤算法（MP）、正交匹配追蹤算法（OMP）、逐步回歸匹配追蹤算法（StOMP）、壓縮采樣匹配追蹤算法（CoSsMP）、硬閾值迭代算法（IHT）、迭代加權最小二乘算法（IRLS）、投影梯度下降算法（PGT）、軟閾值迭代算法（SHT）。各種算法在收斂性和收斂速度以及計算時間上各有優勢，具體可見參考文獻[1-2]。

4? 最新RIP研究進展

在實際應用中，觀測向量通常含有噪聲，也即有下面的觀測模型y=Ax+z，其中y∈Rm是觀測向量，A∈Rm×n（m≤n）是線性測量矩陣，z∈Rm是噪聲向量，常用的方法是考慮如下的l1約束優化問題：

其中ε是噪聲界估計。

有許多學者對問題（7）進行了研究，特別地針對基于RIP條件的恢復，Candes首先指出當測量矩陣A滿足RIP條件且時，l1最小化和恢復模型（1）能分別準確地和穩定地恢復未知稀疏信號。之后又有許多學者對這個界進行了改進，例如，Foucart 和Lai給出了δ2k﹤0.4531，Mo和Li將這個界改進至δ2k﹤0.4931，Cai和Zhang給出δ2k﹤0.5，之后他們又給出是最優界[3-4]。對于高階RIP恢復條件的研究，最近Zhang和Li給出了一個公認的最優結果，為了完整起見，我們簡要列出定理內容，具體可參見文獻[3]。

定理1：考慮恢復模型（1），當時，當測量矩陣滿足且時，對于k稀疏信號那么（1）的最優解*滿足：

5? 結語

該文具體介紹了壓縮感知的應用和理論背景，并介紹了壓縮感知的幾種恢復方法以及恢復條件，并系統介紹了基于RIP條件的一些研究進展及相應結果，最后介紹了壓縮感知RIP界的最新定理。

參考文獻

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

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

[3] 章瑞.壓縮感知中最優限制等距常數界[D].浙江大學，2017.

[4] T.Cai， A.Zhang， Sparse representation of a polytope and recovery of sparse signals and low rank matrices[J].IEEE Transactions on information theory，2014，60（1）：122-132.