Improved FFT-Based MP Algorithm for Signal Sparse Decomposition
-
摘要: 针对基于FFT的MP信号稀疏分解算法中存在的计算量过大的问题,提出了改进算法.改进算法充分利用了当FFT算法的变换长度是2的整数次幂时运算速度最快的性质,用基2 FFT实现信号稀疏分解中的相关运算.理论分析显示,当数字信号长度为1 024采样点时,用FFT算法计算互相关的速度为直接计算的10.6倍.仿真实验结果表明,改进算法的计算速度为直接计算的8.05倍,为原基于FFT的MP算法的3.64倍.Abstract: An improved FFT(fast Fourier transformation) based MP(matching pursuit) algorithm was proposed to reduce the calculation load in signal sparse decomposition.In the algorithm,a radix-2 FFT is performed to calculate the crosscorrelation, because the calculation speed is the fastest when the length of the transform is of integral power of 2.Theoretical analysis shows that,for a digital signal with a length of 1 024,the speed of calculation of crosscorrelation using radix-2 FFT is 10.6 times as fast as that using direct calculation.Simulation results show that the calculation speed of the improved FFT based MP algorithm is 8.05 times as fast as that of direct calculation,and 3.64 times as fast as that of the FFT-based MP algorithm.
-
Key words:
- signal processing /
- sparse representation /
- sparse decomposition /
- MP algorithm /
- FFT /
- improvement
-
MALLAT S,ZHANG Z.Matching pursuit with time-frequency dictionaries[J].IEEE Trans.on Signal Processing,1993,41(12):3397-3415.[2] COIFMAN R,WICKERHAUSER M.Entropy-based algorithms for best basis selection[J].IEEE Trans.Information Theory,1992,38:1713-1716.[3] 张文耀.基于匹配跟踪的低位率语音编码研究[D].北京:中国科学院研究生院(软件研究所),2002.ZHANG Wenyao.Study on matching pursuit low-bit rate speech coding[D].Beijing:Chinese Academy of Sciences,2002.[4] ARTHUR P L,PHILIPOS C L.Voiced/unvoiced speech discrimination in noise using gabor atomic decomposition[C]//Proc.of IEEE ICASSP.Hong Kong:IEEE press,2003,I(4):820-828.[5] 邹红星,周小波,李衍达.时频分析:回溯与前瞻[J].电子学报,2000,28(9):78-84.ZOU Hongxing,ZHOU Xiaobo,LI Yanda.Which time-frequency analysis-a survey[J].Acta Electronica Sinica,2000,28(9):78-84.[6] 傅霆,尧德中.稀疏分解的加权迭代方法及其初步应用[J].电子学报,2004,32(4):567-570.FU Ting,YAO Dezhong.Iterative weighted method of sparse decomposition and preliminary application[J].Acta Electronica Sinica,2004,32(4):567-570.[7] CHEN S,DONOHO D,SAUNDERS M.Atomic decomposition by basis pursuit[J].SIAM Journal on Scientific Computing,1999,20:33-61.[8] DAUBECHIES I.Time-frequency localization operators:a geometric phase space approach[J].IEEE Trans.Inform.Theory,1988,34:605-612[9] 尹忠科,王建英,VANDERGHEYNST P.一种新的图象稀疏分解快速算法[J].计算机应用,2004,24(10):92-96.YIN Zhongke,WANG Jianying,VANDERGHEYNST P.A new fast algorithm to sparsely decompose images[J].Computer Applications,2004,24(10):92-96.[10] 尹忠科,王建英,VANDERGHEYNST P.基于GA和原子特性的信号稀疏分解[J].铁道学报,2005,27(3):58-61.YIN Zhongke,WANG Jianying,VANDERGHEYNST P.Signal sparse decomposition based on GA and atom property[J].Journal of the China Railway Society,2005,27(3):58-61.[11] 尹忠科,王建英,邵君.基于原子结构特性的信号稀疏分解[J].西南交通大学学报,2005,40(2):173-178.YIN Zhongke,WANG Jianying,SHAO Jun.Sparse decomposition based on structural properties of atom dictionary[J].Journal of Southwest Jiaotong University,2005,40(2):173-178.[12] 尹忠科,邵君,VANDERGHEYNST P.利用FFT实现基于MP的信号稀疏分解[J].电子与信息学报,2006,28(4):614-618.YIN Zhongke,SHAO Jun,VANDERGHEYNST P.MP based signal sparse decomposition by using FFT[J].Journal of Electronics Information Technology,2006,28(4):614-618.[13] 丁玉美,高西全,数字信号处理[M].安:西安电子科技大学出版社,2002:81-82[14] 维纳·K·格尔,约翰·G·普罗克斯.刘树棠译.数字信号处理--使用MATLAB[M].西安:西安交通大学出版社,2002:158.[15] 徐伟业.长信号卷积的快速运算及其语音处理的应用[J].计算机工程,2004,30(1):110-113.XU Weiye.Fast realization of long signal convolution computation and its application to speech processing[J].Computer Engineering,2004,30(1):110-113.[16] 李海涛.MATLAB 6.1基础及应用技巧[M].北京:国防工业出版社,2002:106-108.
点击查看大图
计量
- 文章访问数: 1623
- HTML全文浏览量: 66
- PDF下载量: 503
- 被引次数: 0