Fangjun Arroyo^*, Edward Arroyo, Xiezhang Li, Jiehua Zhu, Jiehua Zhu

Show more
Department of Mathematics, Francis Marion University, Florence, USA.
School of Science Technology, American Public University System, Manassas, USA.
Department of Mathematical Sciences, Georgia Southern University, Statesboro, USA.
Show less

Abstract: The generalized l1 greedy algorithm was recently introduced and used to reconstruct medical images in computerized tomography in the compressed sensing framework via total variation minimization. Experimental results showed that this algorithm is superior to the reweighted l1-minimization and l1 greedy algorithms in reconstructing these medical images. In this paper the effectiveness of the generalized l1 greedy algorithm in finding random sparse signals from underdetermined linear systems is investigated. A series of numerical experiments demonstrate that the generalized l1 greedy algorithm is superior to the reweighted l1-minimization and l1 greedy algorithms in the successful recovery of randomly generated Gaussian sparse signals from data generated by Gaussian random matrices. In particular, the generalized l1 greedy algorithm performs extraordinarily well in recovering random sparse signals with nonzero small entries. The stability of the generalized l1 greedy algorithm with respect to its parameters and the impact of noise on the recovery of Gaussian sparse signals are also studied.

Keywords: Compressed Sensing; Gaussian Sparse Signals; l1-Minimization; Reweighted l1-Minimization; l1; Greedy Algorithm Generalized l1 Greedy Algorithm

Cite this paper: Arroyo, F. , Arroyo, E. , Li, X. , Zhu, J. and Zhu, J. (2013) Numerical Studies of the Generalized l₁Greedy Algorithm for Sparse Signals. Advances in Computed Tomography, 2, 132-139. doi: 10.4236/act.2013.24023.

References

[1]   E. Candes, J. Romberg and T. Tao, “Stable Signal Recovery from Incomplete and Inaccurate Information,” Communications on Pure and Applied Mathematics, Vol. 59, No. 8, 2005, pp. 1207-1233.
http://dx.doi.org/10.1002/cpa.20124

[2]   E. Candes, J. Romberg and T. Tao, “Robust Uncertainty Principles: Exact Signal Reconstruction from Highly Incomplete Frequency Information,” IEEE Transactions on Information Theory, Vol. 52, No. 2, 2006, pp. 489-509.
http://dx.doi.org/10.1109/TIT.2005.862083

[3]   E. Candes and T. Tao, “Near Optimal Signal Recovery from Random Projections: Universal Encoding Strategies?” IEEE Transactions on Information Theory, Vol. 52, No. 12, 2006, pp. 5406-5425.
http://dx.doi.org/10.1109/TIT.2006.885507

[4]   E. Candes and M. Wakin, “An Introduction to Compressive Sampling,” IEEE Signal Processing Magazine, Vol. 25, No. 2, 2008, pp. 21-30.
http://dx.doi.org/10.1109/MSP.2007.914731

[5]   D. Donoho, “Compressed Sensing,” IEEE Transactions on Information Theory, Vol. 52, No. 4, 2006, pp. 1289-1306. http://dx.doi.org/10.1109/TIT.2006.871582

[6]   S. Chen, D. Donoho and M. Saunders, “Atomic Decomposition by Basis Pursuit,” SIAM Journal on Scientific Computing, Vol. 20, No. 1, 1998, pp. 33-61.
http://dx.doi.org/10.1137/S1064827596304010

[7]   D. Donoho and B. F. Logan, “Signal Recovery and the Large Sieve,” SIAM Journal on Applied Mathematics, Vol. 52, No. 2, 1992, pp. 577-591.
http://dx.doi.org/10.1137/0152031

[8]   D. Donoho and P. B. Stark, “Uncertainty Principles and Signal Recovery,” SIAM Journal on Applied Mathematics, Vol. 49, No. 3, 1989, pp. 906-931.
http://dx.doi.org/10.1137/0149053

[9]   F. Santosa and W. Symes, “Linear Inversion of Band-Limited Reflection Seismograms,” SIAM Journal on Scientific and Statistical Computing, Vol. 7, No. 4, 1986, pp. 1307-1330. http://dx.doi.org/10.1137/0907087

[10]   R. Tibshirani, “Regression Shrinkage and Selection via the Lasso,” Journal of the Royal Statistical Society: Series B, Vol. 58, 1996, pp. 267-288.

[11]   E. J. Candes, M. B. Wakin and S. P. Boyed, “Enhancing Sparsity by Reweighted l1 Minimization,” Journal of Fourier Analysis Applications, Vol. 14, No. 5-6, 2008, pp. 877-905. http://dx.doi.org/10.1007/s00041-008-9045-x

[12]   I. Kozlov and A. Petukhov, “Sparse Solutions of Underdetermined Linear Systems,” Handbook of Geomathematics, Springer, New York, 2010, pp. 1243-1260.
http://dx.doi.org/10.1007/978-3-642-01546-5_42

[13]   S. Foucarts and M. J. Lai, “Sparsest Solutions of Underdetermined Linear Systems via lq-Minimization for 0 < q ≤ 1,” Applied and Computational Harmonic Analysis, Vol. 26, No. 3, 2009, pp. 395-407.
http://dx.doi.org/10.1016/j.acha.2008.09.001

[14]   M. J. Lai, “On Sparse Solutions of Underdetermined Linear Systems,” Journal of Concrete and Applicable Mathematics, Vol. 8, 2010, pp. 296-327.

[15]   A. Khajehnejad, W. Xu, S. Avestimher and B. Hassibi, “Improved Sparse Recovery Thresholds with Two-Step Reweighted l1-Minimization,” IEEE International Symposium on Information Theory Proceedings, 2010.

[16]   A. Khajehnejad, W. Xu, S. Avestimher and B. Hassibi, “Analyzing Weight l1-Minimization for Sparse Recovery with Nonuniform Sparse Models,” IEEE Transaction on Signal Processing, Vol. 59, No. 5, 2011, pp. 1985-2001.
http://dx.doi.org/10.1109/TSP.2011.2107904

[17]   D. Needell, ”Noisy Signal Recovery via Iterative Reweighted l1-Minimization,” Proceedings of 43rd Annual Asilomar Conference on Signals, Systems, and Computers, 2009, pp. 113-117.

[18]   Y. B. Zhao and D. Li, “Reweighted l1-Minimization for Sparse Solutions to Underdetermined Linear Systems,” SIAM Journal on Optimization, Vol. 22, No. 3, 2012, pp. 1065-1088. http://dx.doi.org/10.1137/110847445

[19]   A. Petukhov and I. Kozlov, ”Fast Implementation of l1 Greedy Algorithm,” Recent Advances in Harmonic Analysis Applications, Springer Proceedings in Mathematics & Statistics, Vol. 25, 2013, pp. 317-326.
http://dx.doi.org/10.1007/978-1-4614-4565-4_25

[20]   J. Zhu and X. Li, “A Generalized l1 Greedy Algorithm for Image Reconstruction in CT,” Applied Mathematics and Computation, Vol. 219, No. 10, 2013, pp. 5487-5494.
http://dx.doi.org/10.1016/j.amc.2012.11.052