基于分治试探的盲自适应匹配追踪重构算法

doi:10.3969/j.issn.1000-436x.2013.04.022

摘要/Abstract

摘要：

压缩感知是一种针对稀疏可压缩信号进行压缩采样的信号处理新方法，针对现有稀疏度探测方法中探测次数较多的问题，基于分治思想提出了盲稀疏度自适应匹配追踪（BSAMP）算法，首先分治试探信号稀疏度，使得其估计值快速逼近真实值，然后通过自适应分组并扩充信号支撑域的方法，快速筛选出有效支撑，并通过弱匹配剪枝得到重构信号。可以在信号稀疏度未知的情况下，快速估计出信号的稀疏度并精确重构出原信号。仿真实验表明，在相同条件下，该算法的重构时间比其他同类算法短，且重构概率也大于其他同类算法。

关键词: 信号处理, 压缩感知, 盲稀疏度, 自适应重构

Abstract:

Compressed sensing is a novel signal processing theory that it introduces a novel way of acquiring compressible signals,the test times of existing sparsity trial and error algorithms were always large.The novel algorithm,blind sparsity adaptive matching pursuit (BSAMP) was proposed,could recover the original signal fast in the case of unknown sparsity.Firstly,the range of sparsity was determined,and each time half of values in current range were eliminated by trial and error test.Secondly,the number of atoms was twice the sparsity,which was united with the set of signal approximation support (got by last iteration) and then reconstructed the signal by solving least-squares problems.Last but not least,the least-squares approximation was pruned by weakly matching for next iteration.The results of simulation show that the novel algorithm can reconstruct signal faster and get larger recovery probability than other similar algorithms in the same conditions.

Key words: signal processing, compressed sensing, blind sparsity, adaptive reconstruction

田文飚,付争,芮国胜. 基于分治试探的盲自适应匹配追踪重构算法[J]. 通信学报, 2013, 34(4): 180-186.

Wen-biao TIAN,Zheng FU,Guo-sheng RUI. Blind adaptive matching pursuit algorithm for signal reconstruction based on sparsity trial and error[J]. Journal on Communications, 2013, 34(4): 180-186.

图/表 6

图1

图2

图3

图4

图5

图6

参考文献 22

[1]	RICHARD G . Baraniuk,compressive sensing[J]. IEEE Signal Processing Magazine, 2007,24(4): 118-121.
[2]	DONOHO D L . Compressed sensing[J]. IEEE Trans on information Theory, 2006,52(4): 1289-1306.
[3]	石光明, 刘丹华, 高大化等. 压缩感知理论及其研究进展[J]．电子学报， 2009,37(5):1070-1081. SHI G M , LIU D H , GAO D H , et al. Advances in theory and application of compressed sensing[J]. Acta Electronica Sinica, 2009,37(5):1070-1081.
[4]	孙林慧, 杨震, 叶蕾．基于自适应多尺度压缩感知的语音信号压缩与重构[J]．电子学报, 2011,39(1):40-45. SUN L H , YANG Z , YE L . Speech compression and reconstruction based on adaptive multiscale compressed sensing theory[J]. Acta Electronica Sinica, 2011,39(1):40-45.
[5]	顾彬, 杨震, 胡海峰．基于压缩感知信道能量观测的协作频谱感知算法[J]．电子与信息学报, 2012,34(1):14-19. GU B , YANG Z , HU H F . Cooperative wideband spectrum sensing algorithm based on compressed sensing channel energy measurements[J]. Journal of Electronics ＆ Information Technology, 2012,34(1):14-19.
[6]	周小星, 王安娜, 孙红英等. 基于压缩感知过程的语音增强[J]．清华大学学报(自然科学版), 2011,51(9):1234-1238. ZHOU X X , WANG A N , SUN H Y , et al. Speech enhancement based on compressive sensing[J]. Journal of Tsinghua Univ(Sc ＆ Tech), 2011,51(9):1234-1238.
[7]	干宗良，齐丽娜，唐贵进等．泛在网络中基于压缩感知的Wyner-Ziv 空域可分级视频编码[J]．通信学报， 2010.31(11):41-48. GAN Z L , QI L N , TANG G J , et al. Wyner-Ziv spatial scalable video coding using compressive sensing in ubiquitous networks[J]. Journal on Communications, 2010.31(11):41-48.
[8]	MALLAT S , ZHANG Z . Matching pursuits with time-frequency dictionaries[J]. IEEE Trans on Signal Processing, 1993,41(12): 3397-3415.
[9]	TROPP J A , GILBERT A C . Signal recovery from random measurements via orthogonal matching pursuit[J]. IEEE Transactions on Information Theory, 2007,53(12): 4655-4666.
[10]	DONOHO D L , TSAIG Y , DRORI I , et al. Sparse Solution of Underdetermined Linear Equations by Stagewise Orthogonal Matching Pursuit[R]. Technique Report, 2006.
[11]	NEEDELL D , TROPP J A . CoSaMP:iterative signal recovery from incomplete and inaccurate samples. Communications of the ACM, 2010,53(12): 93-100.
[12]	DO T T , GAN L , NGUYEN N S . Sparsity adaptive matching suit algorithm for practical compressed sensing[A]. Asilomar Conference on Signals,Systems and Computers[C]. Pacific Grove,California, 2008. 581-587.
[13]	CHEN S S , DONOHO D L , SAUNDERS M A . Atomic decomposition by basis pursuit[J]. SIAM Journal on Scientific Computing, 1998,20(1): 33-61.
[14]	BLUMENSATH T , DAVIES M E . Iterative thresholding for sparse approximation[J]. Fourier Anal, 2008,14(5-6): 629-654.
[15]	GILBERT A , STRAUSS M , TROPP J , et al. Algorithmic linear dimension reduction in the 1 norm for sparse vectors[EB/OL]. .
[16]	GILBERT A C , STRAUSS M J , TROP J A , et al. One sketch for all:fast algorithms for compressed sensing[A]. Proceedings of the 39th Annual ACM Symposium on Theory of Computin[C]. New York,USA, 2007. 237-246.
[17]	DAI W , MILENKOVIC O . Subspace pursuit for compressive sensing signal reconstruction[J]. IEEE Trans on Information Theory, 2009,55(5): 2230-2249.
[18]	张宗念, 黄仁泰, 闫敬文．压缩感知信号盲稀疏度重构算法[J]．电子学报， 2011,39(1):18-22. ZHANG Z N , HUANG R T , YAN J W . A blind sparsity reconstruction algorithm for compressed sensing signal[J]. Acta Electronics Sinica, 2011,39(1):18-22.
[19]	刘亚新, 赵瑞珍, 胡绍海等．用于压缩感知信号重建的正则化自适应匹配追踪算法[J]．电子与信息学报, 2010,32(11):2713-2717. LIU Y X , ZHAO R Z , HU S H , et al. Regularized adaptive matching pursuit algorithm for signal reconstruction based on compressive sensing[J]. Journal of Electronics ＆ Information Technology, 2010,32(11):2713-2717.
[20]	杨成, 冯巍, 冯辉等．一种压缩采样中的稀疏度自适应子空间追踪算法[J]．电子学报, 2010,38(8):1914-1917. YANG C , FENG W , FENG H , et al. A sparsity adaptive subspace pursuit algorithm for compressive sampling[J]. Acta Electronica Sinica, 2010,38(8):1914-1917.
[21]	HUANG H , MAKUR A . Backtracking-based matching pursuit method for sparse signal reconstruction[J]. IEEE Signal Processing Letters, 2011,18(7): 391-394.
[22]	CANDES E J . The restricted isometry property and its implications for compressed sensing[J]. Compte Rendus De l'Academie Des Sciences, 2008,Series I(346): 589-592.