A Deterministic Theory for Exact Non-Convex Phase Retrieval
arXiv:2001.02855 · doi:10.1109/TSP.2020.3007967
Abstract
In this paper, we analyze the non-convex framework of Wirtinger Flow (WF) for phase retrieval and identify a novel sufficient condition for universal exact recovery through the lens of low rank matrix recovery theory. Via a perspective in the lifted domain, we show that the convergence of the WF iterates to a true solution is attained geometrically under a single condition on the lifted forward model. As a result, a deterministic relationship between the accuracy of spectral initialization and the validity of {the regularity condition} is derived. In particular, we determine that a certain concentration property on the spectral matrix must hold uniformly with a sufficiently tight constant. This culminates into a sufficient condition that is equivalent to a restricted isometry-type property over rank-1, positive semi-definite matrices, and amounts to a less stringent requirement on the lifted forward model than those of prominent low-rank-matrix-recovery methods in the literature. We characterize the performance limits of our framework in terms of the tightness of the concentration property via novel bounds on the convergence rate and on the signal-to-noise ratio such that the theoretical guarantees are valid using the spectral initialization at the proper sample complexity.
arXiv commentIn Revision for IEEE Transactions on Signal Processing
References in corpus (16)
- 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
- Implicit Regularization in Nonconvex Statistical Estimation: Gradient Descent Converges Linearly for Phase Retrieval, Matrix Completion, and Blind Deconvolution
- A Geometric Analysis of Phase Retrieval
- Low-rank Solutions of Linear Matrix Equations via Procrustes Flow
- Global Optimality in Low-rank Matrix Optimization
- Necessary and Sufficient Conditions for Success of the Nuclear Norm Heuristic for Rank Minimization
- Optimal Spectral Initialization for Signal Recovery with Applications to Phase Retrieval
- Phaseless Rcovery using Gauss-Newton Method
- A Convergent Gradient Descent Algorithm for Rank Minimization and Semidefinite Programming from Random Linear Measurements
- Dropping Convexity for Faster Semi-definite Optimization
- Exact Imaging of Extended Targets Using Multistatic Interferometric Measurements
- A Generalization of Wirtinger Flow for Exact Interferometric Inversion
- Robust Wirtinger Flow for Phase Retrieval with Arbitrary Corruption