Optimization-based AMP for Phase Retrieval: The Impact of Initialization and ${\ell }_2$-regularization

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. (ii) Spectral initialization has marginal impact on the performance of the algorithm. The sharp analyses in this paper, not only enable us to compare the performance of our method with other phase recovery schemes, but also shed light on designing better iterative algorithms for other non-convex optimization problems.

References in corpus (10)

• Message Passing Algorithms for Compressed Sensing
• Implicit Regularization in Nonconvex Statistical Estimation: Gradient Descent Converges Linearly for Phase Retrieval, Matrix Completion, and Blind Deconvolution
• Phase Retrieval Meets Statistical Learning Theory: A Flexible Convex Relaxation
• Solving Systems of Random Quadratic Equations via Truncated Amplitude Flow
• Solving (most) of a set of quadratic equalities: Composite optimization for robust phase retrieval
• Convergence of the randomized Kaczmarz method for phase retrieval
• Precise Error Analysis of Regularized M-estimators in High-dimensions
• Convolutional Phase Retrieval via Gradient Descent
• Fourth Moment Theorems for complex Gaussian approximation
• Coordinate Descent Algorithms for Phase Retrieval

Cited by in corpus (7)

• Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview
• Optimal Spectral Initialization for Signal Recovery with Applications to Phase Retrieval
• The distribution of the Lasso: Uniform control over sparse balls and adaptive parameter tuning
• Accelerated Wirtinger Flow: A fast algorithm for ptychography
• Approximate Message Passing for Amplitude Based Optimization
• Consistent Risk Estimation in Moderately High-Dimensional Linear Regression
• Spectral Method for Phase Retrieval: an Expectation Propagation Perspective