压缩感知匹配追踪算法的研究
|
摘要
压缩感知理论是建立在概率统计理论、矩阵分析理论、泛函分析以及拓扑学等基础学科之上的信号处理理论框架。对于稀疏信号或者可稀疏化表示的信号,可将信号采样与信号压缩过程合二为一,信号重构过程则采用非线性算法。该理论框架为许多实际信号处理问题提供了更加良好的解决方案。相比较传统方法而言,压缩感知理论突破了奈奎斯特采样定律的要求,可通过少量采样点完成信号的重构,可降低硬件设备的复杂度以及避免采样、传输和存储过程因处理冗余信息而浪费资源。
目前,虽然压缩感知理论方面的研究已经取得了一些重要的成果,但是还停留在初步探索阶段,对于压缩感知理论的三个主要部分：信号的稀疏变换、观测矩阵的设设计和信号重构算法仍然需要我们不断的探索研究。作为压缩感知理论的核心部分,信号重构过程直接影响到了信号重构的速度、质量等。本文通过对压缩感知理论研究现状的分析,以及详细介绍压缩感知理论基本框架的基础上,围绕了匹配追踪算法所存在的问题展开研究,其主要工作如下：
本文首先介绍了压缩感知研究的目的和意义以及国内外相关领域的研究现状,对压缩感知理论的基本框架进行了详细的介绍,重点分析了压缩感知理论中信号的稀疏表示、观测矩阵的设计和信号重构。然后对信号重构进行了详细的分析针对其中比较具有代表性的基追踪算法、匹配追踪算法、正交匹配追踪算法以及分段正交匹配追踪算法的基本原理、重构思想以及主要步骤的算法流程图进行分析对比。分别对一维时域脉冲信号和二维图像进行了重构仿真,简要分析不同算法各自的优缺点。最后通过引入Dice系数作为新的原子匹配准则,将其应用到OMP算法与StOMP算法中,得到新的DOMP算法与DStOMP算法。从算法的有效性、信号重构成功率、信号重构误差与信号重构时间等方面做仿真对比,说明DOMP算法的实用性。同时把DOMP算法与DStOMP算法应用到二维图像重构中,通过对不同采样率下重构图像的时间和重构相对误差对比,分析改进算法的优缺点。
Compression sensing theory is a signal processing theory framework, which is based on basic subject such as probability statistics theory, matrix analysis theory, functional analysis and topology. For sparse signal or signal which can be sparse represented, signal sampling and signal compression process can be combined into one process, and then the signal reconstruction process is a nonlinear algorithm. The theoretical framework provides a better solution for many practical problems in signal processing. Compared to traditional methods, compressed sensing theory broke through the requirement of Nyquist sampling theorem, it can finish signal processing and reconstruction process by getting a small amount of sample point, so it can reduce the complexity of hardware devices and avoid waste of resources when sampling, transporting and storaging for dealing with redundant redundant information.
At present, although the study of compressed sensing theory has made some important achievements, but the study is still stay at preliminary exploration phase, for the three main parts of compressed sensing theory:signal sparse transformation, the design of the observation matrix and the signal reconstruction algorithms, we need still keeping research. As a core part of the compressed sensing theory, signal reconstruction process directly affects the signal reconstruction speed, quality, etc. In this thesis, we analyse the research status of compression sensing theory, introduce compression perception theory framework detailed, and spread the study which revolves around the problem of matching pursuit algorithm research. The main work is as follows:
Firstly, we introduce the purpose and significance of compression sensing research and the related research at home and abroad, at the same time, introduce compression perception theory framework detailed, focous on analyzing the details of signal sparse representation, the design of the observation matrix and the signal reconstruction, which are the three main aspects of compression sensing theory.
And then analyze the signal reconstruction in detail, for based tracking algorithm, the matching pursuit algorithm, orthogonal matching pursuit algorithm and block orthogonal matching pursuit algorithm, we analyze and compare their basic principle, reconstruct ideas and the main steps of the algorithm flow chart. We take a reconstructed simulation for one dimensional time-domain pulse signal and the2dimensional image, and then analyze the advantages and disadvantages of different algorithms respectively.
At last, we introduce Dice coefficient as a new atom matching criteria, apply it to the OMP algorithm, and then we propose a new DOMP algorithm. For the DOMP algorithm, we give a simulation and analysis from the effectiveness and success rate of reconstructing signal, signal reconstruction error and signal reconstruction time, results illustrates the usefulness of DOMP algorithm. The DOMP algorithm and the DStOMP algorithm is applied to the two-dimensional image reconstruction by the relative error for different sampling rates the time and reconstruction of the reconstructed image contrast, analysis of the advantages and disadvantages of the improved algorithm.
目前,虽然压缩感知理论方面的研究已经取得了一些重要的成果,但是还停留在初步探索阶段,对于压缩感知理论的三个主要部分：信号的稀疏变换、观测矩阵的设设计和信号重构算法仍然需要我们不断的探索研究。作为压缩感知理论的核心部分,信号重构过程直接影响到了信号重构的速度、质量等。本文通过对压缩感知理论研究现状的分析,以及详细介绍压缩感知理论基本框架的基础上,围绕了匹配追踪算法所存在的问题展开研究,其主要工作如下：
本文首先介绍了压缩感知研究的目的和意义以及国内外相关领域的研究现状,对压缩感知理论的基本框架进行了详细的介绍,重点分析了压缩感知理论中信号的稀疏表示、观测矩阵的设计和信号重构。然后对信号重构进行了详细的分析针对其中比较具有代表性的基追踪算法、匹配追踪算法、正交匹配追踪算法以及分段正交匹配追踪算法的基本原理、重构思想以及主要步骤的算法流程图进行分析对比。分别对一维时域脉冲信号和二维图像进行了重构仿真,简要分析不同算法各自的优缺点。最后通过引入Dice系数作为新的原子匹配准则,将其应用到OMP算法与StOMP算法中,得到新的DOMP算法与DStOMP算法。从算法的有效性、信号重构成功率、信号重构误差与信号重构时间等方面做仿真对比,说明DOMP算法的实用性。同时把DOMP算法与DStOMP算法应用到二维图像重构中,通过对不同采样率下重构图像的时间和重构相对误差对比,分析改进算法的优缺点。
Compression sensing theory is a signal processing theory framework, which is based on basic subject such as probability statistics theory, matrix analysis theory, functional analysis and topology. For sparse signal or signal which can be sparse represented, signal sampling and signal compression process can be combined into one process, and then the signal reconstruction process is a nonlinear algorithm. The theoretical framework provides a better solution for many practical problems in signal processing. Compared to traditional methods, compressed sensing theory broke through the requirement of Nyquist sampling theorem, it can finish signal processing and reconstruction process by getting a small amount of sample point, so it can reduce the complexity of hardware devices and avoid waste of resources when sampling, transporting and storaging for dealing with redundant redundant information.
At present, although the study of compressed sensing theory has made some important achievements, but the study is still stay at preliminary exploration phase, for the three main parts of compressed sensing theory:signal sparse transformation, the design of the observation matrix and the signal reconstruction algorithms, we need still keeping research. As a core part of the compressed sensing theory, signal reconstruction process directly affects the signal reconstruction speed, quality, etc. In this thesis, we analyse the research status of compression sensing theory, introduce compression perception theory framework detailed, and spread the study which revolves around the problem of matching pursuit algorithm research. The main work is as follows:
Firstly, we introduce the purpose and significance of compression sensing research and the related research at home and abroad, at the same time, introduce compression perception theory framework detailed, focous on analyzing the details of signal sparse representation, the design of the observation matrix and the signal reconstruction, which are the three main aspects of compression sensing theory.
And then analyze the signal reconstruction in detail, for based tracking algorithm, the matching pursuit algorithm, orthogonal matching pursuit algorithm and block orthogonal matching pursuit algorithm, we analyze and compare their basic principle, reconstruct ideas and the main steps of the algorithm flow chart. We take a reconstructed simulation for one dimensional time-domain pulse signal and the2dimensional image, and then analyze the advantages and disadvantages of different algorithms respectively.
At last, we introduce Dice coefficient as a new atom matching criteria, apply it to the OMP algorithm, and then we propose a new DOMP algorithm. For the DOMP algorithm, we give a simulation and analysis from the effectiveness and success rate of reconstructing signal, signal reconstruction error and signal reconstruction time, results illustrates the usefulness of DOMP algorithm. The DOMP algorithm and the DStOMP algorithm is applied to the two-dimensional image reconstruction by the relative error for different sampling rates the time and reconstruction of the reconstructed image contrast, analysis of the advantages and disadvantages of the improved algorithm.
引文
[1]Doohwan Lee, Sasaki T., Yamada T., etc. Spectrum sensing for networked system using 1-bit compressed sensing with partial random circulant measurement matrices [C]. Vehicular Technology Conference (VTC Spring),2012 IEEE 75th.2012:1-5.
[2]Candes E. J., Romberg J., Tao T. Robust uncertainty principles:Exact signal reconstruction from highly incomplete frequency information [J]. Information Theory, IEEE Transactions on,2006,52(2):489-509.
[3]Lustig M., Donoho D. L., Santos J. M., etc. Compressed sensing mri [J]. Signal Processing Magazine, IEEE,2008,25(2):72-82.
[4]Chunmei Zhang, Zhongke Yin, Xiangdong Chen, etc. Signal overcomplete representation and sparse decomposition based on redundant dictionaries [J]. Chinese Science Bulletin,2005,50(23):2672-2677.
[5]石光明,刘丹华,高大化,etc.压缩感知理论及其研究进展[J].电子学报,2009,37(5)：1070-1081.
[6]Candes Emmanuel J, Wakin Michael B. An introduction to compressive sampling [J]. Signal Processing Magazine, IEEE,2008,25(2):21-30.
[7]Candes Emmanuel, Romberg Justin. Sparsity and incoherence in compressive sampling [J]. Inverse problems,2007,23(3):969.
[8]Chen Scott Shaobing, Donoho David L, Saunders Michael A. Atomic decomposition by basis pursuit [J]. SIAM review,2001,43(1):129-159.
[9]Boyd Stephen, Vandenberghe Lieven. Convex optimization [M]. Cambridge university press,2004.
[10]Baraniuk Richard G. Compressive sensing [lecture notes] [J]. Signal Processing Magazine, IEEE,2007,24(4):118-121.
[11]Romberg Justin. Imaging via compressive sampling [J]. Signal Processing Magazine, IEEE,2008,25(2):14-20.
[12]Hormati A., Vetterli M. Distributed compressed sensing:Sparsity models and reconstruction algorithms using annihilating filter [C]. Acoustics, Speech and Signal Processing,2008. ICASSP 2008. IEEE International Conference on.2008:5141-5144.
[13]Laska J., Kirolos S., Massoud Y., etc. Random sampling for analog-to-information conversion of wideband signals [C]. Design, Applications, Integration and Software,2006 IEEE Dallas/CAS Workshop on.2006:119-122.
[14]Laska J. N., Kirolos S., Duarte M. F., etc. Theory and implementation of an analog-to-information converter using random demodulation [C]. Circuits and Systems,2007. ISCAS 2007. IEEE International Symposium on.2007:1959-1962.
[15]Wei Dai, Milenkovic O., Sheikh M. A., etc. Probe design for compressive sensing DNA microarrays [C]. Bioinformatics and Biomedicine,2008. BIBM'08. IEEE International Conference on.2008:163-169.
[16]Lustig Michael, Donoho David, Pauly John M. Sparse mri:The application of compressed sensing for rapid mr imaging [J]. Magnetic resonance in medicine,2007, 58(6):1182-1195.
[17]Duarte Marco F, Davenport Mark A, Takhar Dharmpal, etc. Single-pixel imaging via compressive sampling [J]. Signal Processing Magazine, IEEE,2008,25(2):83-91.
[18]Bajwa Waheed, Haupt Jarvis, Sayeed Akbar, etc. Compressive wireless sensing. in Proceedings of the 5th international conference on Information processing in sensor networks.2006, ACM:Nashville, Tennessee, USA. p.134-142.
[19]Baraniuk Richard, Steeghs Philippe. Compressive radar imaging [C]. Radar Conference,2007 IEEE. IEEE,2007:128-133.
[20]Ma Jianwei, Le Dimet F-X. Deblurring from highly incomplete measurements for remote sensing [J]. Geoscience and Remote Sensing, IEEE Transactions on,2009, 47(3):792-802.
[21]Wagadarikar Ashwin, John Renu, Willett Rebecca, etc. Single disperser design for coded aperture snapshot spectral imaging [J]. Applied optics,2008,47(10):B44-B51.
[22]Takhar Dharmpal, Laska Jason N, Wakin Michael B, etc. A new compressive imaging camera architecture using optical-domain compression [C]. Electronic Imaging 2006. International Society for Optics and Photonics, 2006:606509-606509-10.
[23]Wakin Michael B, Laska Jason N, Duarte Marco F, etc. An architecture for compressive imaging [C]. Image Processing,2006 IEEE International Conference on. IEEE,2006:1273-1276.
[24]史晨星,曹继华,刘霄.基于压缩传感理论的医学ct成像技术[J].科技创新导报,2011,(20)：236-237.
[25]Bajwa Waheed U, Haupt Jarvis, Raz Gil, etc. Compressed channel sensing [C]. Information Sciences and Systems,2008. CISS 2008.42nd Annual Conference on. IEEE,2008:5-10.
[26]Taubock Georg, Hlawatsch Franz. A compressed sensing technique for ofdm channel estimation in mobile environments:Exploiting channel sparsity for reducing pilots [C]. Acoustics, Speech and Signal Processing,2008. ICASSP 2008. IEEE International Conference on. IEEE,2008:2885-2888.
[27]Bobin Jerome, Starck J-L, Ottensamer Roland. Compressed sensing in astronomy [J]. Selected Topics in Signal Processing, IEEE Journal of,2008,2(5):718-726.
[28]Haupt Jarvis, Nowak Robert. Compressive sampling for signal detection [C]. Acoustics, Speech and Signal Processing,2007. ICASSP 2007. IEEE International Conference on. IEEE,2007:111-1509-111-1512.
[29]Mallat Stephane G, Zhang Zhifeng. Matching pursuits with time-frequency dictionaries [J]. Signal Processing, IEEE Transactions on,1993,41(12):3397-3415.
[30]Tropp Joel A, Gilbert Anna C. Signal recovery from random measurements via orthogonal matching pursuit [J]. Information Theory, IEEE Transactions on,2007, 53(12):4655-4666.
[31]Needell Deanna, Vershynin Roman. Uniform uncertainty principle and signal recovery via regularized orthogonal matching pursuit [J]. Foundations of computational mathematics,2009,9(3):317-334.
[32]Donoho David L, Tanner Jared. Sparse nonnegative solution of underdetermined linear equations by linear programming [J]. Proceedings of the National Academy of Sciences of the United States of America,2005,102(27):9446-9451.
[33]屈乐乐,方广有,杨天虹.压缩感知理论在频率步进探地雷达偏移成像中的应用[J].电子与信息学报,2011,33(1)：21-26.
[34]Needell Deanna, Tropp Joel A. Cosamp:Iterative signal recovery from incomplete and inaccurate samples [J]. Applied and Computational Harmonic Analysis,2009,26(3):301-321.
[35]Chen Scott Shaobing, Donoho David L, Saunders Michael A. Atomic decomposition by basis pursuit [J]. SIAM journal on scientific computing,1998, 20(1):33-61.
[36]Kim Seung-Jean, Koh Kwangmoo, Lustig Michael, etc. An interior-point method for large-scale< i> l< sub> 1-regularized least squares [J]. Selected Topics in Signal Processing, IEEE Journal of,2007,1(4):606-617.
[37]Figueiredo Mario AT, Nowak Robert D, Wright Stephen J. Gradient projection for sparse reconstruction:Application to compressed sensing and other inverse problems [J]. Selected Topics in Signal Processing, IEEE Journal of,2007,1(4):586-597.
[38]Daubechies Ingrid, Defrise Michel, De Mol Christine. An iterative thresholding algorithm for linear inverse problems with a sparsity constraint [J]. Communications on pure and applied mathematics,2004,57(11):1413-1457.
[39]Blumensath Thomas, Davies Mike E. Iterative hard thresholding for compressed sensing [J]. Applied and Computational Harmonic Analysis,2009,27(3):265-274.
[40]Gilbert Anna C, Guha Sudipto, Indyk Piotr, etc. Near-optimal sparse fourier representations via sampling [C]. Proceedings of the thiry-fourth annual ACM symposium on Theory of computing. ACM,2002:152-161.
[41]Gilbert Anna C, Muthukrishnan S, Strauss M. Improved time bounds for near-optimal sparse fourier representations [C]. Optics & Photonics 2005. International Society for Optics and Photonics,2005:59141A-59141A-15.
[2]Candes E. J., Romberg J., Tao T. Robust uncertainty principles:Exact signal reconstruction from highly incomplete frequency information [J]. Information Theory, IEEE Transactions on,2006,52(2):489-509.
[3]Lustig M., Donoho D. L., Santos J. M., etc. Compressed sensing mri [J]. Signal Processing Magazine, IEEE,2008,25(2):72-82.
[4]Chunmei Zhang, Zhongke Yin, Xiangdong Chen, etc. Signal overcomplete representation and sparse decomposition based on redundant dictionaries [J]. Chinese Science Bulletin,2005,50(23):2672-2677.
[5]石光明,刘丹华,高大化,etc.压缩感知理论及其研究进展[J].电子学报,2009,37(5)：1070-1081.
[6]Candes Emmanuel J, Wakin Michael B. An introduction to compressive sampling [J]. Signal Processing Magazine, IEEE,2008,25(2):21-30.
[7]Candes Emmanuel, Romberg Justin. Sparsity and incoherence in compressive sampling [J]. Inverse problems,2007,23(3):969.
[8]Chen Scott Shaobing, Donoho David L, Saunders Michael A. Atomic decomposition by basis pursuit [J]. SIAM review,2001,43(1):129-159.
[9]Boyd Stephen, Vandenberghe Lieven. Convex optimization [M]. Cambridge university press,2004.
[10]Baraniuk Richard G. Compressive sensing [lecture notes] [J]. Signal Processing Magazine, IEEE,2007,24(4):118-121.
[11]Romberg Justin. Imaging via compressive sampling [J]. Signal Processing Magazine, IEEE,2008,25(2):14-20.
[12]Hormati A., Vetterli M. Distributed compressed sensing:Sparsity models and reconstruction algorithms using annihilating filter [C]. Acoustics, Speech and Signal Processing,2008. ICASSP 2008. IEEE International Conference on.2008:5141-5144.
[13]Laska J., Kirolos S., Massoud Y., etc. Random sampling for analog-to-information conversion of wideband signals [C]. Design, Applications, Integration and Software,2006 IEEE Dallas/CAS Workshop on.2006:119-122.
[14]Laska J. N., Kirolos S., Duarte M. F., etc. Theory and implementation of an analog-to-information converter using random demodulation [C]. Circuits and Systems,2007. ISCAS 2007. IEEE International Symposium on.2007:1959-1962.
[15]Wei Dai, Milenkovic O., Sheikh M. A., etc. Probe design for compressive sensing DNA microarrays [C]. Bioinformatics and Biomedicine,2008. BIBM'08. IEEE International Conference on.2008:163-169.
[16]Lustig Michael, Donoho David, Pauly John M. Sparse mri:The application of compressed sensing for rapid mr imaging [J]. Magnetic resonance in medicine,2007, 58(6):1182-1195.
[17]Duarte Marco F, Davenport Mark A, Takhar Dharmpal, etc. Single-pixel imaging via compressive sampling [J]. Signal Processing Magazine, IEEE,2008,25(2):83-91.
[18]Bajwa Waheed, Haupt Jarvis, Sayeed Akbar, etc. Compressive wireless sensing. in Proceedings of the 5th international conference on Information processing in sensor networks.2006, ACM:Nashville, Tennessee, USA. p.134-142.
[19]Baraniuk Richard, Steeghs Philippe. Compressive radar imaging [C]. Radar Conference,2007 IEEE. IEEE,2007:128-133.
[20]Ma Jianwei, Le Dimet F-X. Deblurring from highly incomplete measurements for remote sensing [J]. Geoscience and Remote Sensing, IEEE Transactions on,2009, 47(3):792-802.
[21]Wagadarikar Ashwin, John Renu, Willett Rebecca, etc. Single disperser design for coded aperture snapshot spectral imaging [J]. Applied optics,2008,47(10):B44-B51.
[22]Takhar Dharmpal, Laska Jason N, Wakin Michael B, etc. A new compressive imaging camera architecture using optical-domain compression [C]. Electronic Imaging 2006. International Society for Optics and Photonics, 2006:606509-606509-10.
[23]Wakin Michael B, Laska Jason N, Duarte Marco F, etc. An architecture for compressive imaging [C]. Image Processing,2006 IEEE International Conference on. IEEE,2006:1273-1276.
[24]史晨星,曹继华,刘霄.基于压缩传感理论的医学ct成像技术[J].科技创新导报,2011,(20)：236-237.
[25]Bajwa Waheed U, Haupt Jarvis, Raz Gil, etc. Compressed channel sensing [C]. Information Sciences and Systems,2008. CISS 2008.42nd Annual Conference on. IEEE,2008:5-10.
[26]Taubock Georg, Hlawatsch Franz. A compressed sensing technique for ofdm channel estimation in mobile environments:Exploiting channel sparsity for reducing pilots [C]. Acoustics, Speech and Signal Processing,2008. ICASSP 2008. IEEE International Conference on. IEEE,2008:2885-2888.
[27]Bobin Jerome, Starck J-L, Ottensamer Roland. Compressed sensing in astronomy [J]. Selected Topics in Signal Processing, IEEE Journal of,2008,2(5):718-726.
[28]Haupt Jarvis, Nowak Robert. Compressive sampling for signal detection [C]. Acoustics, Speech and Signal Processing,2007. ICASSP 2007. IEEE International Conference on. IEEE,2007:111-1509-111-1512.
[29]Mallat Stephane G, Zhang Zhifeng. Matching pursuits with time-frequency dictionaries [J]. Signal Processing, IEEE Transactions on,1993,41(12):3397-3415.
[30]Tropp Joel A, Gilbert Anna C. Signal recovery from random measurements via orthogonal matching pursuit [J]. Information Theory, IEEE Transactions on,2007, 53(12):4655-4666.
[31]Needell Deanna, Vershynin Roman. Uniform uncertainty principle and signal recovery via regularized orthogonal matching pursuit [J]. Foundations of computational mathematics,2009,9(3):317-334.
[32]Donoho David L, Tanner Jared. Sparse nonnegative solution of underdetermined linear equations by linear programming [J]. Proceedings of the National Academy of Sciences of the United States of America,2005,102(27):9446-9451.
[33]屈乐乐,方广有,杨天虹.压缩感知理论在频率步进探地雷达偏移成像中的应用[J].电子与信息学报,2011,33(1)：21-26.
[34]Needell Deanna, Tropp Joel A. Cosamp:Iterative signal recovery from incomplete and inaccurate samples [J]. Applied and Computational Harmonic Analysis,2009,26(3):301-321.
[35]Chen Scott Shaobing, Donoho David L, Saunders Michael A. Atomic decomposition by basis pursuit [J]. SIAM journal on scientific computing,1998, 20(1):33-61.
[36]Kim Seung-Jean, Koh Kwangmoo, Lustig Michael, etc. An interior-point method for large-scale< i> l< sub> 1-regularized least squares [J]. Selected Topics in Signal Processing, IEEE Journal of,2007,1(4):606-617.
[37]Figueiredo Mario AT, Nowak Robert D, Wright Stephen J. Gradient projection for sparse reconstruction:Application to compressed sensing and other inverse problems [J]. Selected Topics in Signal Processing, IEEE Journal of,2007,1(4):586-597.
[38]Daubechies Ingrid, Defrise Michel, De Mol Christine. An iterative thresholding algorithm for linear inverse problems with a sparsity constraint [J]. Communications on pure and applied mathematics,2004,57(11):1413-1457.
[39]Blumensath Thomas, Davies Mike E. Iterative hard thresholding for compressed sensing [J]. Applied and Computational Harmonic Analysis,2009,27(3):265-274.
[40]Gilbert Anna C, Guha Sudipto, Indyk Piotr, etc. Near-optimal sparse fourier representations via sampling [C]. Proceedings of the thiry-fourth annual ACM symposium on Theory of computing. ACM,2002:152-161.
[41]Gilbert Anna C, Muthukrishnan S, Strauss M. Improved time bounds for near-optimal sparse fourier representations [C]. Optics & Photonics 2005. International Society for Optics and Photonics,2005:59141A-59141A-15.
© 2004-2018 中国地质图书馆版权所有 京ICP备05064691号 京公网安备11010802017129号 地址：北京市海淀区学院路29号 邮编：100083 电话：办公室：(+86 10)66554848；文献借阅、咨询服务、科技查新：66554700 |