迭代收縮SL0壓縮感知恢復算法

劉婉軍， 王宏志， 王賢龍

（長春工業大學 計算機科學與工程學院，吉林 長春 130012）

0 引 言

壓縮感知（Compressed Sensing，CS）信號處理理論提出以來，壓縮感知信號恢復算法的研究一直是壓縮感知理論研究重點。在壓縮感知理論框架下，信號經過稀疏表示，在適當的測量矩陣下采樣，仍然能夠從低維采樣信號中以很高的精度恢復出原始信號［1－2］。從數學上來說，CS理論指出如果信號是可稀疏表示的，測量矩陣滿足RIP［2］條件，就可以高概率從欠定采樣信號中恢復出原信號。目前，國內外很多學者在研究壓縮感知信號恢復算法，并且取得了一些成果［3－6］。壓縮感知的重構算法主要分為貪婪算法［7］和凸優化算法［1］。SL0算法［8］是結合貪婪算法和凸優化算法的一種欠定問題求解算法。由于SL0用一個連續函數的極限表示L0范數，所以求解并不像凸優化算法求解近似線性最優化問題，而是一個非線性最小化問題。SL0算法在算法恢復精度優于凸優化算法中的BP算法［9－10］，同時速度是優于貪婪算法［9－10］。因為SL0算法在壓縮感知信號處理的高效性，SL0算法被許多學者研究，并相應提出了許多改進算法［11－13］。文中在原有SL0算法的基礎上引入迭代收縮，提出迭代收縮壓縮感知SL0PL算法，加快每次最小值搜索速度，減少總的迭代次數，從而使得信號在恢復精度不變的情況下，減少信號恢復時間。

1 SL0壓縮感知算法介紹

壓縮感知理整體框架［1］如圖1所示。

圖1 壓縮感知信號處理框架

原始信號s∈Rn可以用某個正交基Ψ 稀疏表示為Θ∈Rn，將稀疏信號Θ經過測量矩陣Φ∈Rm×n進行采樣，得到采樣信號y∈Rm。在信號接收端，通過求解式（1）恢復原信號

其中

滿足這種性質的函數有很多。SL0壓縮感知算法中采用高斯函數

使用最速下降法循環迭代式（3），σj＝?σj－1，?是下降比例。迭代直到兩次計算誤差小于閾誤差TOL或者σj＜σmin迭代結束，求得恢復信號。

2 迭代閾值收縮SL0算法

SL0算法是壓縮感知信號恢復算法中一種較為有效的恢復算法。無論在理論分析或者實際應用中，SL0算法的有效性都得到了證明［9－10］。其恢復速度是BP算法的2～3倍［9－10］。文中將SL0算法應用于圖像分塊壓縮感知的時候發現，在SL0算法中引入迭代收縮可以減小SL0算法迭代次數，加快每次迭代局部最優解尋找過程，從而減少信號恢復時間。

閾值收縮算法廣泛應用于迭代最小化問題求解當中。對于最小化問題

在前文分析的SL0算法中，SL0算法也是利用不斷的迭代使用最速下降法［6］去尋找最優解。這個思想和閾值收縮是一致的，因此，在SL0每次的迭代過程中加入閾值收縮步驟。同時，SL0算法每次迭代中σ是動態改變的，如果使用固定的收縮閾值，就會導致在不同的σ的情況下，閾值收縮對恢復信號影響不一致，甚至會降低信號恢復質量。因此，定義閾值函數：

n——原始信號長度。

在每次迭代中，先用最速下降法求得本次迭代最優解，然后再進行一次閾值收縮。整個算法步驟如下：

1）利用最小二乘法求得一個近似解

2）最速下降法求解局部最小值

4）步驟2），3）循環L次，計算與第i－1次恢復結果的殘差e，如果誤差e小于閾值TOL或者迭代次數超過最大迭代次數Imax，結束。否則進入步驟5）。

5）閾值收縮系數εj＋1＝εjη，其中η是下降比例，σj＋1＝?σj進入步驟2）。

3 實驗結果

為了驗證迭代收縮算法的信號恢復效果以及恢復時間確實如上述理論分析所說，對一維隨機信號進行實驗。

選取信號長度為n＝1 000的隨機信號，采樣率ration從0.2～0.9，采樣矩陣采用高斯隨機矩陣，每個采樣率重復實驗10次，對重復實驗的結果取平均值作為該采樣率的實驗結果。實驗中，最速下降法最大迭代次數L＝3，迭代誤差閾值TOL＝0.000 1，收縮閾值稀疏ε下降比例η＝0.86。整個迭代，最大迭代次數Imax＝100。記錄每個采樣率信號恢復時間以及恢復信號信噪比PSN。得出的實驗數據如圖2所示。

圖2 SL0算法與迭代收縮SL0算法恢復比較

SL0和迭代收縮SL0算法迭代次數比較見表1。

表1 SL0和迭代收縮SL0算法迭代次數比較

從圖2和表1可以看出，用迭代收縮SL0信號恢復算法，在相同采樣率條件下，需要的迭代次數比SL0平均減小3～6次，迭代次數減少不但使得信號恢復時間減少，同時避免對最優解過操作，使得信號恢復質量降低。迭代收縮SL0的恢復時間相比于SL0恢復算法有一定的提升，特別是在采樣率比較高，采樣信號數據量大，恢復時間有比較明顯的減少。而且恢復信號的信噪比在采樣率為0.9的時候也達到了將近3dB的提升。

4 結 語

通過上述理論以及實驗分析，可以證明迭代收縮SL0算法是一種有效的壓縮感知信號恢復算法。無論在信號恢復時間以及恢復信號的質量上都優于SL0算法。實驗中發現，SL0算法以及改進的SL0算法信號恢復時間與采樣率的關系并不是線性關系，這表明SL0算法參數選擇在當前采樣率是不合適的，導致恢復算法不穩定。因此，未來的研究重點是引入自適應參數，使得恢復算法保持穩定性。

［1］Donoho D L.Compressed sensing［J］.Information Theory，IEEE Transactionson，2006，52（4）：1289－1306.

［2］CandèS E J，Romberg J，Tao T.Robust uncertainty principles：Exact signal reconstruction from highly incomplete frequency information［J］.Information Theory，IEEE Transactionson，2006，52（2）：489－509.

［3］焦李成，楊淑媛，劉芳，等.壓縮感知回顧與展望［J］.電子學報，2011，39（7）：1651－1662.

［4］戴瓊海，付長軍，季向陽.壓縮感知研究［J］.計算機學報，2011，34（3）：425－434.

［5］石光明，劉丹華，高大化，等.壓縮感知理論及其研究進展［J］.電子學報，2009，37：1070－1081.

［6］CandèE J S，Wakin M B.An introduction to compressive sampling［J］.IEEE Signal Processing Magazine，2008，25（2）：21－30，1070－1081.

［7］Tropp J A，Gilbert A C.Signal recovery from random measurements via orthogonal matching pursuit［J］.Information Theory，IEEE Transactionson，2007，53（12）：4655－4666.

［8］Mohimani G H，Babaie Zadeh M，Jutten C.Fast Sparse Representation based on Smoothed？0 Norm［C］／／Independent Component Analysis and Signal Separation.Springer Berlin Heidelberg，2007：389－396.

［9］Mohimani H，Babaie Zadeh M，Gorodnitsky I，et al.Sparse Recovery using Smoothed ＄／ell＾0＄（SL0）：Convergence Analysis［C］.arXiv Preprint arXiv：2010，1001：5073.

［10］Hyder M，Mahata K.An approximate L0norm minimization algorithm for compressed sensing［C］／／Acoustics，Speech and Signal Processing，2009.ICASSP 2009.IEEE International Conferenceon.IEEE，2009：3365－3368.

［11］王軍華，黃知濤，周一宇，等.基于近似L0范數的穩健稀疏重構算法［J］.電子學報，2012，40（6）：1185－1189.

［12］Cui Z H，Zhang Lu W.An Improved Smoothed l0－norm Algorithm Based on Multiparameter Approximation Function，in 12th IEEE International Conference on Communication Technology （ICCT）［C］／／China：Nanjing，2010：11－14，942－945.

［13］Mohimani H，Babaie Zadeh M，Jutten C.A fast approach for overcomplete sparse decomposition based on smoothednorm［J］.Signal Processing，IEEE Transactionson，2009，57（1）：289－301.