壓縮感知問題統計建模及應用

邊昂，張建州

四川大學計算機學院，成都 610065

壓縮感知問題統計建模及應用

邊昂，張建州

四川大學計算機學院，成都 610065

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

壓縮感知；高斯噪聲；l0范式最小絕對偏差；加權中值；假設檢驗

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

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

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

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

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

1 壓縮感知問題的高斯統計模型

觀測信號受到加性噪聲干擾的壓縮感知問題可以表示為如下數學模型進行考慮：

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

當M足夠大時，可以選用一些合適的統計檢驗方法來幫助分析和解決壓縮感知算法中出現的一些問題。

2 統計模型在加權中值回歸估計中的應用

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

2.1 加權中值回歸估計

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

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

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

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

2.2 χ2檢驗下的l1支持檢測

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

2.3 F檢驗停止準則

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

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

3 算法綜述

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

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

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

4 仿真實驗

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

4.1 實驗1

本實驗通過重建信號的稀疏程度對比展示改進后的算法的收斂情況。

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

圖1 信噪比為35 dB下的重建信號殘余能量對比

圖2 稀疏元素為常值情況下的重建信號非零元素個數增長情況對比

圖3 稀疏元素值服從N(0，10)情況下的重建信號非零元素個數增長情況對比

為了更好地說明改進后算法的收斂情況，首先在圖2中對比了兩種算法在兩組非零元素值為常數10的隨機信號上的重建信號的非零元素個數變化情況，然后在圖3中展示了兩種算法在非零元素值服從方差為10的高斯分布的隨機信號的重建信號非零元素增長及收斂情況。可以看到隨著迭代步數的增加WM算法重建信號的非零元素個數先是緩慢上升，然后快速增長，最后趨向于穩定，最終重建信號幾乎全部非零，遠遠超過真實稀疏度。而改進后的算法可以在非零元素個數突增之前穩定下來。

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

4.2實驗2

圖4 不同信噪比下的平均迭代次數和信號重建效果

從實驗結果可以看出在信噪比較高的情況下，算法均能自適應收斂且收斂次數也是較為穩定的，重建信號的均方誤差也沒有較大的波動，也并沒有隨著信噪比變大而趨于下降。

5 結論

本文提出了高斯統計模型來解釋高斯隨機觀測矩陣與高斯噪聲下的壓縮感知重建問題，并在此基礎上，根據相應的統計檢驗方法對l0范式約束下的加權中值回歸估計算法的坐標下降計算順序和人工設定的迭代停止準則問題提出了l1支持檢測計算順序和F檢驗停止準則，并通過數字仿真實驗驗證了其有效性。

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

[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]徐志強.壓縮感知[J].中國科學：數學，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.

邊昂，女，碩士，研究方向：計算機視覺；張建州，男，博士，教授，研究方向：模式識別，計算機視覺，機器學習，計算機應用技術，密碼函數和計算復雜性。E-mail：bmdbianang@gmail.com

2013-01-04

2013-03-11

1002-8331（2014）21-0218-06