Approximate Message Passing for Amplitude Based Optimization

Abstract

We consider an ${\ell }_2$-regularized non-convex optimization problem for recovering signals from their noisy phaseless observations. We design and study the performance of a message passing algorithm that aims to solve this optimization problem. We consider the asymptotic setting $m,n\to \infty$, $m/n\to \delta$ and obtain sharp performance bounds, where $m$ is the number of measurements and $n$ is the signal dimension. We show that for complex signals the algorithm can perform accurate recovery with only $m=\left(\frac{64}{{\pi }^2}-4\right)n\approx 2.5n$ measurements. Also, we provide sharp analysis on the sensitivity of the algorithm to noise. We highlight the following facts about our message passing algorithm: (i) Adding ${\ell }_2$ regularization to the non-convex loss function can be beneficial even in the noiseless setting; (ii) spectral initialization has marginal impact on the performance of the algorithm.

arXiv commentaccepted by ICML; short version of arXiv:1801.01170 with more simulations and other discussions

References in corpus (9)

• Implicit Regularization in Nonconvex Statistical Estimation: Gradient Descent Converges Linearly for Phase Retrieval, Matrix Completion, and Blind Deconvolution
• Solving Systems of Random Quadratic Equations via Truncated Amplitude Flow
• Phase Retrieval Meets Statistical Learning Theory: A Flexible Convex Relaxation
• Solving (most) of a set of quadratic equalities: Composite optimization for robust phase retrieval
• Convergence of the randomized Kaczmarz method for phase retrieval
• Which bridge estimator is optimal for variable selection?
• Optimization-based AMP for Phase Retrieval: The Impact of Initialization and ${\ell }_2$-regularization
• Coordinate Descent Algorithms for Phase Retrieval
• A Local Analysis of Block Coordinate Descent for Gaussian Phase Retrieval

Cited by in corpus (3)

• Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview
• Generalized Approximate Survey Propagation for High-Dimensional Estimation
• Scalable Incremental Nonconvex Optimization Approach for Phase Retrieval