基于改進(jìn)光滑l0范數(shù)的塊稀疏信號(hào)重構(gòu)算法

祁 銳，李宏偉，張玉潔

（1.中國(guó)地質(zhì)大學(xué)a.地球物理與空間信息學(xué)院；b.數(shù)學(xué)與物理學(xué)院，武漢430074；2.海軍工程大學(xué)理學(xué)院，武漢430033）

·開(kāi)發(fā)研究與工程應(yīng)用·

基于改進(jìn)光滑l0范數(shù)的塊稀疏信號(hào)重構(gòu)算法

祁 銳1a，2，李宏偉1b，張玉潔1b

（1.中國(guó)地質(zhì)大學(xué)a.地球物理與空間信息學(xué)院；b.數(shù)學(xué)與物理學(xué)院，武漢430074；2.海軍工程大學(xué)理學(xué)院，武漢430033）

光滑l0范數(shù)算法用帶參數(shù)的高斯光滑函數(shù)序列逼近l0范數(shù)，可以用于壓縮感知信號(hào)重構(gòu)。塊稀疏信號(hào)是一種典型的稀疏信號(hào)，它的非零元素成塊出現(xiàn)。為此，基于改進(jìn)的光滑l0范數(shù)提出一種塊稀疏信號(hào)重構(gòu)算法。利用反正切函數(shù)取代高斯函數(shù)序列，通過(guò)對(duì)下降因子的優(yōu)化處理進(jìn)一步提高收斂效果。仿真實(shí)驗(yàn)結(jié)果表明，相比塊光滑l0范數(shù)算法、光滑l0范數(shù)算法以及正交匹配追蹤算法，該算法具有更好的魯棒性和更高的信噪比。

壓縮感知；塊稀疏；光滑l0范數(shù)；信號(hào)重構(gòu)

1 概述

文獻(xiàn)［1］提出一種新的信號(hào)采樣理論——壓縮感知（Compressed Sensing，CS）。CS在采樣的同時(shí)完成了信號(hào)的壓縮，它可以突破Nyquist采樣定律的限制對(duì)信號(hào)進(jìn)行采樣，并完成精確重構(gòu)。

針對(duì)組合優(yōu)化問(wèn)題，眾多學(xué)者已經(jīng)提出了很多有效的重構(gòu)算法，包括經(jīng)典的基追蹤（Basis Pursuit，BP）算法［2］和正交貪婪（Orthogonal Greedy A lgorithm，OGA）算法［3-4］，以及光滑l0范數(shù)（Smoothed l0Norm，SL0）算法［5］等，但是這些算法是針對(duì)傳統(tǒng)的稀疏信號(hào)，沒(méi)有考慮到源信號(hào)的結(jié)構(gòu)特性。

不同于一般傳統(tǒng)信號(hào)，有些信號(hào)呈現(xiàn)出一種特殊的結(jié)構(gòu)，比如，非零元素成塊形式出現(xiàn)，這種信號(hào)稱(chēng)為塊稀疏信號(hào)。針對(duì)這種塊稀疏信號(hào)的特點(diǎn)，學(xué)者們進(jìn)行了深入的研究，提出了許多有效的算法［6-10］。此外，文獻(xiàn)［11］將SL0算法推廣到塊稀疏信號(hào)重構(gòu)問(wèn)題中，提出了塊光滑l0范數(shù)（Block Smoothed l0Norm，BSL0）算法.本文結(jié)合貪婪算法的快速性和凸優(yōu)化算法的準(zhǔn)確性，研究基于BSL0算法的一種改進(jìn)算法，用一系列含參數(shù)的反正切函數(shù)來(lái)逼近l0范數(shù)，并結(jié)合對(duì)下降因子σ的處理，使得算法在信噪比和重構(gòu)時(shí)間上取到平衡，稱(chēng)為改進(jìn)的塊光滑l0范數(shù)（Improved Block Smoothed l0Norm，IBSL0）。

2 壓縮感知與塊稀疏信號(hào)

2.1 組合優(yōu)化問(wèn)題

假定s∈Rm×1是一個(gè)未知的源信號(hào)，經(jīng)過(guò)測(cè)量矩陣A∈Rn×m（n＜m）并滿(mǎn)足x=As，得到觀(guān)測(cè)信號(hào)x∈Rn×1，由于方程x=As本身是欠定的，因此它存在無(wú)窮多個(gè)解，于是必須添加一些附加條件以保證解的唯一性。在源信號(hào)s稀疏的假設(shè)下，恢復(fù)源信號(hào)s可以通過(guò)求解如下的組合優(yōu)化問(wèn)題：

2.2 塊稀疏信號(hào)壓縮感知模型

塊稀疏信號(hào)壓縮感知模型如下：

其中，A∈Rn×m稱(chēng)為測(cè)量矩陣，它的元素服從高斯分布或伯努利分布，n＜m；x∈Rn×1是觀(guān)測(cè)信號(hào)；s∈Rm×1是塊稀疏源信號(hào)，具體形式如下：

其中，si（i=1，2，…，N）是源信號(hào)s的第i塊；d是每塊的大小，且滿(mǎn)足m=Nd。一個(gè)塊稀疏信號(hào)s稱(chēng)為k-稀疏是指N個(gè)塊中至多有k個(gè)非零塊，即有k個(gè)不為0，可以看到，如果d=1，這種塊稀疏模型退化成傳統(tǒng)的稀疏信號(hào)模型。

I（x）是示性函數(shù)，且滿(mǎn)足：

2.3 重構(gòu)算法

目前塊稀疏信號(hào)的重構(gòu)主要基于以下4種算法：

（1）L-OPT算法。由于求解式（4）是一個(gè)NP-難問(wèn)題，因此文獻(xiàn)［6］利用信號(hào)的塊稀疏特性，將l1范數(shù)最小化的思想移植到問(wèn)題式（4），將其轉(zhuǎn)化為如下的混合l2/l1范數(shù)凸優(yōu)化問(wèn)題來(lái)求解：

文獻(xiàn)［12］進(jìn)一步證明了在滿(mǎn)足一定條件下，可以用式（5）精確地恢復(fù)任意的塊稀疏源信號(hào)。

（2）針對(duì)塊稀疏信號(hào)的貪婪類(lèi)算法［7］。將經(jīng)典的貪婪類(lèi)算法——正交匹配追蹤（Orthogonal M atching Pursuit，OMP）算法拓展到塊稀疏信號(hào)中，得到針對(duì)塊稀疏信號(hào)的塊正交匹配追蹤（Block OMP，BOMP）算法。以BOMP為例，該算法主要由3個(gè)部分構(gòu)成：相關(guān)最大化，更新信號(hào)支撐塊，更新殘差。其中，算法在每次相關(guān)最大化操作時(shí)只找到一個(gè)信號(hào)支撐塊，對(duì)于塊稀疏度為k的信號(hào)，至少需要k次迭代才能恢復(fù)源信號(hào)，算法效率偏低。

（3）基于混合l2/lp范數(shù)的非凸優(yōu)化算法［8］。它的主要思想是將塊稀疏信號(hào)的范數(shù)最小化問(wèn)題轉(zhuǎn)化為如下的非凸優(yōu)化問(wèn)題：

其中：

實(shí)驗(yàn)結(jié)果說(shuō)明該算法要優(yōu)于混合l2/l1范數(shù)凸優(yōu)化算法。

（4）將SL0算法推廣到塊稀疏信號(hào)中的BSL0算法［11］。BSL0相當(dāng)于將SL0算法應(yīng)用到塊稀疏信號(hào)中，將塊稀疏信號(hào)的范數(shù)最小化問(wèn)題用一系列高斯函數(shù)序列去逼近。

3 本文算法

假定源信號(hào)s是一個(gè)k-稀疏信號(hào)，求解式（1）的l0范數(shù)最小化問(wèn)題需要窮舉所有的Ckm種可能，隨著源信號(hào)維數(shù)m的增大，它將會(huì)非常難以實(shí)現(xiàn)。文獻(xiàn)［5］提出了光滑l0范數(shù)（SL0）算法，該算法的主要思想是用連續(xù)的高斯函數(shù)序列去逼近不連續(xù)的l0范數(shù)，考慮高斯函數(shù)，很明顯有：

因此，定義：

將SL0算法應(yīng)用到塊稀疏信號(hào)的重構(gòu)問(wèn)題中［11］，定義：

由于塊稀疏信號(hào)重構(gòu)問(wèn)題可以轉(zhuǎn)化為如下的優(yōu)化問(wèn)題：

其中，b=［b1，b2，…，bn］T，取反正切函數(shù)，可以得到：

于是式（13）轉(zhuǎn)化為如下的優(yōu)化問(wèn)題：

式（16）的目標(biāo)函數(shù)是一個(gè)凸函數(shù)，可以通過(guò)梯度下降法求得它的最值。令Δσ表示函數(shù)Hσ（s）的梯度，考慮到源信號(hào)s的塊稀疏特性，Hσ（s）的梯度可以用如下的分塊形式表示：

由于σ的取值對(duì)Hσ（s）的取值和平滑度有很大影響：σ越大，Hσ越平滑，但是與l0范數(shù)的近似程度越差；σ越小，Hσ越不平滑，但是與l0范數(shù)越近似。為此，在σ迭代下降的過(guò)程中，設(shè)置新的動(dòng)態(tài)σ，使得σ在Hσ（s）接近真值時(shí)逐漸變小，減慢了速度，但是提高了精度，新的算法在信噪比和重構(gòu)時(shí)間上取到平衡，重構(gòu)時(shí)間上稍作犧牲，卻在重構(gòu)精度上優(yōu)化效果顯著。

具體算法流程如下：

Step1 初始化

（2）選擇合適值σ1，σmin，c，cmax，ρ，L，μ。

Step2 for j=1，2，…，J

（1）σ=σj，當(dāng)σ＞σmin時(shí)；

（2）在可行域上使用最速下降算法最小化函數(shù)Hσ（s）（其次是投影到可行集）：

2）for l=1，2，…，L（循環(huán)L次）

①令ΔHσ如式（6）所示；

②s←s-（μσ2）ΔHσ，其中μ較為較小的整數(shù)；

③將s投影到可行集S：

s←s-AT（AAT）-1（As-x）

（3）σ=cσ；

（4）如果c＞cmax，則c=cmax；否則，c=ρc。

算法說(shuō)明：

（2）算法Step2的（1）～（4）的作用在于σ迭代下降的過(guò)程中，設(shè)置新的動(dòng)態(tài)σ，使得σ在Hσ（s）接近真值時(shí)逐漸變小，進(jìn)而提高估計(jì)精度。在仿真實(shí)驗(yàn)中，取cmax=0.8，ρ=1.2。

4 仿真實(shí)驗(yàn)與結(jié)果分析

利用蒙特卡羅實(shí)驗(yàn)將IBSL0算法與BSL0算法、BOMP算法以及SL0算法進(jìn)行比較，所有仿真結(jié)果都是在W indow s XP操作系統(tǒng)、內(nèi)存2.00 GB，處理器Intel（R）Core（TM）2 CPU 2.80 GHz，軟件M atlab 7.1平臺(tái)上進(jìn)行仿真的。

塊稀疏信號(hào)是人工產(chǎn)生的，方法如下：塊稀疏信號(hào)為m維向量，將其均勻分成N塊，每塊大小為d，在N個(gè)塊中任意選取k塊作為非零塊，其中每個(gè)元素服從均值為0方差為1的標(biāo)準(zhǔn)正態(tài)分布N（0，1），其余N-k塊所有元素均為0?；旌暇仃嘇∈Rn×m服從均值為0方差為1的標(biāo)準(zhǔn)正態(tài)分布，且每列進(jìn)行單位化。塊稀疏信號(hào)模型可以表示為：

在以下實(shí)驗(yàn)中，取源信號(hào)維數(shù)m=1 000，觀(guān)測(cè)信號(hào)維數(shù)n=400，內(nèi)循環(huán)迭代次數(shù)L=3，μ=2，σmin= 0.000 1。用信噪比（Signal to Noise Ratio，SNR）sSNR來(lái)評(píng)價(jià)估計(jì)效果，SNR定義為：

實(shí)驗(yàn)1 考查分塊大小d變化時(shí)，IBSL0算法在不同噪聲方差情況下的信噪比變化情況。塊稀疏信號(hào)的稀疏度為k（即N塊中至多k塊非零，源信號(hào)的整體稀疏度為k×d），改變k和d（塊大?。┑娜≈担譃橐韵?種情況：

（1）k×d=100，（k，d）的取值分別為（100，1），（50，2），（25，4），（20，5），（10，10），（5，20），（2，50），（4，25），（1，100）。

（2）k×d=200，（k，d）的取值分別為（200，1），（100，2），（50，4），（40，5），（25，8），（20，10），（10，20），（8，25），（5，40），（2，100），（1，200）。

圖1、圖2分別對(duì)應(yīng)k×d=100，k×d=200=n/2（即源信號(hào)的總體稀疏度達(dá)到觀(guān)測(cè)信號(hào)維數(shù)的一半），分塊從小變大時(shí)，IBSL0算法在噪聲方差逐漸變大時(shí)的信噪比變化情況?？梢钥闯觯琁BSL0算法的信噪比隨著噪聲方差變大慢慢降低，當(dāng)且塊大小為20時(shí)，IBSL0算法的信噪比約為35 dB，總體來(lái)說(shuō)具有不錯(cuò)的抗噪性能，特別是當(dāng)k×d=時(shí)，IBSL0算法仍然具有不錯(cuò)的估計(jì)效果。

圖1 噪聲方差變大時(shí)IBSL0算法估計(jì)性能1

圖2 噪聲方差變大時(shí)IBSL0算法估計(jì)性能2

實(shí)驗(yàn)2 考查塊大小d變化時(shí)，IBSL0算法與BSL0算法、BOMP算法以及SL0算法的信噪比變化情況，該實(shí)驗(yàn)重復(fù)進(jìn)行50次（每次實(shí)驗(yàn)中參數(shù)相同，但混合矩陣A及塊稀疏信號(hào)都隨機(jī)產(chǎn)生），然后取平均，噪聲方差取。

由圖3可以看到，當(dāng)k×d=100時(shí)，4種算法都隨著分塊大小變大時(shí)效果越來(lái)越好，IBSL0算法與BSL0算法性能相當(dāng)，但明顯好于BOMP算法以及SL0算法，SL0的效果最差。由于當(dāng)源信號(hào)的稀疏度不超過(guò)觀(guān)測(cè)信號(hào)維數(shù)的一半時(shí)，式（1）對(duì)應(yīng)的稀疏解s是唯一的，事實(shí)上許多算法在源信號(hào)的稀疏度達(dá)到臨界值時(shí)都不能很好地恢復(fù)源信號(hào)s。然而，圖4表明，當(dāng)k×d=200=n/2時(shí)，隨著分塊大小d增大，BOMP算法以及SL0算法信噪比只有10 dB不到，它們幾乎不能恢復(fù)出原信號(hào)，而IBSL0算法信噪比仍然可以達(dá)到35 dB，高于BSL0算法信噪比30 dB，可見(jiàn)IBSL0算法相比其他算法具有很大的優(yōu)勢(shì)。

圖3 k×d=100時(shí)算法性能比較

圖4 k×d=200時(shí)算法性能比較

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

本文在塊稀疏光滑l0范數(shù)（BSL0）算法的基礎(chǔ)上，用反正切函數(shù)替代高斯函數(shù)，并對(duì)下降因子進(jìn)行改進(jìn)，提出了針對(duì)塊稀疏信號(hào)的改進(jìn)塊光滑l0范數(shù)（IBSL0）算法。數(shù)值實(shí)驗(yàn)表明，IBSL0算法不僅具有不錯(cuò)的魯棒性，而且相比BSL0算法、SL0算法，以及OMP算法，在不同的分塊大小情況下，信噪比都有一定的提高，特別是，當(dāng)源信號(hào)的稀疏度達(dá)到觀(guān)測(cè)信號(hào)維數(shù)的一半時(shí)（即k×d=），IBSL0算法仍然具有不錯(cuò)的估計(jì)性能。然而，本文沒(méi)有從理論上證明IBSL0算法是否能精確重構(gòu)，今后的工作主要包括2個(gè)方面：（1）給出IBSL0精確的重構(gòu)條件；（2）進(jìn)一步研究在塊稀疏度或者觀(guān)測(cè)值增加的情況下，該算法與其他算法的重構(gòu)成功率、運(yùn)行時(shí)間及信噪比的比較。

［1］ Candes E.An Introduction to Compressive Sampling［J］. IEEE Signal Processing Magazine，2008，25（2）：21-30.

［2］ Chen Shaobing，Donoho D L，Saunders M A.Atomic Decomposition by Basis Pursuit［J］.SIAM Journal on Scientific Computing，1999，20（1）：33-61.

［3］ Tropp JA，Gilbert A C.Signal Recovery from Random Measurements via Orthogonal Matching Pursuit［J］.IEEE Transactions on Information Theory，2007，53（12）：4655-4666.

［4］ Dai Wei，Milenkovic O.Subspace Pursuit for Compressive Sensing Signal Reconstruction［J］.IEEE Transactions on Information Theory，2009，55（5）：2230-2249.

［5］ Mohimani H，Babaie-Zadeh M，Jutten C.A Fast Approach for Over-complete Sparse Decomposition Based on Smoothed l0Norm［J］.IEEE Transactions on Signal Processing，2009，57（1）：289-301.

［6］ Stojnic M，Parversh F，Hassibi B.On the Reconstruction of B lock-sparse Signals with an Optional Number of Measure-ments［J］.IEEE Transactions on Signal Processing，2009，57（8）：3075-3085.

［7］ Eldar Y C，Kuppinger P，Bolcskei H.Compressed Sensing of Block-sparse Signals：Uncertainty Relations and Efficient Recovery［J］.IEEE Transactions on Signal Processing，2010，58（6）：3042-3054.

［8］ Wang Yao，Wang Jianjun，Xu Zongben.On Recovery of Block-sparse Signals via Mixed l2/lq（0＜q≤1）Norm Minimization［J］.EURASIP Journal on Advances in Signal Processing，2013，76（1）：1-17.

［9］ 付 寧，曹離然，彭喜元.基于子空間的塊稀疏信號(hào)壓縮感知重構(gòu)算法［J］.電子學(xué)報(bào)，2011，39（10）：2339-2342.

［10］ 田鵬武，康榮宗，于宏毅.非均勻塊稀疏信號(hào)的壓縮采樣與盲重構(gòu)算法［J］.電子與信息學(xué)報(bào)，2013，35（2）：445-450.

［11］ Ham idi-Ghalehjegh S，Babaie-Zadeh M，Jutten C.Fast Block-sparse Decomposition Based on SL0［C］// Proceedings of the 9th International Conference on Latent Variable Analysis and Signal Separation.Berlin，Germ any：Springer，2010：426-433.

［12］ EldarY，Mishali M.Robust Recovery of Signals from a Structured Union of Subspaces［J］.IEEE Transactions on Information Theory，2009，55（11）：5302-5316.

編輯顧逸斐

Block Sparse Signal Reconstruction Algorithm Based on Improved Smoothed l0Norm

QI Rui1a，2，LI Hongwei1b，ZHANG Yujie1b
（1a.Institute of Geophysics and Geomatics；1b.School of Mathematics and Physics，China University of Geosciences，Wuhan 430074，China；2.School of Science，Naval University of Engineering，Wuhan 430033，China）

Smoothed l0norm（SL0）algorithm utilizes a sequence of smoothed Gaussian function with parameter to approximate the l0norm，which can be used efficiently for the compressive sensing reconstruction.Block-sparse signal is a typical sparse signal whose non-zero coefficients occur in a few blocks.This paper proposes a block sparse signal reconstruction based on improved SL0 algorithm with respect to the block sparse signals.The smoothed Gaussian function is substituted by inverse tangent function，and the convergence equality is further improved by optimizing the decreasing factor.Simulation results show that，compared with Block Smoothed l0Norm（BSL0）algorithm，Smoothed l0Norm（SL0）algorithm，and Orthogonal Matching Pursuit（OMP）algorithm，the proposed method has better robustness and higher Signal to Noise Ratio（SNR）.

compressive sensing；block-sparse；Smoothed l0Norm（SL0）；signal reconstruction

祁 銳，李宏偉，張玉潔.基于改進(jìn)光滑l0范數(shù)的塊稀疏信號(hào)重構(gòu)算法［J］.計(jì)算機(jī)工程，2015，41（11）：294-298.

英文引用格式：Qi Rui，Li Hongwei，Zhang Yujie.Block Sparse Signal Reconstruction Algorithm Based on Improved Smoothed l0Norm［J］.Computing Engineering，2015，41（11）：294-298.

1000-3428（2015）11-0294-05

A

TN911

10.3969/j.issn.1000-3428.2015.11.050

國(guó)家自然科學(xué)基金資助項(xiàng)目（61071188）；中央高?；究蒲袠I(yè)務(wù)費(fèi)專(zhuān)項(xiàng)基金資助項(xiàng)目（CUGL130247）；海軍工程大學(xué)青年基金資助項(xiàng)目（HGDQNEQJJ15004）。

祁 銳（1981-），男，講師、博士研究生，主研方向：盲信號(hào)處理，壓縮感知；李宏偉，教授、博士；張玉潔，講師、博士。

2014-10-28

2014-12-21 E-m ail：qqr0425@163.com