壓縮感知中RIP界的研究新進(jìn)展

蔡云　石瑩　楊文國(guó)

摘? 要：該文對(duì)壓縮感知（稀疏恢復(fù)）問(wèn)題的研究背景以及研究模型進(jìn)行了詳細(xì)闡述，并對(duì)基于最小化的恢復(fù)模型準(zhǔn)確恢復(fù)未知稀疏信號(hào)的恢復(fù)條件進(jìn)行系統(tǒng)介紹，最后對(duì)基于約束等距條件（RIP）條件的恢復(fù)結(jié)果進(jìn)行歸納總結(jié)。

關(guān)鍵詞：壓縮感知? 稀疏? RIP條件

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

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

1? 壓縮感知理論

壓縮感知的主要任務(wù)可歸結(jié)為求解如下線性方程組：

其中y∈Rm是觀測(cè)向量，A∈Rm×n（m≤n）是線性測(cè)量矩陣，壓縮感知的主要任務(wù)是從已知的觀測(cè)向量y和線性測(cè)量矩陣A中準(zhǔn)確恢復(fù)未知信號(hào)。顯然，方程組是不確定性的，即它有無(wú)窮多解。但當(dāng)假設(shè)未知信號(hào)具有某種特殊結(jié)構(gòu)即稀疏性時(shí)，且測(cè)量矩陣A滿足良好的性質(zhì)時(shí)，該方程有唯一的稀疏解。當(dāng)向量中非零未知分量的個(gè)數(shù)最多為k個(gè)時(shí)，稱信號(hào)為k-稀疏信號(hào)。

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

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

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

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

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

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

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

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

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

3? 其他恢復(fù)方法

對(duì)于壓縮感知問(wèn)題，除了可以使用l1最小化方法替代l0最小化方法之外，研究者們也常用一種非凸優(yōu)化的方法來(lái)恢復(fù)未知稀疏信號(hào)，即lp（0﹤p﹤1）最小化方法，即考慮用非凸范數(shù)來(lái)逼近零范數(shù)：

測(cè)量矩陣A以極大概率滿足p-RIP條件時(shí)，lp（0﹤p﹤1）最小化方法能準(zhǔn)確恢復(fù)未知稀疏信號(hào)。p-RIP條件定義如下[1]。

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

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

并且研究者表明高斯隨機(jī)測(cè)量矩陣以高概率滿足p-RIP條件，另外數(shù)值實(shí)驗(yàn)也表明lp（0﹤p﹤1）最小化方法具有較好的可實(shí)現(xiàn)性和算法快速計(jì)算的優(yōu)勢(shì)[2]。

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

4? 最新RIP研究進(jìn)展

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

其中ε是噪聲界估計(jì)。

有許多學(xué)者對(duì)問(wèn)題（7）進(jìn)行了研究，特別地針對(duì)基于RIP條件的恢復(fù)，Candes首先指出當(dāng)測(cè)量矩陣A滿足RIP條件且時(shí)，l1最小化和恢復(fù)模型（1）能分別準(zhǔn)確地和穩(wěn)定地恢復(fù)未知稀疏信號(hào)。之后又有許多學(xué)者對(duì)這個(gè)界進(jìn)行了改進(jìn)，例如，F(xiàn)oucart 和Lai給出了δ2k﹤0.4531，Mo和Li將這個(gè)界改進(jìn)至δ2k﹤0.4931，Cai和Zhang給出δ2k﹤0.5，之后他們又給出是最優(yōu)界[3-4]。對(duì)于高階RIP恢復(fù)條件的研究，最近Zhang和Li給出了一個(gè)公認(rèn)的最優(yōu)結(jié)果，為了完整起見(jiàn)，我們簡(jiǎn)要列出定理內(nèi)容，具體可參見(jiàn)文獻(xiàn)[3]。

定理1：考慮恢復(fù)模型（1），當(dāng)時(shí)，當(dāng)測(cè)量矩陣滿足且時(shí)，對(duì)于k稀疏信號(hào)那么（1）的最優(yōu)解*滿足：

5? 結(jié)語(yǔ)

該文具體介紹了壓縮感知的應(yīng)用和理論背景，并介紹了壓縮感知的幾種恢復(fù)方法以及恢復(fù)條件，并系統(tǒng)介紹了基于RIP條件的一些研究進(jìn)展及相應(yīng)結(jié)果，最后介紹了壓縮感知RIP界的最新定理。

參考文獻(xiàn)

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

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

[3] 章瑞.壓縮感知中最優(yōu)限制等距常數(shù)界[D].浙江大學(xué)，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.