压缩传感中信号重构算法的研究
|
摘要
压缩传感是一种新型的数字信号处理方法。它最大的突破在于实现了当采样点数少于奈奎斯特采样点数时也能够精确的重构出原始信号。压缩传感理论合并了采样和压缩的过程,降低了信号处理的复杂度,使其在许多领域得到了大量应用。信号的重构是压缩传感中必不可少的一部分。本文主要对压缩传感中的信号重构算法进行了深入的研究。
首先,本文分析了压缩传感的基本原理,包括稀疏信号的构建、测量矩阵生成与性质以及重构算法的基本思想。在分析了压缩传感基本思想的基础之上,研究了现阶段主要存在的重构算法。并且分析了扩展图的存在性及其本身所具有特殊性质。
其次,本文对最小l1范数重构算法和正交匹配追踪追踪重构算法(OMP)做了是深入研究。分析了两种算法的实现方法,研究了最小l1范数算法的求解过程,并分别给出了两种算法的仿真实现流程图。然后,本文完成了对两种算法性能的分析,在输入信号不同的条件下,分别研究了算法的重构精度与信号稀疏水平、测量矩阵个数等参数之间的关系。接着对算法的重构精度、实现复杂度和应用条件进行了分析和比较。
最后,本文研究了基于扩展图理论的信号重构算法,分别设计了用扩展图算法重构稀疏信号和近似稀疏信号的仿真流程。由于精确构建扩展图是一个较难解决的问题,本文设计利用随机产生的规则的二分图作为算法中所需要的扩展图。在输入不同信号的情况下,分析了扩展图算法的可行性与算法自身的特性。最后对三种算法的重构精度和重构时间进行分析和比较,找出算法的各自优越性。
Compressive sensing is a new type of digital signal processing method. The novel objective of compressive sengsing is to reconstruct a signal accurately and efficiently from far fewer sampling points got by Nyquist Sampling Theorem.Compressive sensing theory combines the process of sampling and compression to reduce the complexity of signal processing, which is widely used in many fields. Signal reconstruction is an essential part of the compressed sensing. This paper focuses on the algorithms of signal reconstruction.
Firstly, the basic principle of compressive sensing, including the costruction of sparse signals, the measurement matrix and the basic idea of recongstruction algorithms is analyzed. Based on the theory of compressive sensing, the main reconstruction algotithms are summed up. Special charaters and the existence of expander graphs are discussed.
Secondly, minimum l1 -norm reconstruction algorithm and Orthogonal Matching Pursuit (OMP) reconstruction algorithm are deeply studied in this paper. The realizable schemes of two methods are ananlyzed, and the solving process of minimum l1 -norm algorithm is researched. Then the simulation flow charts of two algorithms are given. We analyze the performance of minimum l1 -norm algorithm and OMP algorithm by the simulation results, respectively study the relationship amony reconstruction accuracy of the algorith、sparsity level of signals and the number of measurement entries with different input signals.
Finally, the signal reconstruction algorithm using expander graph is studied. We designed the simulation system and flow of reconstruction algorithms using expander graph for sparse signal and approximate sparse signal. Explicit constructions of the considered expander graphs are very difficult. According to the theorems, we randomly generate a regular bipartite graph with a uniform distribution as the expander graph for simulation. We ananlyze the feasibility and characters of the recovery algorithm using expander graph under different input singals. Finally, we compare the accuracy of reconstruction and the recovery time of three algorithms, and analyze the respective advantages of algorithms.
首先,本文分析了压缩传感的基本原理,包括稀疏信号的构建、测量矩阵生成与性质以及重构算法的基本思想。在分析了压缩传感基本思想的基础之上,研究了现阶段主要存在的重构算法。并且分析了扩展图的存在性及其本身所具有特殊性质。
其次,本文对最小l1范数重构算法和正交匹配追踪追踪重构算法(OMP)做了是深入研究。分析了两种算法的实现方法,研究了最小l1范数算法的求解过程,并分别给出了两种算法的仿真实现流程图。然后,本文完成了对两种算法性能的分析,在输入信号不同的条件下,分别研究了算法的重构精度与信号稀疏水平、测量矩阵个数等参数之间的关系。接着对算法的重构精度、实现复杂度和应用条件进行了分析和比较。
最后,本文研究了基于扩展图理论的信号重构算法,分别设计了用扩展图算法重构稀疏信号和近似稀疏信号的仿真流程。由于精确构建扩展图是一个较难解决的问题,本文设计利用随机产生的规则的二分图作为算法中所需要的扩展图。在输入不同信号的情况下,分析了扩展图算法的可行性与算法自身的特性。最后对三种算法的重构精度和重构时间进行分析和比较,找出算法的各自优越性。
Compressive sensing is a new type of digital signal processing method. The novel objective of compressive sengsing is to reconstruct a signal accurately and efficiently from far fewer sampling points got by Nyquist Sampling Theorem.Compressive sensing theory combines the process of sampling and compression to reduce the complexity of signal processing, which is widely used in many fields. Signal reconstruction is an essential part of the compressed sensing. This paper focuses on the algorithms of signal reconstruction.
Firstly, the basic principle of compressive sensing, including the costruction of sparse signals, the measurement matrix and the basic idea of recongstruction algorithms is analyzed. Based on the theory of compressive sensing, the main reconstruction algotithms are summed up. Special charaters and the existence of expander graphs are discussed.
Secondly, minimum l1 -norm reconstruction algorithm and Orthogonal Matching Pursuit (OMP) reconstruction algorithm are deeply studied in this paper. The realizable schemes of two methods are ananlyzed, and the solving process of minimum l1 -norm algorithm is researched. Then the simulation flow charts of two algorithms are given. We analyze the performance of minimum l1 -norm algorithm and OMP algorithm by the simulation results, respectively study the relationship amony reconstruction accuracy of the algorith、sparsity level of signals and the number of measurement entries with different input signals.
Finally, the signal reconstruction algorithm using expander graph is studied. We designed the simulation system and flow of reconstruction algorithms using expander graph for sparse signal and approximate sparse signal. Explicit constructions of the considered expander graphs are very difficult. According to the theorems, we randomly generate a regular bipartite graph with a uniform distribution as the expander graph for simulation. We ananlyze the feasibility and characters of the recovery algorithm using expander graph under different input singals. Finally, we compare the accuracy of reconstruction and the recovery time of three algorithms, and analyze the respective advantages of algorithms.
引文
[1] Donoho D. Compressed sensing [J]. IEEE Transactionsion Information Theory, 2006,52(4):1289-1306
[2] Candès E. Compressive sampling. Proeeedings of intemational congress of mathematieians:[C]. Ztirie, Switzeriand : European Mathematical Soeiety Publishing House,2006.1433-1452
[3] Candès E, Romberg J, Tao J. Robust uncertainty principles: Exact signal recon- struction from highly incomplete frequency information [J].IEEE Transactions on Information Theory, 2006,52 (2):489-509.
[4]李树涛,魏丹.压缩传感综述[J].自动化学报,2009,11(35):1369-1377.
[5] Duarte M F, Davenport M A, Takhar D, Sun T, ec al. Single-Pixel imaging via compressive sampling [J]. IEEE Signal Proeessing Magazine, 2008, 25 (2):83-9.
[6] Candès E,Tao T. Decoding by linear programming [J]. IEEE Transactions on Information Theory, 2005, 51(12):4203-4215
[7]肖龙帅,黄华,夏建刚,等.压缩传感方位估计[J].通信技术,2009,11 (42): 182-184.
[8] Bajwa W, Haupt J, Sayeed A, Nowak R. Compressive wireless sensing[C]. In: Proceedings of the International Conference on Information Processing in Sensor Networks. Nashville, USA: ACM, 2006. 134-142.
[9] Baraniuk R, Steeghs P. Compressive radar imaging[C]. In: Proceedings of the Radar Conference. Washington D. C., USA: IEEE, 2007. 128-133.
[10] Lustig M, Donho D L, Pauly J M. Sparse MRI: The application of compre-ssed sensing for rapid MR imaging [J]. Magnetic Resonance in Medicine, 2007, 58(6):1182-1195.
[11] Sheikh M A, Milenkovic O, Baraniuk R G. Designing compressive sensing DNA microarrays[C]. In: Proceedings of the IEEE International Workshop on Computational Advances in Multi-Sensor Adaptive Processing. Washing- ton D. C., USA: IEEE, 2007. 141-144.
[12] Foucart S and Lai M.-J. Sparsest solutions of undetermined linear systems via lq-minimization for 0 ? q ?1[J]. Applied and Computational Harmonic Analysis, 2009, 26:395-407.
[13] Davies M E ,Gribonval R. Restricted isometry constants where ?p sparse recovery can fail for 0 ? p ?1[J]. IEEE Transaction on Information Theory. 2009, 55 (5):2203-2214.
[14] Fiqueiredo M A T, Nowak R D,Wright S J. Gradient projection for sparse reconstruction: Application to compressed sensing and other inverse pro-blems[J]. IEEE Journal of Selected Topics in Signal Processing, 2007, 1(4): 586-598.
[15] Tropp J, Gilbert A. Signal recovery from random measurements via ortho- gonal matching pursuit [J]. Transactions on Information Theory, 2007, 53 (12): 4655-4666
[16] Blumensath T and Davies M E. Iterative hard thresholding for compressed sensing [J]. Applied and Computational Harmonic Analysis, 2009, 26:265-407.
[17] Fornasier M and Rauhut H. Iterative thresholding algorithms [J]. Applied and Computational Harmonic Analysis, 2009, 25(2):187-208.
[18] Donoho D L, Tsaig Y, Drori I, et al. Sparse solution of underde-termined linear equations by stagewise Orthogonal Matching Pursuit (StOMP)[R]. Teohnical report, Stanford University. 2006.
[19] Xu W and Hassibi B.Efficient Compressive Sensing with Deterministic Guarantees using Expander Graphs[C]. Proceedings of IEEE Information Theroy Workshop, Lake Tahoe, 2007:414-419.
[20] Baron D, Sarvotham Sh, and R.Baraniuk. Bayesian Compressed Sensing via Belief Propagation [R] . Rice ECE Department Technical Report TREE 0601, 2006.
[21] Candès E J, Li X, Ma Y, and Wright. Robust principal component analysis? [R]. Technical report, Stanford University, 2009.
[22] Hu S, Lustig M, Chen A P, Crane J, Kerr A, Kelley D A C. Compressed sen-sing for resolution enhancement of hyperpolarized 13C flyback 3D-MRSI [J]. Journal of Magnetic Resonance, 2008, 192(2): 258-264
[23] Bhattacharya S, Blumensath T, Mulgrew B, Davies M. Fast encoding of synthetic aperture radar raw data using compressed sensing [C]. In: Procee-dings of the 14th Workshop on Statistical Signal Processing. Washington D. C., USA: IEEE, 2007: 448-452.
[24]王蜀南.压缩传感在超宽带通信中的应用[D].吉林:吉林大学学位论文2010:22-25.
[25]何雪云,宋荣方,周克琴.基于感知的OFDM系统稀疏信道估计新方法的研究[J].南京邮电大学学报(自然科学版),2010, 30(2):60-65.
[26]石光明,刘丹华,高大化等.压缩感知理论及其研究进展[J].电子学报,2009,37(5):1070-1078.
[27] Baraniuk R. Compressive sensing [J]. IEEE Signal Proeessing Magazine,2007, 24(4):118-121.
[28] Boggess A , Narcowich F J.小波与傅里叶分析基础(第二版)[M].芮国强,康健译,电子工业出版社,2010:189-195.
[29] Baraniuk R G, Davenport M, DeVore R,et al. The Johnson-Lindenstrauss lemma meets compressed sensing. 2006, dsp.rice.edu/cs/jlcs-v03.pdf.
[30] Candès E,Tao T. Near optimal signal recovery from random projections: Universal encoding strategies [J].IEEE Transactions on Information Theory, 2006,52(12):5406-5425.
[31] Candès E, Romberg J.Sparsity and incoherence in compressive sampling [J]. Inverse Problems, 2007, 23 (3):969-985.
[32]李波,谢杰镇,王博亮.基于压缩传感理论的数据重建[J].计算机技术与发展.2009, 19 (5):23-25.
[33] Tropp J A, Gilbert A C, Muthukrishnan S, et al. Improved sparse approxi-mation over quasi-incoherent dictionaries [C]. In Proc. of the 2003 IEEE International Conference on Image Processing, Barcelona, 2003.
[34] Candès E and Romberg J. Practical Signal Recovery from Random Projec-tions[C]. In Computational Imaging:Proc.SPIE International Symposium on Electronic Imaging, San Jose,CA.2005:76-86.
[35] Cormode G and Muthukrishnan S.Combinatorial Algorithms for Compre-ssed Sensing [R].Technical Report DIMACS TR 200540, 2005.
[36]金坚,谷源涛,梅顺良.压缩采样技术及应用[J].电子与信息学报. 2010, 32(2): 470-473.
[37] Sarvotham S, Dror Baron, and Richard Baraniuk.Sudocodes Fast Measure- ment and Reconstruction of Sparse Signals[C], Proc.IEEE Int. Symposium on Information Theory (ISIT), Seattle, WA, July 2006.
[38] D. Donoho and Y. Tsaig.Fast solution of l1-norm minimization problems when the solution may be sparse [R]. Technical report, Stanford.2006.
[39] Fuchs J J. Sparsity and Uniqueness for some Speci?c Underdetermined Lin-ear Systems. IEEE ICASSP, vol V [C]. Philadelphia. 2005: 729-732.
[40] DeVore R A. Deterministic constructions of compressed sensing matrices[J]. Journal of Complexity. 2007, 23(4-6):918-925.
[41] Capalbo M , Reingold O, Vadhan S, et al.Randomness Conductors and Con-stant-Degree Expansion Beyond the Degree/2 Barrier[C].Proc. of the 34th STOC.2002: 659-668.
[42] Sipser M and Spielman D. Expander codes [J] .IEEE Transactions on Infor-mation Theory. 1996,142(6): 1710-1722.
[43] Candès E, Romberg J, and Tao T. Stable signal recovery from incomplete and inaccurate measurements [J]. Communications on Pure and Applied Mathematics. 2006, 59(8):1207–1223,.
[44] Mallat S and Zhang Z. Matching Pursuits with time-frequency dictionaries [J].IEEE Trans. Signal Process. 1993,41(12):3397–3415.
[45] Bassalygo L A and Pinsker M S. Complexity of an optimum nonblocking switching network without reconnections [J].Problems in Information Trans-mission.1973,9(1):84-87.
[46] Jafarpour S, Xu W, Hassibi B, and Caladerbank R, Efficient compressed Sensing using Optimized Expaner Graphs [J]. IEEE Trans. Inf. Theory, 2009, 55(9):4299-4308.
[47] Xu Weiyu and Hassibi Babak, Further Results on Performance Analysis for Compressive Sensing Using Expander Graphs[C].Signals, Systems and Computers, 2007.ACSSC 2007. Conference Record of the Forty-First Asilo-mar Conference on 4-7 Nov.2007:621-625.
[48] Eli Upfal and AviWigderson. How to share memory in a distributed system. J. Assoc. Comput. Mach.1987, 34(1):116–127.
[49] Berinde R, Gilbert A, Indyk P, et al.Combining geometry and combinatorics: a unified approach to sparse signal recovery [C]. 46th Annual Allerton Con- fernence on Communication, Control, and Computing.2008:798-805.
[50] Hoory S, Linial N, and Wigderson A.Expander graphs and their applications. Bulletin of the American Mathematical Society. 2006,43:439-561.
[2] Candès E. Compressive sampling. Proeeedings of intemational congress of mathematieians:[C]. Ztirie, Switzeriand : European Mathematical Soeiety Publishing House,2006.1433-1452
[3] Candès E, Romberg J, Tao J. Robust uncertainty principles: Exact signal recon- struction from highly incomplete frequency information [J].IEEE Transactions on Information Theory, 2006,52 (2):489-509.
[4]李树涛,魏丹.压缩传感综述[J].自动化学报,2009,11(35):1369-1377.
[5] Duarte M F, Davenport M A, Takhar D, Sun T, ec al. Single-Pixel imaging via compressive sampling [J]. IEEE Signal Proeessing Magazine, 2008, 25 (2):83-9.
[6] Candès E,Tao T. Decoding by linear programming [J]. IEEE Transactions on Information Theory, 2005, 51(12):4203-4215
[7]肖龙帅,黄华,夏建刚,等.压缩传感方位估计[J].通信技术,2009,11 (42): 182-184.
[8] Bajwa W, Haupt J, Sayeed A, Nowak R. Compressive wireless sensing[C]. In: Proceedings of the International Conference on Information Processing in Sensor Networks. Nashville, USA: ACM, 2006. 134-142.
[9] Baraniuk R, Steeghs P. Compressive radar imaging[C]. In: Proceedings of the Radar Conference. Washington D. C., USA: IEEE, 2007. 128-133.
[10] Lustig M, Donho D L, Pauly J M. Sparse MRI: The application of compre-ssed sensing for rapid MR imaging [J]. Magnetic Resonance in Medicine, 2007, 58(6):1182-1195.
[11] Sheikh M A, Milenkovic O, Baraniuk R G. Designing compressive sensing DNA microarrays[C]. In: Proceedings of the IEEE International Workshop on Computational Advances in Multi-Sensor Adaptive Processing. Washing- ton D. C., USA: IEEE, 2007. 141-144.
[12] Foucart S and Lai M.-J. Sparsest solutions of undetermined linear systems via lq-minimization for 0 ? q ?1[J]. Applied and Computational Harmonic Analysis, 2009, 26:395-407.
[13] Davies M E ,Gribonval R. Restricted isometry constants where ?p sparse recovery can fail for 0 ? p ?1[J]. IEEE Transaction on Information Theory. 2009, 55 (5):2203-2214.
[14] Fiqueiredo M A T, Nowak R D,Wright S J. Gradient projection for sparse reconstruction: Application to compressed sensing and other inverse pro-blems[J]. IEEE Journal of Selected Topics in Signal Processing, 2007, 1(4): 586-598.
[15] Tropp J, Gilbert A. Signal recovery from random measurements via ortho- gonal matching pursuit [J]. Transactions on Information Theory, 2007, 53 (12): 4655-4666
[16] Blumensath T and Davies M E. Iterative hard thresholding for compressed sensing [J]. Applied and Computational Harmonic Analysis, 2009, 26:265-407.
[17] Fornasier M and Rauhut H. Iterative thresholding algorithms [J]. Applied and Computational Harmonic Analysis, 2009, 25(2):187-208.
[18] Donoho D L, Tsaig Y, Drori I, et al. Sparse solution of underde-termined linear equations by stagewise Orthogonal Matching Pursuit (StOMP)[R]. Teohnical report, Stanford University. 2006.
[19] Xu W and Hassibi B.Efficient Compressive Sensing with Deterministic Guarantees using Expander Graphs[C]. Proceedings of IEEE Information Theroy Workshop, Lake Tahoe, 2007:414-419.
[20] Baron D, Sarvotham Sh, and R.Baraniuk. Bayesian Compressed Sensing via Belief Propagation [R] . Rice ECE Department Technical Report TREE 0601, 2006.
[21] Candès E J, Li X, Ma Y, and Wright. Robust principal component analysis? [R]. Technical report, Stanford University, 2009.
[22] Hu S, Lustig M, Chen A P, Crane J, Kerr A, Kelley D A C. Compressed sen-sing for resolution enhancement of hyperpolarized 13C flyback 3D-MRSI [J]. Journal of Magnetic Resonance, 2008, 192(2): 258-264
[23] Bhattacharya S, Blumensath T, Mulgrew B, Davies M. Fast encoding of synthetic aperture radar raw data using compressed sensing [C]. In: Procee-dings of the 14th Workshop on Statistical Signal Processing. Washington D. C., USA: IEEE, 2007: 448-452.
[24]王蜀南.压缩传感在超宽带通信中的应用[D].吉林:吉林大学学位论文2010:22-25.
[25]何雪云,宋荣方,周克琴.基于感知的OFDM系统稀疏信道估计新方法的研究[J].南京邮电大学学报(自然科学版),2010, 30(2):60-65.
[26]石光明,刘丹华,高大化等.压缩感知理论及其研究进展[J].电子学报,2009,37(5):1070-1078.
[27] Baraniuk R. Compressive sensing [J]. IEEE Signal Proeessing Magazine,2007, 24(4):118-121.
[28] Boggess A , Narcowich F J.小波与傅里叶分析基础(第二版)[M].芮国强,康健译,电子工业出版社,2010:189-195.
[29] Baraniuk R G, Davenport M, DeVore R,et al. The Johnson-Lindenstrauss lemma meets compressed sensing. 2006, dsp.rice.edu/cs/jlcs-v03.pdf.
[30] Candès E,Tao T. Near optimal signal recovery from random projections: Universal encoding strategies [J].IEEE Transactions on Information Theory, 2006,52(12):5406-5425.
[31] Candès E, Romberg J.Sparsity and incoherence in compressive sampling [J]. Inverse Problems, 2007, 23 (3):969-985.
[32]李波,谢杰镇,王博亮.基于压缩传感理论的数据重建[J].计算机技术与发展.2009, 19 (5):23-25.
[33] Tropp J A, Gilbert A C, Muthukrishnan S, et al. Improved sparse approxi-mation over quasi-incoherent dictionaries [C]. In Proc. of the 2003 IEEE International Conference on Image Processing, Barcelona, 2003.
[34] Candès E and Romberg J. Practical Signal Recovery from Random Projec-tions[C]. In Computational Imaging:Proc.SPIE International Symposium on Electronic Imaging, San Jose,CA.2005:76-86.
[35] Cormode G and Muthukrishnan S.Combinatorial Algorithms for Compre-ssed Sensing [R].Technical Report DIMACS TR 200540, 2005.
[36]金坚,谷源涛,梅顺良.压缩采样技术及应用[J].电子与信息学报. 2010, 32(2): 470-473.
[37] Sarvotham S, Dror Baron, and Richard Baraniuk.Sudocodes Fast Measure- ment and Reconstruction of Sparse Signals[C], Proc.IEEE Int. Symposium on Information Theory (ISIT), Seattle, WA, July 2006.
[38] D. Donoho and Y. Tsaig.Fast solution of l1-norm minimization problems when the solution may be sparse [R]. Technical report, Stanford.2006.
[39] Fuchs J J. Sparsity and Uniqueness for some Speci?c Underdetermined Lin-ear Systems. IEEE ICASSP, vol V [C]. Philadelphia. 2005: 729-732.
[40] DeVore R A. Deterministic constructions of compressed sensing matrices[J]. Journal of Complexity. 2007, 23(4-6):918-925.
[41] Capalbo M , Reingold O, Vadhan S, et al.Randomness Conductors and Con-stant-Degree Expansion Beyond the Degree/2 Barrier[C].Proc. of the 34th STOC.2002: 659-668.
[42] Sipser M and Spielman D. Expander codes [J] .IEEE Transactions on Infor-mation Theory. 1996,142(6): 1710-1722.
[43] Candès E, Romberg J, and Tao T. Stable signal recovery from incomplete and inaccurate measurements [J]. Communications on Pure and Applied Mathematics. 2006, 59(8):1207–1223,.
[44] Mallat S and Zhang Z. Matching Pursuits with time-frequency dictionaries [J].IEEE Trans. Signal Process. 1993,41(12):3397–3415.
[45] Bassalygo L A and Pinsker M S. Complexity of an optimum nonblocking switching network without reconnections [J].Problems in Information Trans-mission.1973,9(1):84-87.
[46] Jafarpour S, Xu W, Hassibi B, and Caladerbank R, Efficient compressed Sensing using Optimized Expaner Graphs [J]. IEEE Trans. Inf. Theory, 2009, 55(9):4299-4308.
[47] Xu Weiyu and Hassibi Babak, Further Results on Performance Analysis for Compressive Sensing Using Expander Graphs[C].Signals, Systems and Computers, 2007.ACSSC 2007. Conference Record of the Forty-First Asilo-mar Conference on 4-7 Nov.2007:621-625.
[48] Eli Upfal and AviWigderson. How to share memory in a distributed system. J. Assoc. Comput. Mach.1987, 34(1):116–127.
[49] Berinde R, Gilbert A, Indyk P, et al.Combining geometry and combinatorics: a unified approach to sparse signal recovery [C]. 46th Annual Allerton Con- fernence on Communication, Control, and Computing.2008:798-805.
[50] Hoory S, Linial N, and Wigderson A.Expander graphs and their applications. Bulletin of the American Mathematical Society. 2006,43:439-561.