祁 銳，李宏偉，張玉潔

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

·開發(fā)研究與工程應用·

基于改進光滑l0范數(shù)的塊稀疏信號重構算法

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

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

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

壓縮感知；塊稀疏；光滑l0范數(shù)；信號重構

1 概述

文獻［1］提出一種新的信號采樣理論——壓縮感知（Compressed Sensing，CS）。CS在采樣的同時完成了信號的壓縮，它可以突破Nyquist采樣定律的限制對信號進行采樣，并完成精確重構。

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

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

2 壓縮感知與塊稀疏信號

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

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

2.2 塊稀疏信號壓縮感知模型

塊稀疏信號壓縮感知模型如下：

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

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

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

2.3 重構算法

目前塊稀疏信號的重構主要基于以下4種算法：

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

文獻［12］進一步證明了在滿足一定條件下，可以用式（5）精確地恢復任意的塊稀疏源信號。

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

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

其中：

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

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

3 本文算法

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

因此，定義：

將SL0算法應用到塊稀疏信號的重構問題中［11］，定義：

由于塊稀疏信號重構問題可以轉化為如下的優(yōu)化問題：

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

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

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

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

具體算法流程如下：

Step1 初始化

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

Step2 for j=1，2，…，J

（1）σ=σj，當σ＞σmin時；

（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。

算法說明：

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

4 仿真實驗與結果分析

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

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

在以下實驗中，取源信號維數(shù)m=1 000，觀測信號維數(shù)n=400，內循環(huán)迭代次數(shù)L=3，μ=2，σmin= 0.000 1。用信噪比（Signal to Noise Ratio，SNR）sSNR來評價估計效果，SNR定義為：

實驗1 考查分塊大小d變化時，IBSL0算法在不同噪聲方差情況下的信噪比變化情況。塊稀疏信號的稀疏度為k（即N塊中至多k塊非零，源信號的整體稀疏度為k×d），改變k和d（塊大?。┑娜≈?，分為以下2種情況：

（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分別對應k×d=100，k×d=200=n/2（即源信號的總體稀疏度達到觀測信號維數(shù)的一半），分塊從小變大時，IBSL0算法在噪聲方差逐漸變大時的信噪比變化情況?？梢钥闯觯琁BSL0算法的信噪比隨著噪聲方差變大慢慢降低，當且塊大小為20時，IBSL0算法的信噪比約為35 dB，總體來說具有不錯的抗噪性能，特別是當k×d=時，IBSL0算法仍然具有不錯的估計效果。

圖1 噪聲方差變大時IBSL0算法估計性能1

圖2 噪聲方差變大時IBSL0算法估計性能2

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

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

圖3 k×d=100時算法性能比較

圖4 k×d=200時算法性能比較

5 結束語

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

［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］ 付 寧，曹離然，彭喜元.基于子空間的塊稀疏信號壓縮感知重構算法［J］.電子學報，2011，39（10）：2339-2342.

［10］ 田鵬武，康榮宗，于宏毅.非均勻塊稀疏信號的壓縮采樣與盲重構算法［J］.電子與信息學報，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

祁 銳，李宏偉，張玉潔.基于改進光滑l0范數(shù)的塊稀疏信號重構算法［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

國家自然科學基金資助項目（61071188）；中央高?；究蒲袠I(yè)務費專項基金資助項目（CUGL130247）；海軍工程大學青年基金資助項目（HGDQNEQJJ15004）。

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

2014-10-28

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