贪婪算法与压缩感知理论

方红; 杨海蓉

doi:10.3724/SP.J.1004.2011.01413

贪婪算法与压缩感知理论

doi: 10.3724/SP.J.1004.2011.01413

方红^1, ,,
杨海蓉²

1.
上海第二工业大学理学院上海 201209;
2.
合肥师范学院数学系合肥 230601

详细信息

通讯作者:
方红上海第二工业大学理学院副教授.主要研究方向为图像处理. E-mail: fanghong@sf.sspu.cn

计量
- 文章访问数: 3121
- HTML全文浏览量: 104
- PDF下载量: 5439
- 被引次数: 0
出版历程
- 收稿日期: 2010-09-06
- 修回日期: 2011-07-14
- 刊出日期: 2011-12-20

Greedy Algorithms and Compressed Sensing

FANG Hong^{1
, ,},
YANG Hai-Rong²

1.
School of Science, Shanghai Second Polytechnic University, Shanghai 201209;
2.
Department of Mathematics, Hefei Normal University, Hefei 230601

摘要

摘要: 贪婪算法以其重建速度快、重建方法实现简便的特点在压缩感知(Compressed sensing, CS)理论中获得了广泛的应用. 本文首先介绍压缩感知的基本理论;然后,着重介绍现有几种重要的贪婪重建算法,包括MP, OMP, IBOOMP, StOMP, SP, ROMP和CoSaMP等, 详细给出每种算法的数学框架和本质思想,着重从最优匹配原子的选择策略和残差信号的更新方式这两个方面对各种算法进行对比分析,以限制等容常数为条件讨论各种算法在实现重建时的性能,包括重建时间、重建的稳定性等;最后,通过模拟实验进一步验证了各种算法的重建效果,同时模拟实验结果还进一步得出各种算法的重建效果与待重建信号本身的稀疏度及测量次数这三者之间的关系,这也为新的更优算法的提出打下理论基础.
- 贪婪算法 /
- 压缩感知 /
- 限制等容常数 /
- 残差 /
- 稀疏度
Abstract: Recently a family of iterative greedy algorithms have received extensive application in compressed sensing (CS) due to their fast reconstruction and low reconstruction complexity. In this paper, the basic theory of CS is first introduced and then we put emphasis on the main greedy algorithms for reconstruction, which include MP, OMP, IBOOMP, StOMP, SP, ROMP, CoSaMP and so on and provide their mathematical frameworks, respectively. Next, we classify all the algorithms according to the strategy of element selection and the update of the residual error. Under the condition of restricted isometry constant, further discussion on the performance of reconstruction algorithms such as running time, reconstruction stability and so on is presented. Last, the reconstruction results from simulated experiments further show the performance of all algorithms. And from those results we also acquire the relationship among the performance of the algorithms, the sparsity of signals to be reconstructed and the number of measurements, which lays a good basis for proposing new and better algorithms.
- Greedy algorithms /
- compressed sensing (CS) /
- restricted isometry constant /
- residual error /
- sparsity

HTML全文

参考文献(1)

[1]

Donoho D L. Compressed sensing. IEEE Transactions on Information Theory, 2006, 52(4): 1289-1306[2] Candes E J. Compressive sampling. In: Proceedings of the International Congress of Mathematics. Madrid, Spain: the European Mathematical Society, 2006. 1433-1452[3] Donoho D L, Huo X. Uncertainty principles and ideal atomic decompositions. IEEE Transactions on Information Theory, 2001, 47(7): 2845-2862[4] Donoho D L, Elad M. Optimally sparse representation in general (nonorthogonal) dictionaries via L1 minimization. Proceedings of the National Academy of Sciences USA, 2003, 100(5): 2197-2202[5] Laska J N, Kirolos S, Duarte M F, Ragheb T S, Baraniuk R G, Massoud Y. Theory and implementation of an analog-to-information converter using random demodulation. In: Proceedings of the IEEE International Symposium on Circuits and Systems. New Orleans, USA: IEEE, 2007. 1959-1962[6] Ragheb T, Kirolos S, Laska J, Gilbert A, Strauss M, Baraniuk R, Massoud Y. Implementation models for analog-to-information conversion via random sampling. In: Proceedings of the 50th Symposium on Circuits and Systems. Montreal, Canada: IEEE, 2007. 325-328[7] Bajwa W, Haupt J, Sayeed A, Nowak R. Compressive wireless sensing. In: Proceedings of the 5th International Conference on Information Processing in Sensor Networks. New York, USA: IEEE, 2006. 134-142[8] Chen S B, Donoho D L, Saunders M A. Atomic decomposition by basis pursuit. SIAM Journal on Scientific Computing, 1998, 20(1): 33-61[9] Figueiredo M A, Nowak R D, Wright S J. Gradient projection for sparse reconstruction: application to compressed sensing and other inverse problems. IEEE Journal of Selected Topics in Signal Processing, 2007, 1(4): 586-597[10] Daubechies I, Defrise M, De Mol C. An iterative thresholding algorithm for linear inverse problems with a sparsity constraint. Communications on Pure and Applied Mathematics, 2004, 57(11): 1413-1457[11] Blumensath T, Davies M. Iterative hard thresholding for compressed sensing. Applied and Computational Harmonic Analysis, 2009, 27(3): 265-274[12] Cai J F, Osher S, Shen Z W. Linearized Bregman iterations for compressed sensing. Mathematics of Computation, 2008, 78(267): 1515-1536[13] Yin W, Osher S, Goldfarb D, Darbon J. Bregman iterative algorithms for L1-minimization with applications to compressed sensing. SIAM Journal on Imaging Sciences, 2008, 1(1): 143-168[14] Osher S, Mao Y, Dong B, Yin W T. Fast linearized Bregman iteration for compressive sensing and sparse denoising. Communications in Mathematical Sciences, 2010, 8(1): 93-111[15] Cai J F, Osher S, Shen Z W. Convergence of the linearized Bregman iteration for L1-norm minimization. Mathematics of Computation, 2009, 78(268): 2127-2136[16] Gilbert A C, Guha S, Indyk P, Muthukrishnan S, Strauss M J. Near-optimal sparse Fourier representations via sampling. In: Proceedings of the 34th Annual ACM Symposium on Theory of Computing. New York, USA: ACM, 2000. 152-161[17] Gilbert A, Strauss M, Tropp J, Vershynin R. Algorithmic linear dimension reduction in the L1 norm for sparse vectors. In: Proceedings of the 44th Annual Allerton Conference on Communication, Control and Computing. Allerton, USA: Curran Associates, 2006. 1-9[18] Gormode G, Muthukrishan S. Combinatorial algorithms for compressed sensing. In: Proceedings of the 40th Annual Conference on Information Sciences and Systems. Princeton, USA: IEEE, 2006. 280-294[19] Gilbert A, Strauss M, Tropp J, Vershynin R. One sketch for all: fast algorithms for compressed sensing. In: Proceedings of the 39th Annual ACM Symposium on Theory of Computing. New York, USA: ACM, 2007. 237-246[20] Zayyani H, Babaie-Zadeh M, Jutten C. Bayesian pursuit algorithm for sparse representation. In: Proceedings of the IEEE International Conference on Acoustics, Speech and Signal Processing. Taipei, China: IEEE, 2009. 1549-1552[21] Baron S, Sarvoham R, Baraniuk R G. Bayesian compressive sensing via belief propagation. IEEE Transactions on Signal Processing, 2010, 58(1): 269-280[22] Seeger M W, Steinke F, Tsuda K. Bayesian inference and optimal design in the sparse linear model. Journal of Machine Learning Research-Proceedings Track, 2007, 2(6): 444-451[23] Weiss Y, Chang H S, Freeman W T. Learning compressed sensing. In: Proceedings of the 45th Allerton Conference on Communications, Control and Computing. Illinois, USA: Curran Associates, 2007. 1-7[24] Mallat S, Zhang Z. Matching pursuit with time-frequency dictionaries. IEEE Transactions on Signal Processing, 1993, 41(12): 3397-3415[25] Tropp J, Gilbert A. Signal recovery from random measurements via orthogonal matching pursuit. IEEE Transactions on Information Theory, 2007, 53(12): 4655-4666[26] Donoho D L, Tsaig Y, Drori I, Starck J L. Sparse Solution of Underdetermined Linear Equations by Stage Wise Orthogonal Matching Pursuit, Technical Report No.2006-2, Department of Statistics, Stanford University, USA, 2006[27] Needell D, Vershynin R. Signal recovery from inaccurate and incomplete measurements via regularized orthogonal matching pursuit. IEEE Journal of Selected Topics in Signal Processing, 2010, 4(2): 310-316[28] Needell D, Tropp J A. CoSaMP: iterative signal recovery from incomplete and inaccurate samples. Applied and Computational Harmonic Analysis, 2008, 26(3): 301-321[29] Dai W, Milenkovic O. Subspace pursuit for compressive sensing signal reconstruction. IEEE Transactions on Information Theory, 2009, 55(5): 2230-2249[30] Fang Hong, Zhang Quan-Bing, Wei Sui. Image reconstruction based on improved backward optimized orthogonal matching pursuit algorithm. Journal of South China University of Technology (Natural Science), 2008, 36(8): 23-27(方红, 章权兵, 韦穗. 改进的后退型最优正交匹配追踪的图像重建方法. 华南理工大学学报(自然科学版), 2008, 36(8): 23-27)[31] Candes E, Romberg J, Tao T. Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information. IEEE Transactions on Information Theory, 2006, 52(2): 489-509[32] Candes E, Tao T. Decoding by linear programming. IEEE Transactions on Information Theory, 2005, 51(12): 4203-4215[33] Candes E, Romberg J, Tao T. Stable signal recovery form incomplete and inaccurate measurements. Communications on Pure and Applied Mathematics, 2006, 59(8): 1207-1223[34] Candes E. The restricted isometry property and its implications for compressed sensing. Comptes Rendus Mathematique, 2008, 346(9-10): 589-592[35] Foucart S, Lai M. Sparsest solutions of underdetermined linear systems via Lq-minimization for 0 q 1. Applied and Computational Harmonic Analysis, 2009, 26(3): 395-407[36] Cai T, Wang L, Xu G W. Shifting inequality and recovery of sparse signals. IEEE Transactions on Signal Processing, 2010, 58(3): 1300-1308[37] Cai T, Wang L, Xu G W. New bounds for restricted isometry constants. IEEE Transactions on Information Theory, 2010, 56(9): 4388-4394[38] Fang Hong, Zhang Quan-Bing, Wei Sui. A method of image reconstruction based on sub-Gaussian random projection. Journal of Computer Research and Development, 2008, 45(8): 1402-1407(方红, 章权兵, 韦穗. 基于亚高斯随机投影的图像重建方法. 计算机研究与发展, 2008, 45(8): 1402-1407)[39] Varadarajan B, Khudanpur S, Tran T D. Stepwise optimal subspace pursuit for improving sparse recovery. IEEE Signal Processing Letters, 2011, 18(1): 27-30[40] Candes E, Tao T. Near optimal signal recovery from random projections: universal encoding strategies? IEEE Transactions on Information Theory, 2006, 52(12): 5406-5425[41] Rudelson M, Vershynin R. Sparse reconstruction by convex relaxation: Fourier and Gaussian measurements. In: Proceedings of the 40th Annual Conference on Information Science and Systems. Princeton, USA: IEEE, 2006. 207-212[42] Takhar D, Laska J, Wakin M, Duarte M F, Baron D, Sarvotham S, Kelly K, Baraniuk R. A new compressive imaging camera architecture using optical-domain compression. In: Proceedings of the Computational Imaging IV at SPIE Electronic Imaging. San Jose, USA: SPIE, 2006. 43-52[43] Duarte M, Davenport M, Takhar D, Laska J, Sun T, Kelly K, Baraniuk R. Single-pixel imaging via compressive sampling. IEEE Signal Processing Magazine, 2008, 25(2): 83-91[44] Baraniuk R, Steeghs P. Compressive radar imaging. In: Proceedings of the IEEE Radar Conference. Boston, USA: IEEE, 2007. 128-133[45] Kirolos S, Laska J, Wakin M, Duarte M, Baron D, Ragheb T, Massoud Y, Baraniuk R. Analog-to-information conversion via random demodulation. In: Proceedings of the IEEE Dallas/CAS Workshop on Design, Applications, Integration and Software. Richardson, USA: IEEE, 2006. 71-74[46] Ragheb T, Kirolos S, Laska J, Gilbert A, Strauss M, Baraniuk R, Massoud Y. Implementation models for analog-to-information conversion via random sampling. In: Proceedings of the 50th Midwest Symposium on Circuits and Systems. Montreal, Canada: IEEE, 2007. 325-328[47] Laska J, Kirolos S, Massoud Y, Baraniuk R, Gilbert A, Iwen M, Strauss M. Random sampling for analog-to-information conversion of wideband signals. In: Proceedings of the IEEE Dallas/CAS Workshop on Design, Applications, Integration and Software. Richardson, USA: IEEE, 2006. 119-122[48] Lustig M, Donoho D L, Pauly J M. Sparse MRI: the application of compressed sensing for rapid MR imaging. Magnetic Resonance in Medicine, 2007, 58(6): 1182-1195[49] Bajwa W, Haupt J, Sayeed A M, Nowak R. Compressive wireless sensing. In: Proceedings of the 5th International Conference on Information Processing in Sensor Networks. Nashville, USA: IEEE, 2006. 134-142[50] Rabbat M, Haupt J, Singh A, Nowak R. Decentralized compression and predistribution via randomized gossiping. In: Proceedings of the 5th International Conference on Information Processing in Sensor Networks. Nashville, USA: IEEE, 2006. 51-59

施引文献

资源附件(0)

访问统计