面向压缩感知的块稀疏度自适应迭代算法
付 宁,乔立岩,曹离然
(哈尔滨工业大学自动化测试与控制系,哈尔滨工业大学3033信箱,黑龙江哈尔滨150080)
摘 要: 块稀疏信号是一种典型的稀疏信号,目前在块稀疏信号的压缩感知问题中,大多数信号重构算法要求信号的块稀疏度已知且算法复杂度高.针对实际应用中信号块稀疏度未知的情况,提出了一种块稀疏度自适应迭代算法,用于信号重构.首先,该算法初始化一个块稀疏度,其值按设定步长进行增加.对每一个块稀疏度的迭代,算法都会找到信号支撑块的一个子集,并修正更新上一次找到的信号支撑块,最后找到信号的整个支撑块,从而重构出源信号.该算法不需要信号的块稀疏度作为先验知识,而且算法复杂度低.仿真实验表明,该算法的重构概率较已有大多数块稀疏信号重构算法的重构概率高,在块稀疏信号的压缩感知问题中具有实际意义.
关键词: 压缩感知;块稀疏;自适应;重构概率
中图分类号: TN911 文献标识码: A 文章编号: 0372 2112(2011)3A 075 05
Block Sparsity Adaptive Itera tion Algorithm for Compressed Sensing
FU Ning,QIAO Li yan,C AO Li ran
(De part me nt o f Automatic Test and Control ,Harbin Institute o f Technology,P.O.Bo x 3033,Harbin,He ilongjiang ,150080China )
Abstract: Block spar s e signal is a typical sparse signal.Among the block sparse signal problems for compressed sensing,the most ex isting recovery algorithms require block sparsity as prior know ledge and have a high complex ity.In this paper,a block s par sity adaptive iteration algorithm for compressed sensing has been proposed when the blo ck sparsity is unknown.Firstly ,the algorithm initializes a blo ck s parsity which w ill increase by steps.Subsequently,for each block s parsity,a sub set of the signal support set can be determi ned by the algorithm,which updates the previous one,until the exact support set is acquired,finally the original signal can be reconstructed through the exact support set.This algorithm doesn t require blo ck sparsity as prior know ledge and has a low com plexity.Simulation results demonstrate its high recovery probability than most existing algorithms,which makes it a promising for practical block s parse signal compressed s ensing task.
Key words: compressed sensing ;block sparse;adaptive;recovery probability
1 引言
压缩感知(Co mpressed Sensing,CS)是2006年由
Cand s,Romber g,Tao 和Donoho 等人提出的一种新的信号采样理论[1,2].CS 理论指出:当信号具有稀疏特性时,可以通过远小于信号长度的少量观测值来精确重构源信号.CS 理论将信号的采样和压缩结合成一步对信号进行编码,在一定程度上打破了传统奈奎斯特采样定理的极限,减轻了硬件处理的负担.
标准的CS 框架是在未知向量满足稀疏性的条件下,从欠定方程组中得到未知向量的恢复.自CS 理论建立起来后,已经提出了很多有效而精确的重构算法,比较有代表性的包括针对线性规划的基追踪(Basis Pur sui t,BP)算法[3]以及贪婪算法[4~6]等.但是标准的CS 框架下没有考虑到信号的结构,对于某些类型的稀疏信
号,标准CS 理论下的算法重构概率低.文献[7]指出了
实际中的一种典型稀疏信号 块稀疏信号(Block sparse Signal),即,信号值不为零的地方是成块出现的.基于信号的这种特性,Eldar 等人进行了深入研究,建立了块稀疏信号下的压缩感知理论框架,并提出了一系列重构算法.文献[8]中指出,块稀疏信号的重构可以看成是一个混合l 2/l 1范数的优化问题(Mixed l 2/l 1 norm Op ti mization Progra m,L OP T),并通过标准凸优化的软件包可以求解,此算法可以看出是BP 算法的在块稀疏信号中的拓展.由于基于BP 算法的复杂度高,文献[9]又将匹配追踪(Matching Pursuit,MP)、正交匹配追踪(Orthogo nal Matching Pursuit,OMP)拓展到块稀疏信号中,提出了块稀疏匹配追踪(Block MP,BMP)以及块稀疏正交匹配追踪(Block OMP,BOMP).由于L OPT 、B MP 以及BOMP 利用了信号的块稀疏特性,把信号的每个块都当成一个
收稿日期:2010 11 10;修回日期:2011 01 05
第3A 期2011年3月电 子 学 报ACTA ELECTRONICA SINICA Vol.39 No.3A
Mar. 2011
整体进行运算,因此块稀疏度比传统意义下的稀疏度更小,文献中的实验表明这些算法较传统意义下的稀疏重构算法有更好的效果.但是,这些算法复杂度较高且要求信号的块稀疏度作为先验知识,然而,块稀疏度在实际信号的压缩感知问题中是未知的,获取并不容易.
针对实际块稀疏信号中块稀疏度未知的特点,本文提出了一种块稀疏度自适应迭代算法.该算法只需初始化一个块稀疏度,并设定一个步长进行增加,对每一个块稀疏度,算法都会找到信号支撑块的一个子集,并利用回溯思想修正更新上一次找到的信号支撑块.最终在迭代收敛条件满足的情况下,找到整个信号支撑块,从而重构出源信号.仿真实验表明,本文算法有效,且重构概率有了提高.
2 压缩感知以及块稀疏信号
2.1 压缩感知
信号的稀疏表示是CS 理论应用的前提,CS 理论是对传统编解码思想的重要突破,CS 理论将采样和压缩结合成一步对信号进行编码,利用信号的稀疏性,对信号以远低于奈奎斯特采样率进行非自适应的测量编码,进行传输后通过一定的算法进行解码重构.
为使问题简化,考虑稀疏度为K 的离散实信号x :
x R N 1, T x 0 K N (1)
其中N 为信号长度,
表示信号的0 范数,即信号
值不为0的个数. 为信号的稀疏基.可以找到它的m 次测量:
y = x (2)
其中 R m N 为与 不相关的测量矩阵,且m arg min T x 0, s.t. y = x (3) 2.2 块稀疏信号理论 考虑另外一种类型的稀疏信号 块稀疏信号(Block sparse Signal ),其定义如下[7]: x =[x 1, ,x d x T [1] ,x d +1, ,x 2d x T [2] , ,x N -d +1, ,x N x T [M] ]T (4) 其中N =Md,x [l],(l =1, ,M )为一子块.为简化问题,假设x [l ]等长.如果向量x 称为块K 稀疏信号,则x [l]至多有K 个不为0的l 2范数.当d =1时,块稀疏即退化成式(1)所描述的一般意义下的稀疏. 实际中块稀疏信号的形式是很多的,如多波段信 号(multi band signal)、DNA 阵列(DNA microarray)、雷达脉冲信号(radar pulse signal)以及多测量向量问题(mult i ple measure me nt vector problem,MMV)等等[9].研究这些具有特定结构的稀疏信号重构算法具有重要意义. 2.3 重构算法 对于压缩感知中块稀疏信号的重构问题,文献[8,9]提出了三种典型算法,目前块稀疏信号的重构主要基于这三种方法,下面给予简单介绍. (1)混合l 2/l 1范数优化(Mixed l 2/l 1 norm Optimiza tion Progra m,L OP T )算法.该算法主要是解决下面的优化问题[8]: min M l=1 x [l ] 2, s.t. y = x (5) 然后可以转化为一个凸优化工具包(c onvex second order cone program,SOCP)能解决的二次锥规划问题[10]: min M l=1 t l s.t. y = x t l x [l ] 2, t l 0,1 l M (6) (2)块稀疏正交匹配追踪(Bloc k spa rse Orthogonal Matching Pursuit,BOMP )算法.该算法主要步骤如下[9] : (a)初始化残差r 0=y ,在第l 步(l 1)迭代的时候,选择与残差r l -1最匹配的块: i l =a rg ma x i (mean ( T [i ]r l - 1 ))(7) 其中mean 表示求均值. (b)确定i l 后,寻找估计信号x. x = + I y (8) 其中I 表示i j 的集合,1 j l. (c)更新残差: r l =y - I x (9) 直到r l 的l 2范数小于设定的迭代误差时,算法结束. (3)块稀疏匹配追踪(Bloc k sparse Ma tching Pursuit,BMP)算法[9],该算法第一步和BOMP 相同,但BMP 通过下式更新残差: r l =r l -1- [i l ] +[i l ]r l -1 (10) BMP 更新残差没有采用正交化的思想.下面给出BOMP 和BMP 算法框图. 从算法框图可以看出,算法主要由三部分构成:相关测试、更新信号支撑块、更新残差.其中算法在每次相关测试时只找到信号支撑的一个块,对于块稀疏度为K 的信号,至少要进行K 次迭代才能恢复源信号,要 76 电 子 学 报2011年 求块稀疏度K 已知;且每次迭代找到信号支撑的一个块后,便不再改变,对于错误的支撑块,算法没有修复能力,导致信号的重构概率不高. 3 本文算法 针对实际中信号块稀疏度未知的特点,本文提出 了一种块稀疏度自适应迭代算法,主要思想是通过初始化块稀疏度,并随步长进行增加,对每一个块稀疏度的迭代,算法都会找到信号支撑块的一个子集,并利用回溯思想修正更新上一次找到的支撑块,最后找到信号的整个支撑块,从而达到重构源信号的目的.算法框图如下 : 根据框图,下面对此算法的具体步骤进行详细阐述. 3.1 算法步骤 (1)设定算法输入:测量矩阵 R m N ,观测信号y ,初始化块稀疏度k,算法迭代误差 ,分块向量G,分块向量的确定如下,对于式(4)描述的块稀疏信号,分块向量为: G =[1, ,1d ,2, ,2d , ,M, ,M d ]T (11) 并初始化残差值r 0=y ,初始化信号支撑块t 0= ,步长step =1,信号支撑块大小S =k,重构向量^x =0; (2)初级测试:第l 次迭代时,l {1,2, ,M },选择与残差r l -1最匹配的子空间i l ,具体操作为: i l =a rg max S (mean ( T [i ]r l -1)) (12) 即测量矩阵的每一块与残差进行内积操作后,取绝对值后再平均,最后选择最大的S 个值的标号赋值给i l ,这里的序号对应分块向量G 中的分组号(1,2, ,M ); (3)回溯: ^ t l =t l -1 i l (13) (4)终级测试:计算信号支撑块的估计t l : t l =arg max S (mean ( +^ t l y ))(14) 其中 + ^t l = T ^t l ^t l -1 T ^t l 为 ^t l 的伪逆. ^t l 为^t l 对应的 测量矩阵 的列向量组成的矩阵.且t l ^t l . (5)计算残差r l : r l =y - t l ( + t l y ) (15) (6)若r l 2 r l -12,则:step =step +1;S =step S,返回步骤(2),否则直接返回步骤(2). (7)当迭代次数大于分组数(即分块向量G 中的最 大值)或者残差小于算法迭代误差 时,迭代结束.输出重构向量^x ,满足: ^x = +t l y (16) 3.2 算法复杂度分析 算法复杂度方面,由算法原理知本文算法的复杂度和初始化块稀疏度有关,为直观地说明本文算法复杂度大小,采用文献[5]中的实验测试方法.实验设置如下: (1)测量矩阵 R m N 为高斯分布,m =256,N =512,分块大小d =4.其中块稀疏度K =1,2, ,30.随机选定K 个块,分别在这K 个块上赋值得到所需的仿真测试信号x (幅度采用高斯分布或0 1信号). (2)分别设置k =1或k =K 下两种情况,对每个块稀疏度K ,算法精确重构200次.得到算法的平均迭代次数. 图3、图4分别给出了算法设置k =1和k =K 时平均迭代次数随信号块稀疏度的变换曲线: 图中表明,当k =1时,本文算法平均迭代次数满 足n it =O(K).当k =K 时,平均迭代次数满足n i t =O (log K),所以在精确重构的条件下,本文算法的复杂度可以较好地估计.由于本文算法的复杂度主要集中在初级测试的相关最大化(Correlation Maxi mization,CM )操 作上[5] ,算法每次迭代进行CM 运算需要m N 次乘法,因此算法总的复杂度可以控制在O (mN log K )和 77 第 3A 期付 宁:面向压缩感知的块稀疏度自适应迭代算法 O (mNK)之间. 比较其他三种算法,L OPT 是基于线性规划(Linear Progra m,LP )的算法,其复杂度与BP 算法相当,为O (N 3 ),BMP 和BOMP 属于贪婪算法,BO MP 算法需要K 次迭代才能重构源信号,复杂度与O MP 算法相当,为O (Km N ),而BMP 比BO MP 少施密特正交化这一步,所以其复杂度也可以控制在O(Km N )以内.因此在复杂度方面,本文算法比L OP T 、BMP 和BO MP 算法均有一定的优势. 4 实验验证 本实验将本文算法和L OPT 、BMP 、BOMP 算法分别应用于块稀疏信号的重构,计算每一种方法的重构概 率进行对比. 仿真实验按以下步骤进行: (1)随机产生一个高斯分布测量矩阵 R m N ,给定分块大小d 以及块稀疏度K ,随机选定K 个块,分别在这K 个块上赋值得到所需的仿真测试信号(幅度采用高斯分布或0 1信号). (2)通过式(2)得到观测信号y = x,利用每种重构算法得到重构信号^x ,若^x -x 2< 10 -5 则重构成 功. (3)对每种重构算法运行500次,并计算重构概率.本实验过程中,分别采用幅值为高斯分布的信号和0 1的二值信号进行实验.测量矩阵行数m =80,列数N =160,分块大小d =8,源信号的块稀疏度K =1,2, ,12,计算每种算法在不同K 值下的重构概率,并绘制重构概率随块稀疏度的变化曲线. 实验结果如图5所示. 其中图5(a)为幅值为高斯分布的信号实验结果,图5(b)为0 1的二值信号实验结果.从图中可见,虽然本文不需要已知块稀疏度,但无论对于哪类块稀疏信号,本文算法的重构概率比其他三种方法都有提高;尤其对于0 1的二值信号,本文算法的重构概率有显著提高.这是因为算法使用了回溯思想,在这种思想框架 下,算法首先寻找到与空间 t l 最接近的块,在下一次迭代时通过回溯又得到相同数量的块,然后通过式(14)的最小均方准则判定,若上一次迭代寻找到的块到空间 t l 的距离比其他S 个块更大,则算法会将这些块排除到信号支撑块外.因此本文算法具有修正信号支撑块的作用,所以重构概率较BMP 和BOMP 算法更高. 5 结论 本文提出了一种新的面向压缩感知的块信号重构算法 块稀疏度自适应迭代算法.此方法通过初始化块稀疏度,并在每次迭代之后块稀疏度随步长增加,利用回溯思想不断地估计和更新源信号的支撑块,最终找到源信号的整个支撑块,重构出源信号.该算法不需要信号的块稀疏度作为先验知识,且复杂度低.实验表明,对于压缩感知问题中的块稀疏信号重构,其重构概率较高,对于块稀疏信号的处理具有实际意义. 参考文献 [1]E Cand s,J Romberg,Terence Tao.Robust uncertainty princi ples :exact signal recons truction from highly incomplete fre quency information [J].IEEE Trans on Information Theory,2006,52(2):489-509. [2]D L https://www.wendangku.net/doc/207992714.html,pressed sensing [J].IEEE Trans on Informa tion Theory.2006,52(4):1289-1306. [3]E Cand s,Terence Tao.Decoding by linear p ro gramming [J]. IEEE Trans on Information Theory ,2005,51(12):4203-4215. [4]J A Tropp,A C Gilbert.Signal reco very from random measure ments via orthogonal matching pursuit[J].IEEE Trans on In formation Theory,2007,53(12):4655-4666. [5]W Dai,O Milenkovic.Subspace pursuit for compressive sensing signal reconstruction [J].IEEE Trans on Information Theory,2009,55(5):2230-2249. [6]T T Do ,L Gan,N Nguyen,T D T ran.Sparsity adaptive match ing pursuit algorithm for practical compress ed sensing [A].In Proceedings of the 42th A silomar Conference on Signals,Sys tems,and Computers[C ].Pacific Gro ve,California,2008.581-587. [7]R G Baraniu k,V Cevher,M F Duarte,C Hegde.M odel based compressive s ensing [J].IEEE Trans on Information Theory,2010,56(4):1982-2001. [8]Y C Eldar,M Mishali.Robust recovery of signals from a struc tured union of subspaces[J].IEEE Trans on Information Theo ry,2009,55(11):5302-5316. [9]Y C Eldar,P Kuppinger ,H B https://www.wendangku.net/doc/207992714.html,pressed sensing of block sparse signals:uncertainty relations and efficient recovery [J].IEEE Trans on Signal Processing,2010,58(6):3042- 78 电 子 学 报2011年 3054. [10]M Lobo,L Vandenberghe,S Bo yd.Applications of second or der cone pro gramming[J].Linear Algebra and i ts Applica tions,1998,284(1-3):193-228. 作者简介 付 宁 男,1979年出生于河南省鹤壁市, 博士,哈尔滨工业大学自动化测试与控制系讲 师,主要研究方向为压缩感知理论、盲信号处理、 自动测试技术等. E mail:funi nghit@https://www.wendangku.net/doc/207992714.html, 乔立岩 男,1973年出生于黑龙江省哈尔滨市,回族,博士,哈尔滨工业大学自动化测试与控制系教授,主要研究方向为进化算法、模式识别、故障诊断技术等. E mail:qi aoliyan@https://www.wendangku.net/doc/207992714.html, 曹离然 男,1987年出生于四川省内江市,在读硕士研究生,主要研究方向为压缩感知算法、盲信号处理等. E mail:liran4538@https://www.wendangku.net/doc/207992714.html, 79 第 3A 期付 宁:面向压缩感知的块稀疏度自适应迭代算法