TL;DR
This paper investigates the effectiveness of the alternating projections algorithm for solving the phase retrieval problem, a fundamental challenge in signal processing and imaging. The authors demonstrate that this classical, non-convex method can achieve high-probability exact recovery of an unknown signal, even with a linear number of measurements (m = O(n)), provided a careful initialization is used. Furthermore, they show that in a regime with quadratically many measurements (m = O(n²)), the need for a special initialization disappears, making the algorithm robust to arbitrary starting points.
What Problem Does This Paper Address?
Phase retrieval is the problem of reconstructing a signal (represented as a vector $x_0$) from measurements that only capture its magnitude, not its phase. Mathematically, we are given $m$ measurements $b_k = | \langle a_k, x_0 \rangle |$ for $k=1, \dots, m$, where $a_k$ are known sensing vectors and $x_0$ is the unknown signal. This problem arises in various fields, including optics, crystallography, and audio signal processing. The core challenge is that the phase information is lost, making direct reconstruction difficult. While convex optimization methods can provide theoretical guarantees, they are computationally expensive for high-dimensional signals. This paper focuses on analyzing a popular non-convex iterative method, alternating projections (AP), which is computationally efficient but known to sometimes get stuck in "stagnation points," preventing it from reaching the true solution. The authors aim to understand the conditions under which AP can reliably recover the signal, particularly in terms of the number of measurements ($m$) relative to the signal dimension ($n$).
Methods
The paper analyzes the Gerchberg-Saxton algorithm, a classic iterative method for phase retrieval that employs alternating projections. The core idea is to iteratively project an estimate of the signal onto two sets: one that enforces the measured magnitudes and another that enforces the signal's properties (e.g., being a vector in $\mathbb{C}^n$). The authors' main contribution is to provide theoretical guarantees for the convergence of this algorithm.
They analyze two main scenarios:
- With careful initialization: They prove that if the number of measurements $m$ is linear in the signal dimension $n$ (i.e., $m = O(n)$), alternating projections can achieve exact recovery with high probability, provided a specific initialization procedure is used. This initialization aims to find a starting point close to the true solution.
- Without special initialization: They show that when the number of measurements $m$ is quadratic in $n$ (i.e., $m = O(n^2)$), the algorithm converges to the correct solution with high probability, even from an arbitrary initial guess (unless it's "almost orthogonal" to the true solution). This implies that in this regime, stagnation points either disappear or have negligible attraction basins.
The proofs rely on sophisticated tools from random matrix theory, concentration inequalities, and analysis of non-convex optimization operators.
Datasets
Not discussed in the paper. The paper focuses on theoretical analysis and numerical validation using synthetic data generated according to the problem's assumptions (random Gaussian sensing vectors).
Key Insights and Ideas
- Alternating Projections is Surprisingly Robust: The paper demonstrates that a classical, seemingly simple algorithm like alternating projections can be theoretically guaranteed to work for phase retrieval under specific conditions, even in the challenging low-measurement regime ($m=O(n)$).
- Initialization Matters (Sometimes): The need for a "good" initialization is crucial when measurements are sparse ($m=O(n)$). This highlights the importance of finding good starting points for non-convex optimization.
- Measurement Density is Key: The transition from needing a special initialization ($m=O(n)$) to not needing one ($m=O(n^2)$) underscores the critical role of the number of measurements in overcoming the inherent non-convexity of the phase retrieval problem. A quadratic increase in measurements dramatically simplifies the problem's landscape.
- Stagnation Points are Manageable: The analysis of stagnation points reveals that they are not an insurmountable obstacle. Either they can be avoided with a good start, or they become irrelevant when enough measurements are available.
Key Results
- $m=O(n)$ Regime: With a carefully chosen initialization, alternating projections achieve exact recovery with high probability when $m \ge Cn$ for some constant $C$. The convergence rate is linear.
- $m=O(n^2)$ Regime: Alternating projections succeed with high probability from any initial point (not almost orthogonal to the true solution) when $m \ge Mn^2$ for some constant $M$. This implies the absence of problematic stagnation points.
- Numerical Validation: The paper includes numerical experiments that support these theoretical findings, showing high success probabilities for alternating projections in the analyzed regimes.
Limitations and Future Work
- Initialization Dependence: The theoretical guarantees for the $m=O(n)$ regime rely on a specific initialization procedure. While this procedure is presented, its practical implementation and computational cost are not the primary focus.
- "Almost Orthogonal" Initializations: In the $m=O(n^2)$ regime, the guarantee of convergence from any initial point has a caveat: initializations that are "almost orthogonal" to the true solution might still pose issues. The paper acknowledges that analyzing the size of attraction basins for stagnation points is difficult and leaves this as future work.
- Conjecture on Random Initialization: The authors conjecture that even in the $m=O(n)$ regime, a random isotropic initialization might suffice for high-probability success, despite the theoretical presence of stagnation points. This is supported by numerical evidence but not formally proven.
- General Sensing Vectors: While the analysis focuses on random Gaussian sensing vectors, extending these results to more structured or non-random sensing vectors (which are common in applications) would be valuable.
Summary updated