الگوریتم جدید و مقاوم AMP برای ماتریس‌های غیر iid و گوسی مبتنی بر تئوری بیز در نمونه‌برداری فشرده
الموضوعات :فهیمه انصاری رام 1 , مرتضی خادمی 2 , عباس ابراهیمی مقدم 3 , هادی صدوقی یزدی 4
1 - دانشگاه فردوسی مشهد
2 - دانشگاه فردوسی مشهد
3 - دانشگاه فردوسی
4 - دانشگاه فردوسی مشهد
الکلمات المفتاحية: الگوریتم تقریب انتقال پیام (AMP)ماتریس‌های بدحالتماتریس‌های سطری متعامدماتریس‌های گوسی iidماتریس‌های مرتبه پاییننمونه‌برداری فشرده (CS),
ملخص المقالة :
: الگوریتم تقریب انتقال پیام (AMP) یک الگوریتم تکراری کم‌هزینه برای بازیابی سیگنال در نمونه‌برداری فشرده است. هنگامی که ماتریس نمونه‌بردار دارای مؤلفه‌هایی با توزیع گوسی مستقل و یکسان (iid) باشد، همگرایی AMP با تحلیل ریاضی اثبات می‌شود. اما برای سایر ماتریس‌های نمونه‌بردار به خصوص ماتریس‌های بدحالت، عملکرد این الگوریتم ضعیف شده و حتی ممکن است واگرا شود. این مشکل منجر به محدودیت استفاده از AMP در بعضی کاربردها از جمله تصویربرداری شده است. در این مقاله الگوریتمی جهت اصلاح AMP مبتنی بر تئوری بیز برای ماتریس‌های غیر iid ارائه شده است. نتایج شبیه‌سازی نشان می‌دهد که میزان مقاومت الگوریتم پیشنهادی برای ماتریس‌های غیر iid نسبت به روش‌های پیشین بیشتر می‌باشد. به عبارت دیگر این روش دارای دقت بیشتر در بازیابی است و با تکرار کمتری همگرا خواهد شد.
[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/
