Solving systems of phaseless equations via Riemannian optimization with optimal sampling complexity

Abstract

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.

References in corpus (7)

• How to Escape Saddle Points Efficiently
• Implicit Regularization in Nonconvex Statistical Estimation: Gradient Descent Converges Linearly for Phase Retrieval, Matrix Completion, and Blind Deconvolution
• No Spurious Local Minima in Nonconvex Low Rank Problems: A Unified Geometric Analysis
• Phase Retrieval Meets Statistical Learning Theory: A Flexible Convex Relaxation
• Accelerated Methods for Non-Convex Optimization
• An Elementary Proof of Convex Phase Retrieval in the Natural Parameter Space via the Linear Program PhaseMax
• Convergence of the randomized Kaczmarz method for phase retrieval

Cited by in corpus (8)

• Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview
• Fast Global Convergence for Low-rank Matrix Recovery via Riemannian Gradient Descent with Random Initialization
• Provable Near-Optimal Low-Multilinear-Rank Tensor Recovery
• Towards the optimal construction of a loss function without spurious local minima for solving quadratic equations
• Bridging Convex and Nonconvex Optimization in Robust PCA: Noise, Outliers, and Missing Data
• Analysis of Asymptotic Escape of Strict Saddle Sets in Manifold Optimization
• Nonconvex Factorization and Manifold Formulations are Almost Equivalent in Low-rank Matrix Optimization
• A stochastic alternating minimizing method for sparse phase retrieval