基于原子库树状结构划分的诱导式信号稀疏分解

Journal of Systems Engineering and Electronics ›› 2009, Vol. 31 ›› Issue (8): 1976-1981.

基于原子库树状结构划分的诱导式信号稀疏分解

刘丹华¹, 石光明¹, 高大化^1,2, 周佳社¹

1. 西安电子科技大学电子工程学院, 陕西, 西安, 710071;
2. 空军工程大学理学院, 陕西, 西安, 710051

收稿日期:2008-04-03 修回日期:2008-08-08 出版日期:2009-08-20 发布日期:2010-01-03
作者简介:刘丹华(1978- ),女,博士研究生,主要研究方向为信号/图像稀疏分解、图像压缩、信号处理.E-mail:dhliu@mail.xidian.edu.cn
基金资助:
国家自然科学基金(60672125);国家自然基金委员会与微软亚洲研究院联合项目(60776795)资助课题

Guiding method of signal sparse decomposition based on tree-structured partition of atom dictionary

LIU Dan-hua¹, SHI Guang-ming¹, GAO Da-hua^1,2, ZHOU Jia-she¹

1. School of Electronic Engineering, Xidian Univ., Xi'an 710071, China;
2. School of Science, Air Force Engineering Univ., Xi'an 710051, China

Received:2008-04-03 Revised:2008-08-08 Online:2009-08-20 Published:2010-01-03

摘要/Abstract

摘要： 针对以往提出的稀疏分解算法仅从原子库构造方面或分解方式角度对算法进行各种改进且计算复杂度高的问题,提出了一种诱导性塔式分解算法.该算法首先将原子库逐层划分,得到一个树状层次结构的原子库,然后在迭代过程中利用划分所得树状结构有目的、有导向性地指引信号分解方向,从而一劳永逸地加快了信号分解速度,极大地降低了算法的计算复杂度.实验结果表明,与经典的匹配追踪(matching pursuit,MP)算法相比,本文算法在同等稀疏度且逼近误差接近的情况下,计算量大约降低为MP算法的1/40,计算时间降低为MP算法的1/100左右.仿真实验证明了该算法的有效性.

Abstract: To overcome the deficiency of traditional sparse decomposition algorithm,in which the performance improvement is merely made either by improving the mode of constructing atom dictionary or by decomposing method,and it also has a high calculative complexity,a new guiding pyramidal algorithm of sparse decomposition is presented.The algorithm firstly divides the atom dictionary into several subsets by its characteristics and forms a tree structure atom dictionary after several layer-by-layer partition of the atom set.Then the decomposing of signals can be purposefully performed along the course charted by the tree structure at each iteration and the decomposing speed is greatly increased,and the calculative complexity is sharply decreased.Experiment results show that the calculating amount of the new algorithm is only about 1/40 of MP algorithm,and the computing time 1/100 of MP algorithm,under the condition of the same sparsity and similar approximation error.The simulation results indicate that the presented method is efficient.

中图分类号:

TN911.7

刘丹华, 石光明, 高大化, 周佳社. 基于原子库树状结构划分的诱导式信号稀疏分解 [J]. Journal of Systems Engineering and Electronics, 2009, 31(8): 1976-1981.

LIU Dan-hua, SHI Guang-ming, GAO Da-hua, ZHOU Jia-she. Guiding method of signal sparse decomposition based on tree-structured partition of atom dictionary [J]. Journal of Systems Engineering and Electronics, 2009, 31(8): 1976-1981.

参考文献

[1] Mallat S,Zhang Z.Matching pursuit with time-frequency dictionaries[J].IEEE Trans.on Signal Processing,1993,41(12):3397-3415.
[2] 尹忠科,解梅,王建英.基于稀疏分解的图像去噪[J].电子科技大学学报,2006,35(6):876-878.
[3] 张文耀.基于匹配跟踪的低位率语音编码研究[D].北京:中国科学院研究生院软件研究所,2002.
[4] Arthur P L,Philipos C L.Voiced/unvoiced speech discrimination in noise using gabor atomic decomposition[C]//Proc.International Conference on Acoustics,Speech and Signal Processing,Hong Kong:Institute of Electrical and Electronics Engineers Inc,2003,1:820-823.
[5] 邹红星,周小波,李衍达.时频分析:回溯与前瞻[J].电子学报,2000,28(9):78-84.
[6] 傅霆,尧德中.稀疏分解的加权迭代方法及其初步应用[J].电子学报,2004,32(4):567-570.
[7] 王建英,尹忠科,张春梅.信号与图像的稀疏分解及初步应用[M].成都:西南交通大学出版社.2006.
[8] Donoho D L.Compressed sensing[J].IEEE Trans.on Informarion Theory,2006,52(4):1289-1306.
[9] Emmanuel Candès.Compressive sampling[C]//International Congress of Mathematics,Madrid,Spain,2006:1433-1452.
[10] Temlyakov V N.Greedy algorithms and m-term approximation[J].Journal of Approx.Theory,1999:117-145.
[11] Tropp J A.Greed is good:algorithmic results for sparse ap-proximation[J].IEEE Trans.on Information Theory,2003,50(11):2231-2242.
[12] Pati Y C,Rezaiifar R,Krishnaprasad P S.Orthogonal matching pursuits:recursive function approximation with applications to wavelet decomposition[C]//Conference Record of the 27th Asilomar Conference on Signals,Systems & Computers,IEEE,Los Alamitos,CA,USA,1993,1:40-44.
[13] Gribonval R,Vandergheynst P.On the exponential convergence of matching pursuits in quasi-incoherent dictionaries[J].IEEE Trans.on Information Theory,2006,52(1):255-261.
[14] Temlyakov V N.Nonlinear methods of approximation[J].Found.Comput.Math.,2003,3(1):33-107.
[15] Tropp J A,Gilbert A C.Signal recovery from random measurements via orthogonal matching pursuit[J].IEEE Trans.on In formation Theory,2007,53(12):4655-4666.
[16] Chen S B,Donoho D L,Saunders M A.Atomic decomposition by basis pursuit[J].SIAM Review,2001,43(1):129-159.
[17] Daubechies I.Time-frequency localization operators:a geometric phase space approach[J].IEEE Trans.on Information Theory,1988,34(4):605-612.
[18] Coif man R R,Wickerhauser M V.Entropy-based algorithms for best-basis selection[J].IEEE Trans.on Information Theory,1992,38(2):713-718.
[19] Mallat S.信号处理的小波导引[M].2版.杨力华,戴道清,黄文良,等译.北京:机械工业出版社,2002.
[20] Donoho D L,Tsaig Y,Drori I,et al.Sparse solution of underdetermined linear equations by stagewise orthogonal matching pursuit[R].Dept.of Statistics,Stanford Univ.,2006.http://stat.Stanford.edu/-idrori/StOMP.pdf.
[21] Marco F Duarte,Michael B Wakin,Richard G Baraniuk.Fast reconstruction of piecewise smooth signals from incoherent projections.workshop on signal processing with adaptative sparse structured representations(SPARS),Rennes,France,2005,http://spars05.irisa.fr/ACTES/TS5-3.pdf.
[22] Chinh L,Minh N D.Tree-based orthogonal matching pursuit algorithm for signal reconstruction[C]//International Conference on Image Processing,Atlanta,GA,USA,2006:1277-1280.
[23] Gabriel P.Best basis compressed sensing[C]//Lecture Notes in Computer Science,Scale Space and Variational Methods in Computer Vision,Germany,Springer,2007:80-91.
[24] 刘丹华,石光明,周佳社.一种冗余字典下的信号稀疏分解新方法[J].西安电子科技大学学报(自然科学版),2008,35(2):228-232.
[25] 邵君,尹忠科,王建英,等.信号稀疏分解中过完备原子库的集合划分[J].铁道学报,2006,28(1):68-71.
[26] Davis G,Mallat S,Avellaneda M.Adaptive greedy approximation[J].Constr.Approx.,1997,13(1):57-98.
[27] 张春梅,尹忠科,肖明霞.基于冗余字典的信号超完备表示与稀疏分解[J].科学通报,2006,51(6):628-633.
[28] Shrijver A.Theory of Linear and Integer Programming[M].US:Wiley Press,1998.