Solving Large-scale Systems of Random Quadratic Equations via Stochastic Truncated Amplitude Flow
arXiv:1610.09540 · doi:10.1109/TSP.2017.2652392
Abstract
A novel approach termed \emph{stochastic truncated amplitude flow} (STAF) is developed to reconstruct an unknown -dimensional real-/complex-valued signal from `phaseless' quadratic equations of the form . This problem, also known as phase retrieval from magnitude-only information, is \emph{NP-hard} in general. Adopting an amplitude-based nonconvex formulation, STAF leads to an iterative solver comprising two stages: s1) Orthogonality-promoting initialization through a stochastic variance reduced gradient algorithm; and, s2) A series of iterative refinements of the initialization using stochastic truncated gradient iterations. Both stages involve a single equation per iteration, thus rendering STAF a simple, scalable, and fast approach amenable to large-scale implementations that is useful when is large. When are independent Gaussian, STAF provably recovers exactly any exponentially fast based on order of quadratic equations. STAF is also robust in the presence of additive noise of bounded support. Simulated tests involving real Gaussian vectors demonstrate that STAF empirically reconstructs any exactly from about magnitude-only measurements, outperforming state-of-the-art approaches and narrowing the gap from the information-theoretic number of equations . Extensive experiments using synthetic data and real images corroborate markedly improved performance of STAF over existing alternatives.
arXiv comment21 pages, 12 figures
References in corpus (24)
- Phase Retrieval via Wirtinger Flow: Theory and Algorithms
- Identifying and attacking the saddle point problem in high-dimensional non-convex optimization
- Guaranteed Matrix Completion via Non-convex Factorization
- GESPAR: Efficient Phase Retrieval of Sparse Signals
- An algebraic characterization of injectivity in phase retrieval
- Escaping From Saddle Points --- Online Stochastic Gradient for Tensor Decomposition
- Low-rank Solutions of Linear Matrix Equations via Procrustes Flow
- Phase Retrieval from 1D Fourier Measurements: Convexity, Uniqueness, and Algorithms
- PRIME: Phase Retrieval via Majorization-Minimization
- Phaseless Rcovery using Gauss-Newton Method
- Low Rank Phase Retrieval
- Phase Retrieval: An Overview of Recent Developments
- Phase Retrieval for Sparse Signals: Uniqueness Conditions
- Phase Recovery, MaxCut and Complex Semidefinite Programming
- Solving Systems of Random Quadratic Equations via Truncated Amplitude Flow
- Dropping Convexity for Faster Semi-definite Optimization
- Undersampled Phase Retrieval via Majorization-Minimization
- Phase Retrieval Using Feasible Point Pursuit: Algorithms and Cramér-Rao Bound
- Reshaped Wirtinger Flow and Incremental Algorithm for Solving Quadratic System of Equations
- Phase Retrieval via Incremental Truncated Wirtinger Flow
- The local convexity of solving systems of quadratic equations
- Inexact Alternating Optimization for Phase Retrieval In the Presence of Outliers
- Fast Stochastic Algorithms for SVD and PCA: Convergence Properties and Convexity
- A Convex Formulation for Mixed Regression with Two Components: Minimax Optimal Rates
Cited by in corpus (14)
- Low Rank Phase Retrieval
- Solving Systems of Random Quadratic Equations via Truncated Amplitude Flow
- Undersampled Phase Retrieval via Majorization-Minimization
- An Overview of Advances in Signal Processing Techniques for Classical and Quantum Wideband Synthetic Apertures
- Compressive Phase Retrieval via Reweighted Amplitude Flow
- Inexact Alternating Optimization for Phase Retrieval In the Presence of Outliers
- Sparse Phase Retrieval via Truncated Amplitude Flow
- Phase Retrieval via Smooth Amplitude Flow
- Online Stochastic Gradient Descent with Arbitrary Initialization Solves Non-smooth, Non-convex Phase Retrieval
- Robust Wirtinger Flow for Phase Retrieval with Arbitrary Corruption
- Solving Almost all Systems of Random Quadratic Equations
- Sample-Efficient Sparse Phase Retrieval via Stochastic Alternating Minimization
- Phase Retrieval via Sparse Wirtinger Flow
- Asynchronous Variance-reduced Block Schemes for Composite Nonconvex Stochastic Optimization: Block-specific Steplengths and Adapted Batch-sizes