壓縮感知問題統(tǒng)計(jì)建模及應(yīng)用

邊昂，張建州

四川大學(xué)計(jì)算機(jī)學(xué)院，成都 610065

壓縮感知問題統(tǒng)計(jì)建模及應(yīng)用

邊昂，張建州

四川大學(xué)計(jì)算機(jī)學(xué)院，成都 610065

對(duì)高斯噪聲下的高斯隨機(jī)觀測矩陣壓縮感知問題建立了新的統(tǒng)計(jì)模型，并在該統(tǒng)計(jì)模型的基礎(chǔ)上，引入相應(yīng)的統(tǒng)計(jì)檢驗(yàn)方法對(duì)l0范式約束下的硬閾值加權(quán)中值回歸重建算法進(jìn)行分析。提出了基于卡方檢驗(yàn)的l1范式支持檢測計(jì)算順序排序方法來改進(jìn)該算法的坐標(biāo)下降的計(jì)算順序；針對(duì)該算法需要通過人工設(shè)定最大迭代次數(shù)和殘差能量下界來控制迭代次數(shù)的問題，提出了基于F檢驗(yàn)的自適應(yīng)停止準(zhǔn)則，并在仿真實(shí)驗(yàn)中證明了改進(jìn)后算法的有效性。

壓縮感知；高斯噪聲；l0范式最小絕對(duì)偏差；加權(quán)中值；假設(shè)檢驗(yàn)

壓縮感知[1-2]旨在通過解決非光滑優(yōu)化的問題，將稀疏信號(hào)從被噪聲污染的較少的觀測信息中重建出來。在這個(gè)領(lǐng)域最大的挑戰(zhàn)就是如何在范式約束下，對(duì)不適定方程進(jìn)行求解。

目前針對(duì)高斯噪聲等有界誤差噪聲的方法有很多，包括匹配追蹤（MP）[3]，正交匹配追蹤（OMP）[4]，逐步正交匹配追蹤（StOMP）[5]，正則化正交匹配追蹤（ROMP）[6]，子空間匹配追蹤（SSMP）[7]和壓縮感知匹配追蹤（CoSaMP）[8]等貪心算法，以及Lasso[9]和Dantzig[10]選擇算法這樣的凸松弛算法。最近有文章指出，Lasso和Dantzig選擇算法可以取到最好的效果[11]。

最近，一個(gè)基于稀疏信號(hào)服從特定分布的壓縮感知混合高斯統(tǒng)計(jì)模型在文獻(xiàn)[12]中被提出。在這篇文獻(xiàn)中，通過對(duì)稀疏信號(hào)的概率分布的假設(shè)，將壓縮感知問題作為一個(gè)統(tǒng)計(jì)問題進(jìn)行分析，并通過該統(tǒng)計(jì)模型下引入線性濾波算法進(jìn)行分析。在信號(hào)服從高斯或高斯混合分布的假設(shè)下，線性濾波算法被證實(shí)比傳統(tǒng)的貪婪算法更高效。但是稀疏信號(hào)的特定概率分布假設(shè)在現(xiàn)實(shí)中比較難以實(shí)現(xiàn)和檢驗(yàn)，而高斯隨機(jī)觀測矩陣卻是比較常用的滿足RIP性質(zhì)的構(gòu)造觀測矩陣[13-14]，因此本文針對(duì)被高斯噪聲污染的高斯測量矩陣壓縮感知問題建立了一個(gè)新的高斯統(tǒng)計(jì)模型，將觀測向量作為服從特定分布的相互獨(dú)立的樣本點(diǎn)，在此基礎(chǔ)上，可以引入相應(yīng)的統(tǒng)計(jì)檢驗(yàn)方法來分析和解決壓縮感知算法中出現(xiàn)的相關(guān)問題。

文獻(xiàn)[15]提出的坐標(biāo)下降的加權(quán)中值回歸估計(jì)方法是一種通過坐標(biāo)下降的線性濾波算子來估計(jì)絕對(duì)偏差最優(yōu)解，以正則化參數(shù)作為硬閾值來控制解的稀疏性的l0范式約束下的優(yōu)化算法。該算法被證實(shí)對(duì)重尾噪聲，高斯噪聲，混合高斯噪聲等不同類型的噪聲都是穩(wěn)健的。然而，根據(jù)算法的設(shè)定，隨著迭代次數(shù)的增加，硬閾值呈指數(shù)級(jí)下降，導(dǎo)致解的非零元個(gè)數(shù)也會(huì)隨之不斷增加以致遠(yuǎn)遠(yuǎn)超出真實(shí)稀疏度。因此，自適應(yīng)的迭代停止準(zhǔn)則成為通過加權(quán)中值回歸估計(jì)得到真實(shí)稀疏解的必要條件。本文在高斯統(tǒng)計(jì)模型的基礎(chǔ)上引入相應(yīng)的統(tǒng)計(jì)檢驗(yàn)方法，提出了新的計(jì)算順序排序方法和自適應(yīng)的迭代停止準(zhǔn)則，有效地避免加權(quán)中值回歸迭代算法中的需要手動(dòng)控制迭代次數(shù)和殘余能量下界的弊端。

本文接下來將首先介紹壓縮感知問題的統(tǒng)計(jì)建模，然后分別介紹加權(quán)中值回歸估計(jì)，以及建立在統(tǒng)計(jì)模型基礎(chǔ)上的基于卡方檢驗(yàn)的計(jì)算順序排序方法和基于F分布的迭代停止準(zhǔn)則，并在此基礎(chǔ)上提出改進(jìn)后的算法，再通過仿真實(shí)驗(yàn)結(jié)果說明算法的有效性，最后給出總結(jié)和進(jìn)一步展望。

1 壓縮感知問題的高斯統(tǒng)計(jì)模型

觀測信號(hào)受到加性噪聲干擾的壓縮感知問題可以表示為如下數(shù)學(xué)模型進(jìn)行考慮：

其中，X是N維的稀疏信號(hào)，也是目標(biāo)向量，非零元素個(gè)數(shù)為K；Y是M維觀測信號(hào)；A是M×N的觀測矩陣，且M?N；ξ為噪聲向量。高斯隨機(jī)矩陣是壓縮感知問題中最常用的滿足RIP性質(zhì)的隨機(jī)觀測矩陣之一，高斯噪聲也是比較常見的噪聲，因此可以建立起相應(yīng)的統(tǒng)計(jì)模型來描述這種情況下的壓縮感知問題。

當(dāng)M足夠大時(shí)，可以選用一些合適的統(tǒng)計(jì)檢驗(yàn)方法來幫助分析和解決壓縮感知算法中出現(xiàn)的一些問題。

2 統(tǒng)計(jì)模型在加權(quán)中值回歸估計(jì)中的應(yīng)用

按照壓縮感知問題模型式（1），信號(hào)重建可以表述為根據(jù)少量觀測信號(hào)和給定的觀測矩陣對(duì)稀疏信號(hào)求逆的過程。但方程（1）是不適定的，無法直接對(duì)其進(jìn)行逆運(yùn)算。用優(yōu)化的方法來重建信號(hào)是一類比較常見的壓縮感知算法，加權(quán)回歸估計(jì)算法（WM算法）即是其中之一。

2.1 加權(quán)中值回歸估計(jì)

在噪聲服從重尾分布或高斯分布的情況下，可以用l1范式約束解的精確性，用l0范式約束解的稀疏性，將相應(yīng)的優(yōu)化問題表示如下：

其中，τ是約束解的稀疏性在優(yōu)化過程中重要性的正則化參數(shù)，也是求解中衡量解的顯著性的硬閾值參數(shù)。但是優(yōu)化問題式（2）是一個(gè)NP難解問題。為解決這一難題，文獻(xiàn)[10]提出了硬閾值坐標(biāo)下降回歸估計(jì)的方法來解決這一難題。算法描述如下：

輸入：觀測向量Y，高斯或伯努力隨機(jī)觀測矩陣A，閾值控制參數(shù)0＜β＜1，預(yù)設(shè)迭代次數(shù)K和目標(biāo)殘余能量ε。

大量實(shí)驗(yàn)表明，該算法在信噪比較高的情況下，對(duì)不同類型的噪聲都是穩(wěn)健的。但是，算法的迭代停止準(zhǔn)則——最大迭代次數(shù)和殘余能量下界都需要在迭代開始前人工來設(shè)定。由于硬閾值著迭代次數(shù)的增加呈指數(shù)下降的，因此，較多的迭代次數(shù)會(huì)使硬閾值過小，無法有效判定向量元素是否為零，使得解的非零元素個(gè)數(shù)超過真實(shí)個(gè)數(shù)，無法得到最優(yōu)解。如果控制迭代的次數(shù)較少，又會(huì)使得算法對(duì)較小的非零元素不敏感，影響了解的精確性。因此，在噪聲方差和信號(hào)稀疏性未知的情況下，有必要尋找一個(gè)合適的，自適應(yīng)的迭代停止準(zhǔn)則來幫助算法在找到最優(yōu)解的時(shí)候自行中止迭代。

2.2 χ2檢驗(yàn)下的l1支持檢測

相對(duì)于原算法的坐標(biāo)下降的計(jì)算順序，提出了基于卡方檢驗(yàn)的l1支持檢測方法，通過該方法對(duì)元素的顯著性進(jìn)行判定，并按照元素顯著性從大到小的次序進(jìn)行計(jì)算。

2.3 F檢驗(yàn)停止準(zhǔn)則

WM算法的迭代停止準(zhǔn)則通過人工設(shè)置迭代最大次數(shù)和誤差下限的方式來實(shí)現(xiàn)。由于WM算法的硬閾值是隨迭代次數(shù)增加指數(shù)級(jí)下降的，因此隨著迭代次數(shù)的增多，算法檢出的非零元素就會(huì)越來越多。如果次數(shù)過少，解的精度達(dá)不到；如果迭代次數(shù)過多，得到的解的稀疏度又會(huì)大大超過真實(shí)解的稀疏度。因此最優(yōu)迭代次數(shù)是很難進(jìn)行人工判斷的，需要找到合適的自適應(yīng)的停止準(zhǔn)則進(jìn)行代替。

WM算法將解向量初始化為零向量。在仿真實(shí)驗(yàn)中可以觀察到，隨著迭代次數(shù)的增加，殘余能量曲線首先短暫下降，然后，由于硬閾值的指數(shù)級(jí)下降而迅速上升，且曲線的下降和上升都不是單調(diào)遞減或單調(diào)遞增的。因此需要設(shè)計(jì)一個(gè)雙向的停止準(zhǔn)則使得算法能夠適應(yīng)零初值的設(shè)定，也可以在殘余能量快速上升之前停止迭代。

3 算法綜述

考慮固定不同的正則化參數(shù)會(huì)得到不同的最優(yōu)解，因此本文增加了正則化參數(shù)控制機(jī)制，只在檢出非零元素個(gè)數(shù)不變的情況下才允許硬閾值下降。具體算法如下：

輸入：觀測向量Y，高斯隨機(jī)觀測矩陣A，閾值控制參數(shù)0＜β＜1，置信水平α，其中β的最優(yōu)取值范圍為[0.75，0.95]。在參數(shù)缺失的情況下，默認(rèn)β=0.8，α=0.05。

復(fù)步驟（1），（2）；否則，停止迭代。

4 仿真實(shí)驗(yàn)

本章將通過仿真實(shí)驗(yàn)來展示改進(jìn)后的算法的性能。實(shí)驗(yàn)1展示了改進(jìn)后算法的收斂情況，實(shí)驗(yàn)2則展示了在不同信噪比下的還原信號(hào)的精確程度。以下實(shí)驗(yàn)均采用服從均值為0，方差為1的高斯分布的高斯隨機(jī)觀測矩陣。

4.1 實(shí)驗(yàn)1

本實(shí)驗(yàn)通過重建信號(hào)的稀疏程度對(duì)比展示改進(jìn)后的算法的收斂情況。

在圖1中展示了信噪比為24 dB下的兩種方法在兩組噪聲服從方差為1的高斯分布，信號(hào)長度，稀疏度，觀測信號(hào)個(gè)數(shù)分別為(250，12，100)和(512，20，256)，信噪比為35 dB的隨機(jī)信號(hào)上的重建信號(hào)的殘余能量的變化曲線?？梢钥吹?，WM算法的重建信號(hào)的殘余能量隨著迭代步數(shù)的增加先是快速下降然后不斷攀升至一個(gè)穩(wěn)定值，但殘余能量穩(wěn)定值并不是l1范式下最優(yōu)的。因此可以通過對(duì)最小殘余能量進(jìn)行限制的方式控制迭代次數(shù)，而改進(jìn)后的方法確實(shí)可以輔助輸出l1范式最優(yōu)解或局部較次優(yōu)解。

圖1 信噪比為35 dB下的重建信號(hào)殘余能量對(duì)比

圖2 稀疏元素為常值情況下的重建信號(hào)非零元素個(gè)數(shù)增長情況對(duì)比

圖3 稀疏元素值服從N(0，10)情況下的重建信號(hào)非零元素個(gè)數(shù)增長情況對(duì)比

為了更好地說明改進(jìn)后算法的收斂情況，首先在圖2中對(duì)比了兩種算法在兩組非零元素值為常數(shù)10的隨機(jī)信號(hào)上的重建信號(hào)的非零元素個(gè)數(shù)變化情況，然后在圖3中展示了兩種算法在非零元素值服從方差為10的高斯分布的隨機(jī)信號(hào)的重建信號(hào)非零元素增長及收斂情況?？梢钥吹诫S著迭代步數(shù)的增加WM算法重建信號(hào)的非零元素個(gè)數(shù)先是緩慢上升，然后快速增長，最后趨向于穩(wěn)定，最終重建信號(hào)幾乎全部非零，遠(yuǎn)遠(yuǎn)超過真實(shí)稀疏度。而改進(jìn)后的算法可以在非零元素個(gè)數(shù)突增之前穩(wěn)定下來。

從以上三組實(shí)驗(yàn)結(jié)果也可以看出，改進(jìn)后算法的非零元素檢出速度變慢了，因此可以說明支持檢測算法和硬閾值下降控制機(jī)制對(duì)每步迭代的結(jié)果有所改變。

4.2實(shí)驗(yàn)2

圖4 不同信噪比下的平均迭代次數(shù)和信號(hào)重建效果

從實(shí)驗(yàn)結(jié)果可以看出在信噪比較高的情況下，算法均能自適應(yīng)收斂且收斂次數(shù)也是較為穩(wěn)定的，重建信號(hào)的均方誤差也沒有較大的波動(dòng)，也并沒有隨著信噪比變大而趨于下降。

5 結(jié)論

本文提出了高斯統(tǒng)計(jì)模型來解釋高斯隨機(jī)觀測矩陣與高斯噪聲下的壓縮感知重建問題，并在此基礎(chǔ)上，根據(jù)相應(yīng)的統(tǒng)計(jì)檢驗(yàn)方法對(duì)l0范式約束下的加權(quán)中值回歸估計(jì)算法的坐標(biāo)下降計(jì)算順序和人工設(shè)定的迭代停止準(zhǔn)則問題提出了l1支持檢測計(jì)算順序和F檢驗(yàn)停止準(zhǔn)則，并通過數(shù)字仿真實(shí)驗(yàn)驗(yàn)證了其有效性。

新算法本身也有一些可以繼續(xù)改進(jìn)的地方，尤其是針對(duì)估計(jì)向量的初始化對(duì)算法的影響和高信噪比下F檢驗(yàn)停止準(zhǔn)則可否在實(shí)踐中推廣到其他類型噪聲的情況等問題還可以進(jìn)一步討論，將在今后的工作中繼續(xù)探索這些問題的解決方法。

[1]Candes E J，Romberg J，Tao T.Robust uncertainty principles：exact signal reconstruction from highly incomplete frequency information[J].IEEE Trans on Information Theory，2006，52（2）：489-509.

[2]Donoho D L.Compressed sensing[J].IEEE Trans on Information Theory，2006，52（4）：1289-1306.

[3]Mallat S，Zhang Z.Matching pursuits with time-frequency dictionaries[J].IEEE Trans on Signal Processing，1993，41（12）：3397-3415.

[4]Tropp J A，Gilbert A C.Signal recovery from random measurements via orthogonal matching pursuit[J].IEEE Trans on Information Theory，2007，53（12）：4655-4666.

[5]Donoho D L，Tsaig Y，Drori I，et al.Sparse solution of underdetermined linear equations by stagewise orthogonal matching pursuit[R].2006.

[6]Needell D，Vershynin R.Uniform uncertainty principle and signal recovery via regularized orthogonal matching pursuit[J].Foundations of Computational Mathematics，2009，9（3）：317-334.

[7]Dai W，Milenkovic O.Subspace pursuit for compressive sensing signal reconstruction[J].IEEE Trans on Information Theory，2009，55（5）：2230-2249.

[8]Needell D，Tropp J A.CoSaMP：iterative signal recovery from incomplete and inaccurate samples[J].Applied and Computational Harmonic Analysis，2009，26（3）：301-321.

[9]Chen S S，Donoho D L，Saunders M A.Atomic decomposition by basis pursuit[J].SIAM J Scientific Computing，1998，20（1）：33-66.

[10]Candes E J，Tao T.The Dantzig selector：statistical estimation when p is much larger than n[J].The Annals of Statistics，2007，35（6）：2313-2351.

[11]Candès E J，Davenport M A.How well can we estimate a sparse vector?[J].Appl Comput Harmonic Anal，2013, 34（2）：317-323.

[12]Yu G，Sapiro G.Statistical compressed sensing of Gaussian mixture models[J].IEEE Trans on Signal Processing，2011，59（12）：5842-5858.

[13]徐志強(qiáng).壓縮感知[J].中國科學(xué)：數(shù)學(xué)，2012，42（9）：865-877.

[14]Candes E J，Tao T.Decoding by linear programming[J]. IEEE Trans on Information Theory，2005，51（12）：4203-4215. [15]Paredes J L，Arce G R.Compressive sensing signal reconstruction by weighted median regression estimates[J].IEEE Trans on Signal Processing，2011，59（6）：2585-2601.

[16]Press W H，Teukolsky S A，Vetterling W T，et al.Numerical recipes in C++；The art of scientific computing[M]. 2nd ed.Beijing：Publishing House of Electronics Industry，2003：614-655.

BIAN Ang,ZHANG Jianzhou

College of Computer Science,Sichuan University,Chengdu 610065,China

In this paper,a novel statistical model is proposed to describe the Gaussian noisy compressed sensing problem with Gaussian random measurement matrix,and under the statistical framework,some hypothesis tests are used to analyse the performance of the weighted median regression estimate compressive sensing signal reconstruction with an iterative hard threshold under thel0-regularized constraint.Theχ2test based computation sequence is proposed to improve the performance of its coordination descent computation sequence,and F test based data adaptive stopping criterion is presented to take the place of its manual stopping conditions of the maximal number of iterations and the lower bound of the residual energy.Practical performance of the proposal is evaluated via numerical experiments.

compressing sensing;Gaussian noise;l0-regularized least absolute deviation;weighted median;hypothesis testing

A

TN911.7

10.3778/j.issn.1002-8331.1212-0374

BIAN Ang,ZHANG Jianzhou.Statistical model and applications of compressed sensing.Computer Engineering and Applications,2014,50（21）：218-223.

邊昂，女，碩士，研究方向：計(jì)算機(jī)視覺；張建州，男，博士，教授，研究方向：模式識(shí)別，計(jì)算機(jī)視覺，機(jī)器學(xué)習(xí)，計(jì)算機(jī)應(yīng)用技術(shù)，密碼函數(shù)和計(jì)算復(fù)雜性。E-mail：bmdbianang@gmail.com

2013-01-04

2013-03-11

1002-8331（2014）21-0218-06