Solving Complex Quadratic Systems with Full-Rank Random Matrices

Abstract

We tackle the problem of recovering a complex signal $\mathbf{x}\in {\mathbb{C}}^n$ from quadratic measurements of the form $y_i={\mathbf{x}}^{\ast }{\mathbf{A}}_i\mathbf{x}$, where ${\mathbf{A}}_i$ is a full-rank, complex random measurement matrix whose entries are generated from a rotation-invariant sub-Gaussian distribution. We formulate it as the minimization of a nonconvex loss. This problem is related to the well understood phase retrieval problem where the measurement matrix is a rank-1 positive semidefinite matrix. Here we study the general full-rank case which models a number of key applications such as molecular geometry recovery from distance distributions and compound measurements in phaseless diffractive imaging. Most prior works either address the rank-1 case or focus on real measurements. The several papers that address the full-rank complex case adopt the computationally-demanding semidefinite relaxation approach. In this paper we prove that the general class of problems with rotation-invariant sub-Gaussian measurement models can be efficiently solved with high probability via the standard framework comprising a spectral initialization followed by iterative Wirtinger flow updates on a nonconvex loss. Numerical experiments on simulated data corroborate our theoretical analysis.

arXiv commentThis updated version of the manuscript addresses several important issues in the initial arXiv submission

References in corpus (22)

• Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization
• Phase Retrieval via Wirtinger Flow: Theory and Algorithms
• Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview
• Global Optimality of Local Search for Low Rank Matrix Recovery
• An algebraic characterization of injectivity in phase retrieval
• No Spurious Local Minima in Nonconvex Low Rank Problems: A Unified Geometric Analysis
• Fast low-rank estimation by projected gradient descent: General statistical and algorithmic guarantees
• Nonconvex phase synchronization
• Low-rank Solutions of Linear Matrix Equations via Procrustes Flow
• Gradient Descent with Random Initialization: Fast Global Convergence for Nonconvex Phase Retrieval
• The Non-convex Geometry of Low-rank Matrix Optimization
• Phase Retrieval: An Overview of Recent Developments
• Sketchy Decisions: Convex Low-Rank Matrix Optimization with Optimal Storage
• Phase Retrieval for Sparse Signals: Uniqueness Conditions
• A Convergent Gradient Descent Algorithm for Rank Minimization and Semidefinite Programming from Random Linear Measurements
• Power System State Estimation via Feasible Point Pursuit: Algorithms and Cramer-Rao Bound
• Reconstructing Point Sets from Distance Distributions
• Phase Retrieval Without Small-Ball Probability Assumptions
• Coordinate Descent Algorithms for Phase Retrieval
• Don't take it lightly: Phasing optical random projections with unknown operators
• On phase retrieval via matrix completion and the estimation of low rank PSD matrices
• Phase retrieval for sub-Gaussian measurements

Cited by in corpus (4)

• Reconstructing Point Sets from Distance Distributions
• A continuous constraint satisfaction problem for the rigidity transition in confluent tissues
• Total Least Squares Phase Retrieval
• Spectral Algorithm for Low-rank Multitask Regression