Abstract
The classical Kaczmarz iteration and its randomized variants are popular tools for fast inversion of linear overdetermined systems. This method extends naturally to the setting of the phase retrieval problem via substituting at each iteration the phase of any measurement of the available approximate solution for the unknown phase of the measurement of the true solution. Despite the simplicity of the method, rigorous convergence guarantees that are available for the classical linear setting have not been established so far for the phase retrieval setting. In this short note, we provide a convergence result for the randomized Kaczmarz method for phase retrieval in $\mathbb{R}^d$. We show that with high probability a random measurement system of size $m \asymp d$ will be admissible for this method in the sense that convergence in the mean square sense is guaranteed with any prescribed probability. The convergence is exponential and comparable to the linear setting.
Introduction
Phase retrieval is a fundamental challenge in signal processing and imaging science, particularly in fields like X-ray crystallography and coherent diffractive imaging. The goal is to recover a signal $x$ from the magnitudes of its linear measurements: $| \langle x, \phi_i \rangle | = b_i$. In these settings, the "phase" (or the sign in the real-valued case) of the measurements is lost, making the recovery problem non-linear and non-convex.
The Kaczmarz method is a popular iterative solver for overdetermined linear systems ($Ax=b$). It operates by sequentially projecting the current estimate onto hyperplanes defined by the rows of the measurement matrix. While a "phase-adapting" version of this algorithm has been used heuristically for phase retrieval due to its computational efficiency and simplicity, it has historically lacked formal convergence proofs. Unlike the linear case, where every projection moves the estimate closer to the solution, a wrong sign estimation in phase retrieval can push the estimate further away. This paper provides the first rigorous theoretical framework to guarantee convergence for the randomized Kaczmarz method (RKM) in the phase retrieval context.
The Phase-Adapting Randomized Kaczmarz Algorithm
The authors analyze a specific iterative process designed to handle the missing phase information. At each iteration $k$, the algorithm performs the following steps:
- Random Selection: A measurement vector $\phi_t$ is selected at random from the available set.
- Phase Estimation: The algorithm uses the sign of the current estimate's projection, $\sigma(x_k \cdot \phi_t)$, as a proxy for the unknown true sign of the measurement.
- Update: A standard Kaczmarz update is performed using this estimated sign: $$x_{k+1} = x_k + (\sigma(x_k \cdot \phi_t)b_t - \langle x_k, \phi_t \rangle) \phi_t$$
This approach is computationally lean but introduces stochasticity and the risk of divergence if the phase proxy is incorrect too frequently.
Theoretical Framework: Admissibility and Drift
To prove convergence, the authors introduce the concept of $\delta$-admissibility. A measurement system is considered $\delta$-admissible if it satisfies four deterministic properties related to how the vectors tile the unit sphere and how their moments behave. The paper demonstrates that a random measurement system—where vectors are drawn uniformly from the sphere $\mathbb{S}^{d-1}$—satisfies these properties with high probability when the number of measurements $m$ scales linearly with the dimension $d$ ($m \ge Cd$).
Because the algorithm is non-linear, the error sequence is not monotonic. To address this, the authors employ drift analysis and hitting-time bounds. This mathematical approach treats the error sequence as a random walk with a strong bias toward the solution. They prove that if the algorithm is initialized within a specific "basin of attraction," it is highly likely to remain within a "stability event" where the expected error shrinks at each step.
Key Results
1. Optimal Sample Complexity
The study establishes that rigorous convergence is guaranteed with $m \ge Cd$ measurements. This $O(d)$ scaling is the information-theoretic optimal for phase retrieval, matching the requirements of more complex batch algorithms.
2. Exponential Convergence
Under the condition that the algorithm remains within the stability event, the expected squared error decays exponentially. The rate is comparable to the linear Kaczmarz setting: $$\mathbb{E}[\text{dist}^2(x, x_k)] \le e^{-k/4d} \text{dist}^2(x, x_0)$$
3. High Probability Stability
The analysis shows that for any $\epsilon > 0$, if the initial relative error is sufficiently small (e.g., via spectral initialization), the algorithm stays on track with probability at least $1 - \epsilon^2$. This ensures that the heuristic success of the algorithm is backed by a high-probability theoretical guarantee.
Limitations and Future Directions
While this work provides a significant theoretical foundation, several areas remain for further exploration:
- Complex Domain: The current proof is restricted to the real-valued case ($\mathbb{R}^d$). Extending the geometric analysis of tessellation properties to the complex domain ($\mathbb{C}^d$) is a necessary next step for broader application in optics.
- Initialization: The convergence guarantee depends on a "good" starting point $x_0$. While standard methods like spectral initialization can provide this, the paper focuses on the local convergence from that point rather than the global initialization process.
- Tightening Bounds: The authors suggest that the probability lower bounds for the stability event are likely conservative and could be refined in future research to reflect even more robust performance.
Conclusion
This paper bridges the gap between the practical utility of the randomized Kaczmarz method and its mathematical theory in the context of phase retrieval. By proving that the algorithm achieves exponential convergence with optimal sample complexity, the authors provide a rigorous justification for using Kaczmarz-style updates in non-linear signal recovery tasks.
Summary updated