A New and Robust AMP Algorithm for Non IID Matrices Based on Bayesian Theory in Compressed Sensing
Subject Areas : electrical and computer engineeringF. Ansari Ram 1 , M. Khademi 2 , Abbas Ebrahimi moghadam 3 , H. Sadoghi Yazdi 4
1 - Ferdosi University
2 - Ferdowsi University of Mashhad
3 - Ferdosi University
4 - Ferdosi University
Abstract :
AMP is a low-cost iterative algorithm for recovering signal in compressed sensing. When the sampling matrix has IID zero-mean Gaussian elements, the convergence of AMP is analytically guaranteed. But for other sampling matrices, especially ill-conditioned matrices, the recovery performance of AMP degrades and even may be diverged. This problem limits the use of AMP in some applications such as imaging. In this paper, a method is proposed for modifying the AMP algorithm based on Bayesian theory for non-IID matrices. Simulation results show better robustness properties of the proposed algorithm for non-IID matrices in comparison with previous works. In other words, the proposed method has more precision in recovery, and converges with less iterations.
[1] E. Candes, J. Romberg, and T. Tao, "Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information," IEEE Trans. on Inform.Theory, vol. 52, no. 2, pp. 489-509, Feb. 2006.
[2] D. L. Donoho, "Compressed sensing," IEEE Trans. on Inform. Theory, vol. 52, no. 4, pp. 1289-1306, Apr. 2006.
[3] S. Qaisar, R. M. Bilal, W. Iqbal, M. Naureen, and S. Lee, "Compressive sensing: from theory to applications, a survey," J. of Communications and Networks, vol. 15, no. 5, pp. 443-456, Oct. 2013.
[4] A. Maleki, Approximate Message Passing Algorithms for Compressed Sensing, PhD Thesis, Stanford University, 2011.
[5] S. Chen, D. Donoho, and M. Saunders, "Atomic decomposition by basis pursuit," SIAM Rev., vol. 43, no. 1, pp. 129-159, Mar. 2001.
[6] W. Lu and N. Vaswani, "Modified basis pursuit denoising (modified BPDN) for noisy compressive sensing with partially known support," in Proc. IEEE Int. Conf. on Acoustics, Speech and Signal Processing, ICASSP'10, pp. 3926-3929, Dallas, TX, USA, 14-19 Mar. 2010.
[7] B. Efron, T. Hastie, I. Johnstone, and R. Tibshirani, "Least angle regression," Annals of Statistics, vol. 32, no. 2, pp. 407-499, Apr. 2004.
[8] S. Chen, S. A. Billing, and W. Lue, "Orthogonal least squares methods andtheir application to nonlinear system identification," International J. of Control, vol. 50, no. 5, pp. 1873-1896, 1989.
[9] Y. C. Pati, R. Rezaiifar, and P. S. Krishnaprasad, "Orthogonal matching pursuit: recursive function approximation with applications to wavelet decomposition," in Proc. 27th Asilomar Conf. on Signals, Systems and Computers, vol. 1, pp. 40-44, Pacific Grove, CA, USA, 1-3 Nov. 1993.
[10] D. Needell and J. A. Tropp, "CoSaMP: iterative signal recovery from incomplete and inaccurate samples," Applied and Computational Harmonic Analysis, vol. 26, no. 3, pp. 301-321, May 2008.
[11] S. Ji, Y. Xue, and L. Carin, "Bayesian compressive sensing," IEEE Trans. on Signal Processing, vol. 56, no. 6, pp. 2346-2356, Jun. 2008.
[12] H. Zayyani, M. Babaie-Zadeh, and C. Jutten, "An iterative Bayesian algorithm for sparse component analysis in presence of noise," IEEE Trans. on Signal Processing, vol. 57, no. 11, pp. 4378-4390, Nov. 2009.
[13] S. Derin Babacan, R. Molina, and A. K. Katsaggelos, "Bayesian compressive sensing using Laplace priors," IEEE Trans. on Image Processing, vol. 19, no. 1, pp. 53-63, Jan. 2010.
[14] D. Baron, S. Sarvotham, and R. G. Baraniuk, "Bayesian compressive sensing via belief propagation," IEEE Trans. on Signal Processing, vol. 58, no. 1, pp. 269-280, Jan. 2010.
[15] R. Giri and B. D. Rao, Type I and Type II Bayesian Methods for Sparse Signal Recovery Using Scale Mixtures, arXiv preprint arXiv:1507.05087, 2015.
[16] E. C. Marques, N. Maciel, L. A. B. Naviner, and H. Caie, "A review of sparse recovery algorithms," IEEE Access, vol. 7, pp. 1300-1322, Dec. 2018.
[17] T. Blumensath and M. E. Davies, "Iterative hard thresholding for compressed sensing," Applied and Computational Harmonic Analysis, vol. 27, no. 3, pp. 265-274, Nov. 2009.
[18] A. Chambolle, R. A. DeVore, N. Lee, and B. J. Lucier, "Nonlinear wavelet image processing: variational problems, compression, and noise removal through wavelet shrinkage," IEEE Trans. Image Process., vol. 7, no. 3, pp. 319-335, Mar. 1998.
[19] D. L. Donoho, A. Maleki, and A. Montanari, "Message passing algorithms for compressed sensing," in Proc. Nat. Acad. Sci., vol. 106, pp. 18914-18919, Nov. 2009.
[20] M. Bayati and A. Montanari, "The dynamics of message passing on dense graphs, with applications to compressed sensing," IEEE Trans. Inf. Theory, vol. 57, no. 2, pp. 764-785, Feb. 2011.
[21] J. Vila, P. Schniter, S. Rangan, F. Krzakala, and L. Zdeborov'a, "Adaptive damping and mean removal for the generalized approximate message passing algorithm," in Proc. IEEE Int. Conf. Acoust., Speech, Signal Process., ICASSP'15, pp. 2021-2025, Brisbane, QLD, Australia, 19-24 Apr. 2015.
[22] S. Rangan, P. Schniter, and A. Fletcher, "On the convergence of approximate message passing with arbitrary matrices," in Proc. IEEE Int. Symp. on Information Theory, ISIT'14, pp. 236-240, Honolulu, HI, USA, 29 Jun.-4 Jul. 2014.
[23] F. Caltagirone, L. Zdeborov'a, and F. Krzakala, "On convergence of approximate message passing," in Proc. IEEE Int. Symp. on Information Theory, ISIT'14, pp. 1812-1816, Honolulu, HI, USA, 29 Jun.-4 Jul. 2014.
[24] A. Manoel, F. Krzakala, E. W. Tramel, and L. Zdeborov'a, "Swept approximate message passing for sparse estimation," in Proc 32nd Int. Conf. on Machine Learning, ICML'15, vol. 37, pp. 1123-1132, Jul. 2015.
[25] S. Rangan, A. K. Fletcher, P. Schniter, and U. S. Kamilov, "Inference for generalized linear models via alternating directions and Bethe free energy minimization," in Proc. IEEE Int. Symp. on Information Theory, ISIT'15, pp. 1640-1644, Hong Kong, China, 14-19 Jun. 2015.
[26] J. Ma and L. Ping, "Orthogonal AMP," IEEE Access, vol. 5, pp. 2020-2033, Jan. 2017.
[27] S. Rangan, P. Schniter, and A. K. Fletcher, "Vector approximate message passing," IEEE Trans. on Information Theory, vol. 65, no. 10, pp. 6664-6684, May 2019.
[28] A. Maleki and D. L. Donoho, "Optimally tuned iterative thresholding algorithm for compressed sensing," IEEE J. Select. Top. Signal Processing, vol. 4, no. 2, pp. 330-341, Apr. 2010.
[29] I. Daubechies, M. Defrise, and C. D. Mol, "An iterative thresholding algorithm for linear inverse problems with a sparsity constraint," Commun. Pure Appl. Math., vol. 57, no. 11, pp. 1413-1457, Nov. 2004.
[30] A. Beck and M. Teboulle, "A fast iterative shrinkage-thresholding algorithm for linear inverse problems," SIAM J. Imag. Sci., vol. 2, no. 1, pp. 183-202, Mar. 2009.
[31] A. Montanari, Graphical Models Concepts in Compressed Sensing, in Compressed Sensing: Theory and Applications, (Y. C. Eldar and G. Kutyniok, Eds.), Cambridge Univ. Press, 2012.
[32] D. L. Donoho, A. Maleki, and A. Montanari, "Noise sensitivity phase transition," IEEE Trans. Inform. Theory, vol. 57, no. 10, pp. 6920-6941, Oct. 2011.
[33] A. Mousavi, A. Maleki, and R. G. Baraniuk, "Parameterless optimal approximate message passing," arXiv preprint, 2013.
[34] H. A. van der Vorst, Iterative Krylov Methods for Large Linear Systems, vol. 13, Cambridge, U.K.: Cambridge Univ. Press, 2003.
[35] Alyson K. Fletcher and Philip Schniter, "Learning and Free Energies for Vector Approximate Message Passing," arXive preprint 2016.
[36] S. Akhlaghi, N. Zhou, and Z. Huang, "Adaptive Adjustment of Noise Covariance in Kalman Filter for Dynamic State Estimation," ArXiv preprints, Feb. 2017.
[37] "Generalized approximate message passing," SourceForge.net project GAMPmatlab, Available on-line at http://gampmatlab.sourceforge.net/
