基于矩阵分解的压缩感知重构算法的研究
|
摘要
传统的信号处理技术遵循奈奎斯特采样定律,信号的采样频率必须大于信号最高频率的2倍才能精确地恢复原始信号。因此,传统的信号处理技术已经不能满足日益增长的信号需求。近年来,一种新的信号处理技术被相关学者提出来,即压缩感知技术。该技术与传统的信号处理技术相比突显出巨大的优势,压缩感知技术将数据的采集和压缩合二为一,突破了奈奎斯特定理的束缚,并能精确地恢复信号。压缩感知理论一经提出,就受到了人们的广泛关注,成为信号处理领域研究的热点话题。该理论具有巨大的应用前景,无论在理论研究与实际应用中都有重要的意义。
本文首先介绍了压缩感知理论的背景和研究意义,以及简单介绍了目前国内外的研究现状。然后介绍了压缩感知理论的整体框架,阐述了感知过程的三个步骤：信号的稀疏表示、观测矩阵的设计以及信号的重构算法。在信号的稀疏表示部分,介绍了信号稀疏化的基本原理；对于观测矩阵的设计,首先分析了观测矩阵的选取原则,然后给出几种常用的观测矩阵。本文主要研究的是信号的重构算法,针对几种主要的信号重构算法,重点介绍了正交匹配追踪算法及其改进算法。对几种算法进行了MATLAB仿真比较并进行了分析。基于经典的正交匹配追踪算法,其中在信号重构部分运用到最小二乘法,但是最小二乘法计算过程中矩阵的计算复杂度比较高,并且每次迭代中都要运用到最小二乘法。针对这点,对最小二乘法的原理进行了介绍,并列举了几种常用的矩阵分解方法,QR分解、cholesky分解以及奇异值分解比较适用于最小二乘法。在此基础上,将正交匹配追踪算法中的矩阵进行QR分解,推导出简化的结果。对改进算法进行仿真并进行结果分析,证实改进算法相比原算法在运算时间上有所缩短。
Traditional signal processing technology follows the law of Nyquist sampling signals, that the sampling frequency must be greater than two times of the highest frequency that the signal can be accurately restore. Therefore, the traditional signal processing technology have been formed by contradiction in growing demand of signal. In recent years, a new signal processing technology was proposed by some related scholars, which is the Compressed Sensing technology. The technology demonstrated a huge advantage when it was compared with the traditional signal processing technology, which combined collection and compression of signal. It had broken the shackles of the law of Nyquist and the signal can be restored accurately. When the theory of compressed Sensing technology was put forwarded, compressed sensing theory has been received widespread attention by people, and has become a hot topic in the field of signal processing research. The theory has great application prospects, which has important significance both in filed of research theory and practical application.
This thesis firstly introduces the background and the research significance of compressed sensing theory, and the research status at home and abroad is introduced simply. Then this thesis introduces the overall framework of compressed sensing theory, and expounds the three steps of the process of perception:sparse representation of signal, the design of the observation matrix and the signal reconstruction algorithm. In the part of sparse representation of signal, this thesis introduces the basic principle of signal sparse; To the design of the observation matrix, the selecting principle of the observation matrix is firstly analyzed, then several observation matrix are given. This thesis mainly studies the signal reconstruction algorithm, aiming at several main signal reconstruction algorithm, that the orthogonal matching pursuit algorithm and its improved algorithm are mainly introduced. Several algorithms for the MATLAB simulation are compared and analyzed. Based on the classical orthogonal matching pursuit algorithm, which the least squares method was used in part of signal reconstruction, but the complexity is higher in the process of matrix calculation with least squares calculation, and least squares is applied to each iteration. In the light of this, the principle of least square method is introduced, and several common methods of the matrix decomposition are listed, such as the QR decomposition, the cholesky decomposition and singular value decomposition are suitably applied to least squares. On this basis, the matrix QR decomposition is used in the orthogonal matching pursuit algorithm, and deduces the simplified results. Simulate the improved algorithm and analysis of the simulation results. It is confirmed that running time of the improved algorithm is shorter than the original algorithm.
本文首先介绍了压缩感知理论的背景和研究意义,以及简单介绍了目前国内外的研究现状。然后介绍了压缩感知理论的整体框架,阐述了感知过程的三个步骤：信号的稀疏表示、观测矩阵的设计以及信号的重构算法。在信号的稀疏表示部分,介绍了信号稀疏化的基本原理；对于观测矩阵的设计,首先分析了观测矩阵的选取原则,然后给出几种常用的观测矩阵。本文主要研究的是信号的重构算法,针对几种主要的信号重构算法,重点介绍了正交匹配追踪算法及其改进算法。对几种算法进行了MATLAB仿真比较并进行了分析。基于经典的正交匹配追踪算法,其中在信号重构部分运用到最小二乘法,但是最小二乘法计算过程中矩阵的计算复杂度比较高,并且每次迭代中都要运用到最小二乘法。针对这点,对最小二乘法的原理进行了介绍,并列举了几种常用的矩阵分解方法,QR分解、cholesky分解以及奇异值分解比较适用于最小二乘法。在此基础上,将正交匹配追踪算法中的矩阵进行QR分解,推导出简化的结果。对改进算法进行仿真并进行结果分析,证实改进算法相比原算法在运算时间上有所缩短。
Traditional signal processing technology follows the law of Nyquist sampling signals, that the sampling frequency must be greater than two times of the highest frequency that the signal can be accurately restore. Therefore, the traditional signal processing technology have been formed by contradiction in growing demand of signal. In recent years, a new signal processing technology was proposed by some related scholars, which is the Compressed Sensing technology. The technology demonstrated a huge advantage when it was compared with the traditional signal processing technology, which combined collection and compression of signal. It had broken the shackles of the law of Nyquist and the signal can be restored accurately. When the theory of compressed Sensing technology was put forwarded, compressed sensing theory has been received widespread attention by people, and has become a hot topic in the field of signal processing research. The theory has great application prospects, which has important significance both in filed of research theory and practical application.
This thesis firstly introduces the background and the research significance of compressed sensing theory, and the research status at home and abroad is introduced simply. Then this thesis introduces the overall framework of compressed sensing theory, and expounds the three steps of the process of perception:sparse representation of signal, the design of the observation matrix and the signal reconstruction algorithm. In the part of sparse representation of signal, this thesis introduces the basic principle of signal sparse; To the design of the observation matrix, the selecting principle of the observation matrix is firstly analyzed, then several observation matrix are given. This thesis mainly studies the signal reconstruction algorithm, aiming at several main signal reconstruction algorithm, that the orthogonal matching pursuit algorithm and its improved algorithm are mainly introduced. Several algorithms for the MATLAB simulation are compared and analyzed. Based on the classical orthogonal matching pursuit algorithm, which the least squares method was used in part of signal reconstruction, but the complexity is higher in the process of matrix calculation with least squares calculation, and least squares is applied to each iteration. In the light of this, the principle of least square method is introduced, and several common methods of the matrix decomposition are listed, such as the QR decomposition, the cholesky decomposition and singular value decomposition are suitably applied to least squares. On this basis, the matrix QR decomposition is used in the orthogonal matching pursuit algorithm, and deduces the simplified results. Simulate the improved algorithm and analysis of the simulation results. It is confirmed that running time of the improved algorithm is shorter than the original algorithm.
引文
[1]Candes E, Rom berg J, Tao J. Robust uncertainty principles:Exact signal reconstru ction from highly incomplete frequency information [J]. IEEE Transactions on Inform ation Theory,2006,52(2):489-509
[2]Donoho D. Compressed sensing [J]. IEEE Transactions on Information Theory, 2006,52(4):1289-1306
[3]Y.C Eldar.Compressed sensing of analog signals in shift-in-variant spaces [JJ.IEEE Transactions on Signal Processing,2009,57(8):2986-2997
[4]尹忠科,解梅,王建英.“基于稀疏分解的图像去噪”,电子科技大学学报,2006,35(6)：876-878
[5]张旭东,卢国栋,冯建.图像编码基础和小波压缩技术一原理、算法和标准[M].北京：清华大学出版社,2004.03
[6]张春田,苏育挺,张静.数字图像压缩编码,北京：清华大学出版社,2006,350-361
[7]Candes E, Wakin B. "people hearing without listening." An Introduction to Compr essive Sampling [J], Tech. Report, California Institute of technology.2007,1-28.
[8]J.A. TroPP "Topics in sparse approximation" [D].Ph. D dissertation, Stanford University, Stanford, CA.1995
[9]付强,李琼.压缩感知中测量矩阵的研究,应用技术与研究,2011,7(1)
[10]Candes E, Romberg J. Sparsity and incoherence in compressive sampling [JJ.Inve rse Problems,2007,23(3):969-985.
[11]Davenport M, Wakin M, Baraniuk R. Detection and estimation with compressive measurements, Technical Report TREE 0610, Department of Electrical Engineering, Rice University, USA,2006.
[12]Rauhut H, Schnass K V P. Compressed sensing and redundant dictionaries [J].IE EE Transactions on Information Theory,2008,54(5):2210-2219.
[13]Hong Fang, Quanbing Zhang, Sui Wei "Method of Image Reconstruction Based on Sub-Gaussian Random Projection" [J]. Journal of Computer Research and Development,2008,45 (8):1402-1407
[14]David L. Donoho "Compressed Sensing" [J].IEEE Transactions on Information Theory, vol.52, No.4, April 2006:289-1306
[15]Hong Fang, Quanbing Zhang, Sui Wei, "Method of Image Reconstruction Based on very sparse random Projection" [J].Computer Engineering and Application,2007, 43 (22):25-27
[16]Emmanuel Candes, "ComPressive sampling"[J]. Proceedings of the International Congress of Mathematicans, Madrid, Spain,2006,3:1433-1452
[17]Y. Tsaig, D. Donoho, "Extenstion of compressed sensing" [J]. Signal Processing, 2006,86 (3),549-571
[18]W. Yin, S. P. Morgan, J. Yang, "Practical compressive sensing with Toeplitz and to VOIP" 2010
[19]T. Do, T.D. Trany, L. Gan, "Fast compressive sampling with structurally Random matrices" [J]. Proceedings of the IEEE International Conference on Acoustics, Speech and Signal Processing, Washington D.C, USA:IEEE,2008,47-50
[20]Justin Rombery, "Compressive sensing by random convolution" [J].SIAM Journal on Imaging Sciences, Nov.2009,2 (4):1098-1128
[21]Lome Applebaum, Stephen Howard, Stephen Searle, Robert Calderbank, "Chirp sensing code:Deterministic compressed sensing measurements for fast recovery", Preprint,2008,AValiable:httP//dsp.rice.edu/cs
[22]Radu Berinde, Piotr Indyk, "Sparse recovery using sparse random matrices",2008, preprint [online]. Available:http//dsp.rice.edu/cs
[23]Fiqueiredo M A T, Nowak R D, Wright S J. "Gradient projection for sparse recon struction:Application to compressed sensing and other inverse problems", IEEE Jour nal of Selected Topics in Signal Processing,2007,1(4):586-598.
[24]Kim S, Koh K, Lustig M, Boyd S, Gorinevsky D. "An interior-point method for 1 arge-scale regularized least squares", IEEE Journal of Selected Topics in Signal Proce ssing,2007,1(4):606-617.
[25]Thong T Do, Gan Lu, Nguyen, and Tran D. "Sparsity adaptive matching pursuit algorithm for practical compressed sensing" [J]. Asilomar Conference on Signals, Systems, and Computers, Pacific Grove, California,2008,10:581-587.
[26]Liu Yaxin, Zhao Ruizhen, Hu Shahai, Jiang Chunhui, "Regularized Adaptive Matching Pursuit Algorithm for Signal Reconstruction Based on Compressive Sensing" [J], Journal of Electronics&Information Technology, Vol.32No.11,Nov.2010
[27]M Herman, T Strohmer. "High-resolution radar via compressed sensing", [J].IEEE Transactions on Signal Processing,2009,57 (6):2275-2284.
[28]Kirolos S, Laska J, Wakin M, Duarte M,Baron D,Ragheb T, Massoud Y, Baraniu k R. "Analog-to-information conversion via random demodulation" [J].Design, Appli cations, Integration and Software, IEEE Dallas/CAS Workshop on,71-74, Oct,2006.
[29]Laska J, Kirolos S, Massoud Y etc. "Random sampling for analog-to-information conversion of wideband signals", [A].Proceedings of the IEEE Dallas Circuits and Sy stems Workshop (DCAS'06) [C].Dallas, Texas,2006.
[30]Wang W, Garofalakis M, Ramchandran K. "Distributed sparse random projection s for refinable approximation", [A]. Proceedings of the Sixth International Symposiu m on Information Processing in Sensor Networks (IPSN2007) [C].New York:Associa tion for Computing Machinery,2007.3312339.
[31]J.Bobin, J.Starck, R.Ottensamer, "Compressed sensing in astronomy" [J]. Applied Mathematics and Computation,2008,206(2):980-988
[32]Takhar D, Laska J, Wakin M etc. "A new compressive imaging camera architectu re using optical domain compression", [A]. Proceedings of SPIE [C]. Bellingham WA international Society for Optical Engineering.2006-6065.
[33]Chens, Donohod.L, Saundersma. "Atomic Decomposition by Basis pursuit" [J], SIAM J.Sci.Comp,1999,20(l):33-61.
[34]Rui Guosheng, Wang Lin,Tian Wenbiao, "Improved algorithm based basis Pursuit for compressive sensing reconstruction" [J]. Electronic Measurement Technology,2010,33(4):38-41
[35]Tropp J, Gilbert A. "Signal.recovery from random measurements via orthogonal matching pursuit", [J].Transactions on Information Theory,2007,53(12):4655-4666.
[36]Donoho D L, Tsaig Y, Drori I, Starck J L. "Sparse solution of underdetermined li near equations by stagewise orthogonal matching pursuit (StOMP)". Submitted for pu blication.
[37]Needell D, Vershynin R. "Uniform uncertainty principle and signal recovery via r egularized orthogonal matching pursuit". Found. Computer, Math.2008.
[38]M.A.T.Figueiredo, R.D.Nowak, and S.J.Wright, "Gradient projection for sparse reconstruction:application to compressed sensing and other inverse Problems" [J]. submitte,2007.
[39]高睿,赵瑞珍,胡绍海.基于压缩感知的变步长自适应匹配追踪重建算法[J].光学学报,2010,30(6)：1639-1644.
[40]陆建.最小二乘法及其应用[J].中国西部科技,2007,(12)：19-21
[41]杨明,刘先忠.矩阵论,武汉：华中科技大学出版社,2005
[42]李新,何传江.矩阵理论及其应用[M].重庆：重庆大学出版社,2005：130-145
[43]Joanne A. Foster John G.,Martin R. Davies and Jonathon A. Chambers. "An Algorithm for Calculating the QR and Singular Value Decompositions of Polynomial Matrices", [J]. IEEE Transactions On Signal Processing, March,2010,58 (3):1263-1274.
[44]李建东矩阵QR分解的三种方法[J].吕凉学院学报,2009,25(1)：16-19
[45]罗小桂.矩阵奇异值分解及其应用[J].井冈山学院学报,2005,12(4)：133-135
[46]吴昌愙,魏洪增主编.矩阵理论与方法[M].北京：电子工业出版社,2006.
[47]鲁铁定,宁津生等,最小二乘配置的QR分解解法[J].辽宁工程技术大学学报,2009,28(4)：550-553.
[2]Donoho D. Compressed sensing [J]. IEEE Transactions on Information Theory, 2006,52(4):1289-1306
[3]Y.C Eldar.Compressed sensing of analog signals in shift-in-variant spaces [JJ.IEEE Transactions on Signal Processing,2009,57(8):2986-2997
[4]尹忠科,解梅,王建英.“基于稀疏分解的图像去噪”,电子科技大学学报,2006,35(6)：876-878
[5]张旭东,卢国栋,冯建.图像编码基础和小波压缩技术一原理、算法和标准[M].北京：清华大学出版社,2004.03
[6]张春田,苏育挺,张静.数字图像压缩编码,北京：清华大学出版社,2006,350-361
[7]Candes E, Wakin B. "people hearing without listening." An Introduction to Compr essive Sampling [J], Tech. Report, California Institute of technology.2007,1-28.
[8]J.A. TroPP "Topics in sparse approximation" [D].Ph. D dissertation, Stanford University, Stanford, CA.1995
[9]付强,李琼.压缩感知中测量矩阵的研究,应用技术与研究,2011,7(1)
[10]Candes E, Romberg J. Sparsity and incoherence in compressive sampling [JJ.Inve rse Problems,2007,23(3):969-985.
[11]Davenport M, Wakin M, Baraniuk R. Detection and estimation with compressive measurements, Technical Report TREE 0610, Department of Electrical Engineering, Rice University, USA,2006.
[12]Rauhut H, Schnass K V P. Compressed sensing and redundant dictionaries [J].IE EE Transactions on Information Theory,2008,54(5):2210-2219.
[13]Hong Fang, Quanbing Zhang, Sui Wei "Method of Image Reconstruction Based on Sub-Gaussian Random Projection" [J]. Journal of Computer Research and Development,2008,45 (8):1402-1407
[14]David L. Donoho "Compressed Sensing" [J].IEEE Transactions on Information Theory, vol.52, No.4, April 2006:289-1306
[15]Hong Fang, Quanbing Zhang, Sui Wei, "Method of Image Reconstruction Based on very sparse random Projection" [J].Computer Engineering and Application,2007, 43 (22):25-27
[16]Emmanuel Candes, "ComPressive sampling"[J]. Proceedings of the International Congress of Mathematicans, Madrid, Spain,2006,3:1433-1452
[17]Y. Tsaig, D. Donoho, "Extenstion of compressed sensing" [J]. Signal Processing, 2006,86 (3),549-571
[18]W. Yin, S. P. Morgan, J. Yang, "Practical compressive sensing with Toeplitz and to VOIP" 2010
[19]T. Do, T.D. Trany, L. Gan, "Fast compressive sampling with structurally Random matrices" [J]. Proceedings of the IEEE International Conference on Acoustics, Speech and Signal Processing, Washington D.C, USA:IEEE,2008,47-50
[20]Justin Rombery, "Compressive sensing by random convolution" [J].SIAM Journal on Imaging Sciences, Nov.2009,2 (4):1098-1128
[21]Lome Applebaum, Stephen Howard, Stephen Searle, Robert Calderbank, "Chirp sensing code:Deterministic compressed sensing measurements for fast recovery", Preprint,2008,AValiable:httP//dsp.rice.edu/cs
[22]Radu Berinde, Piotr Indyk, "Sparse recovery using sparse random matrices",2008, preprint [online]. Available:http//dsp.rice.edu/cs
[23]Fiqueiredo M A T, Nowak R D, Wright S J. "Gradient projection for sparse recon struction:Application to compressed sensing and other inverse problems", IEEE Jour nal of Selected Topics in Signal Processing,2007,1(4):586-598.
[24]Kim S, Koh K, Lustig M, Boyd S, Gorinevsky D. "An interior-point method for 1 arge-scale regularized least squares", IEEE Journal of Selected Topics in Signal Proce ssing,2007,1(4):606-617.
[25]Thong T Do, Gan Lu, Nguyen, and Tran D. "Sparsity adaptive matching pursuit algorithm for practical compressed sensing" [J]. Asilomar Conference on Signals, Systems, and Computers, Pacific Grove, California,2008,10:581-587.
[26]Liu Yaxin, Zhao Ruizhen, Hu Shahai, Jiang Chunhui, "Regularized Adaptive Matching Pursuit Algorithm for Signal Reconstruction Based on Compressive Sensing" [J], Journal of Electronics&Information Technology, Vol.32No.11,Nov.2010
[27]M Herman, T Strohmer. "High-resolution radar via compressed sensing", [J].IEEE Transactions on Signal Processing,2009,57 (6):2275-2284.
[28]Kirolos S, Laska J, Wakin M, Duarte M,Baron D,Ragheb T, Massoud Y, Baraniu k R. "Analog-to-information conversion via random demodulation" [J].Design, Appli cations, Integration and Software, IEEE Dallas/CAS Workshop on,71-74, Oct,2006.
[29]Laska J, Kirolos S, Massoud Y etc. "Random sampling for analog-to-information conversion of wideband signals", [A].Proceedings of the IEEE Dallas Circuits and Sy stems Workshop (DCAS'06) [C].Dallas, Texas,2006.
[30]Wang W, Garofalakis M, Ramchandran K. "Distributed sparse random projection s for refinable approximation", [A]. Proceedings of the Sixth International Symposiu m on Information Processing in Sensor Networks (IPSN2007) [C].New York:Associa tion for Computing Machinery,2007.3312339.
[31]J.Bobin, J.Starck, R.Ottensamer, "Compressed sensing in astronomy" [J]. Applied Mathematics and Computation,2008,206(2):980-988
[32]Takhar D, Laska J, Wakin M etc. "A new compressive imaging camera architectu re using optical domain compression", [A]. Proceedings of SPIE [C]. Bellingham WA international Society for Optical Engineering.2006-6065.
[33]Chens, Donohod.L, Saundersma. "Atomic Decomposition by Basis pursuit" [J], SIAM J.Sci.Comp,1999,20(l):33-61.
[34]Rui Guosheng, Wang Lin,Tian Wenbiao, "Improved algorithm based basis Pursuit for compressive sensing reconstruction" [J]. Electronic Measurement Technology,2010,33(4):38-41
[35]Tropp J, Gilbert A. "Signal.recovery from random measurements via orthogonal matching pursuit", [J].Transactions on Information Theory,2007,53(12):4655-4666.
[36]Donoho D L, Tsaig Y, Drori I, Starck J L. "Sparse solution of underdetermined li near equations by stagewise orthogonal matching pursuit (StOMP)". Submitted for pu blication.
[37]Needell D, Vershynin R. "Uniform uncertainty principle and signal recovery via r egularized orthogonal matching pursuit". Found. Computer, Math.2008.
[38]M.A.T.Figueiredo, R.D.Nowak, and S.J.Wright, "Gradient projection for sparse reconstruction:application to compressed sensing and other inverse Problems" [J]. submitte,2007.
[39]高睿,赵瑞珍,胡绍海.基于压缩感知的变步长自适应匹配追踪重建算法[J].光学学报,2010,30(6)：1639-1644.
[40]陆建.最小二乘法及其应用[J].中国西部科技,2007,(12)：19-21
[41]杨明,刘先忠.矩阵论,武汉：华中科技大学出版社,2005
[42]李新,何传江.矩阵理论及其应用[M].重庆：重庆大学出版社,2005：130-145
[43]Joanne A. Foster John G.,Martin R. Davies and Jonathon A. Chambers. "An Algorithm for Calculating the QR and Singular Value Decompositions of Polynomial Matrices", [J]. IEEE Transactions On Signal Processing, March,2010,58 (3):1263-1274.
[44]李建东矩阵QR分解的三种方法[J].吕凉学院学报,2009,25(1)：16-19
[45]罗小桂.矩阵奇异值分解及其应用[J].井冈山学院学报,2005,12(4)：133-135
[46]吴昌愙,魏洪增主编.矩阵理论与方法[M].北京：电子工业出版社,2006.
[47]鲁铁定,宁津生等,最小二乘配置的QR分解解法[J].辽宁工程技术大学学报,2009,28(4)：550-553.
© 2004-2018 中国地质图书馆版权所有 京ICP备05064691号 京公网安备11010802017129号 地址：北京市海淀区学院路29号 邮编：100083 电话：办公室：(+86 10)66554848；文献借阅、咨询服务、科技查新：66554700 |