2014/02/13 by Sundeep Rangan, Philip Schniter, Rangan, Sundeep +5 · 3 citations
Computer Science · Engineering · Mathematics · #FOS: Computer and information sciences #Information Theory (cs.IT) #Random Matrices and Applications #Sparse and Compressive Sensing Techniques #Stochastic Gradient Optimization Techniques
paper · pdf · doi:10.48550/arxiv.1402.3210
openalex publication_date 2014/02/13 · openalex created_date 2022/10/03 · openalex updated_date 2026/07/28
Approximate message passing (AMP) methods and their variants have attracted\nconsiderable recent attention for the problem of estimating a random vector\n\x observed through a linear transform \A. In the case of\nlarge i.i.d. zero-mean Gaussian \A, the methods exhibit fast\nconvergence with precise analytic characterizations on the algorithm behavior.\nHowever, the convergence of AMP under general transforms \A is not\nfully understood. In this paper, we provide sufficient conditions for the\nconvergence of a damped version of the generalized AMP (GAMP) algorithm in the\ncase of quadratic cost functions (i.e., Gaussian likelihood and prior). It is\nshown that, with sufficient damping, the algorithm is guaranteed to converge,\nalthough the amount of damping grows with peak-to-average ratio of the squared\nsingular values of the transforms \A. This result explains the good\nperformance of AMP on i.i.d. Gaussian transforms \A, but also their\ndifficulties with ill-conditioned or non-zero-mean transforms \A. A\nrelated sufficient condition is then derived for the local stability of the\ndamped GAMP method under general cost functions, assuming certain strict\nconvexity conditions.\n