Solving systems of phaseless equations via Riemannian optimization with optimal sampling complexity
This work addresses the problem of phase retrieval, providing algorithms with optimal sampling complexity and theoretical guarantees for nonconvex optimization.
The paper presents a Riemannian gradient descent algorithm and its truncated variant for solving phaseless equations, achieving successful recovery when the number of equations is proportional to the number of unknowns. Empirical evaluations show the algorithms are competitive with state-of-the-art first-order nonconvex approaches.
A Riemannian gradient descent algorithm and a truncated variant are presented to solve systems of phaseless equations $|Ax|^2=y$. The algorithms are developed by exploiting the inherent low rank structure of the problem based on the embedded manifold of rank-$1$ positive semidefinite matrices. Theoretical recovery guarantee has been established for the truncated variant, showing that the algorithm is able to achieve successful recovery when the number of equations is proportional to the number of unknowns. Two key ingredients in the analysis are the restricted well conditioned property and the restricted weak correlation property of the associated truncated linear operator. Empirical evaluations show that our algorithms are competitive with other state-of-the-art first order nonconvex approaches with provable guarantees.