Convergence of the randomized Kaczmarz method for phase retrieval

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.

arXiv comment13 pages, a mistake corrected, an appendix added

References in corpus (2)

• Paved with Good Intentions: Analysis of a Randomized Block Kaczmarz Method
• Reshaped Wirtinger Flow and Incremental Algorithm for Solving Quadratic System of Equations

Cited by in corpus (11)

• Accelerated Wirtinger Flow: A fast algorithm for ptychography
• Online stochastic gradient descent on non-convex losses from high-dimensional inference
• Online Stochastic Gradient Descent with Arbitrary Initialization Solves Non-smooth, Non-convex Phase Retrieval
• Solving systems of phaseless equations via Riemannian optimization with optimal sampling complexity
• Approximate Message Passing for Amplitude Based Optimization
• Optimization-based AMP for Phase Retrieval: The Impact of Initialization and ${\ell }_2$-regularization
• Towards the optimal construction of a loss function without spurious local minima for solving quadratic equations
• Linear Convergence of An Iterative Phase Retrieval Algorithm with Data Reuse
• A stochastic alternating minimizing method for sparse phase retrieval
• The Dual Kaczmarz Algorithm
• Regularized Kaczmarz Algorithms for Tensor Recovery