迭代收縮SL0壓縮感知恢復(fù)算法

劉婉軍， 王宏志， 王賢龍

（長春工業(yè)大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院，吉林 長春 130012）

0 引 言

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

1 SL0壓縮感知算法介紹

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

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

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

其中

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

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

2 迭代閾值收縮SL0算法

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

閾值收縮算法廣泛應(yīng)用于迭代最小化問題求解當(dāng)中。對于最小化問題

在前文分析的SL0算法中，SL0算法也是利用不斷的迭代使用最速下降法［6］去尋找最優(yōu)解。這個(gè)思想和閾值收縮是一致的，因此，在SL0每次的迭代過程中加入閾值收縮步驟。同時(shí)，SL0算法每次迭代中σ是動(dòng)態(tài)改變的，如果使用固定的收縮閾值，就會導(dǎo)致在不同的σ的情況下，閾值收縮對恢復(fù)信號影響不一致，甚至?xí)档托盘柣謴?fù)質(zhì)量。因此，定義閾值函數(shù)：

n——原始信號長度。

在每次迭代中，先用最速下降法求得本次迭代最優(yōu)解，然后再進(jìn)行一次閾值收縮。整個(gè)算法步驟如下：

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

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

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

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

3 實(shí)驗(yàn)結(jié)果

為了驗(yàn)證迭代收縮算法的信號恢復(fù)效果以及恢復(fù)時(shí)間確實(shí)如上述理論分析所說，對一維隨機(jī)信號進(jìn)行實(shí)驗(yàn)。

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

圖2 SL0算法與迭代收縮SL0算法恢復(fù)比較

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

表1 SL0和迭代收縮SL0算法迭代次數(shù)比較

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

4 結(jié) 語

通過上述理論以及實(shí)驗(yàn)分析，可以證明迭代收縮SL0算法是一種有效的壓縮感知信號恢復(fù)算法。無論在信號恢復(fù)時(shí)間以及恢復(fù)信號的質(zhì)量上都優(yōu)于SL0算法。實(shí)驗(yàn)中發(fā)現(xiàn)，SL0算法以及改進(jìn)的SL0算法信號恢復(fù)時(shí)間與采樣率的關(guān)系并不是線性關(guān)系，這表明SL0算法參數(shù)選擇在當(dāng)前采樣率是不合適的，導(dǎo)致恢復(fù)算法不穩(wěn)定。因此，未來的研究重點(diǎn)是引入自適應(yīng)參數(shù)，使得恢復(fù)算法保持穩(wěn)定性。

［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］.電子學(xué)報(bào)，2011，39（7）：1651－1662.

［4］戴瓊海，付長軍，季向陽.壓縮感知研究［J］.計(jì)算機(jī)學(xué)報(bào)，2011，34（3）：425－434.

［5］石光明，劉丹華，高大化，等.壓縮感知理論及其研究進(jìn)展［J］.電子學(xué)報(bào)，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范數(shù)的穩(wěn)健稀疏重構(gòu)算法［J］.電子學(xué)報(bào)，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.