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 \rightarrow \infty$, $m/n \rightarrow \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.
Introduction
Phase retrieval is a classic inverse problem central to fields such as X-ray crystallography, diffraction imaging, and astronomical observation. The core challenge involves recovering a signal $x \in \mathbb{C}^n$ from the magnitudes of its linear measurements $|Ax| = y$, where the phase information is lost. Because the relationship between the measurements and the signal is non-linear, the resulting optimization landscape is non-convex and notoriously difficult to navigate.
While various algorithms like Wirtinger Flow and PhaseLift have been developed, their theoretical guarantees often rely on "loose" bounds. These typically suggest recovery is possible with $Cn$ measurements, but the constant $C$ is often unspecified or overly conservative. This research introduces a new Approximate Message Passing (AMP) algorithm, termed AMP.A, which provides "sharp" theoretical thresholds and exact error rates, clarifying the precise requirements for successful signal recovery.
The AMP.A Framework
The authors propose an amplitude-based optimization approach enhanced by two key features: $\ell_2$-regularization and an adaptive continuation strategy. The optimization objective includes a penalty term $\frac{\mu}{2}\|x\|_2^2$ added to the standard loss function.
Adaptive Continuation
Rather than maintaining a static regularization parameter, AMP.A adaptively updates $\mu$ at each iteration. This acts as a continuation strategy that smooths the non-convex landscape during the early stages of the algorithm, helping it avoid local minima. As the algorithm converges toward the signal, the regularization is adjusted to sharpen the focus on the true solution.
State Evolution Analysis
The performance of AMP.A is analyzed in the high-dimensional limit where $m, n \to \infty$ while the ratio $\delta = m/n$ remains constant. This allows for the use of "State Evolution" (SE) equations, which predict the algorithm's Mean Squared Error (MSE) at every iteration with high precision. This theoretical framework enables the identification of exact phase transitions—the points at which the algorithm shifts from failure to successful recovery.
Key Insights and Results
1. Sharp Recovery Thresholds
The study identifies precise measurement ratios required for perfect recovery in the noiseless setting:
- Complex-valued signals: Accurate recovery is achieved when $\delta > \frac{64}{\pi^2} - 4 \approx 2.5$.
- Real-valued signals: The threshold is lower, requiring $\delta > \frac{\pi^2}{4} - 1 \approx 1.5$.
2. The Role of Initialization
A significant finding of this work is the reassessment of "spectral initialization." While many existing phase retrieval methods rely heavily on sophisticated initialization to succeed, this analysis shows that for AMP.A, spectral initialization has only a marginal impact on the final recovery quality. As long as the initial guess is not perfectly orthogonal to the true signal, the algorithm's dynamics eventually lead it to the correct solution, provided the measurement ratio $\delta$ is above the threshold.
3. Noise Sensitivity
The paper provides an exact formula for noise sensitivity in the high Signal-to-Noise Ratio (SNR) regime. For complex signals, the sensitivity is characterized as $\frac{4}{1 - 2/\delta}$. This allows practitioners to calculate exactly how many additional measurements are required to achieve a specific desired error tolerance in the presence of noise.
Conclusion
By combining $\ell_2$-regularization with the AMP framework, this research provides a more transparent and efficient path to solving the phase retrieval problem. The sharp analysis not only confirms that complex signals can be recovered with roughly 2.5x measurements but also demonstrates that the structural design of the algorithm (specifically the regularization schedule) is more critical than the specific initialization used. Future work may focus on closing the gap between the 1.5 threshold and the information-theoretic limit of 1.0 for real-valued signals, potentially through even more sophisticated continuation strategies.
Summary updated