Solving Large-scale Systems of Random Quadratic Equations via Stochastic Truncated Amplitude Flow

Abstract

A novel approach termed \emph{stochastic truncated amplitude flow} (STAF) is developed to reconstruct an unknown $n$-dimensional real-/complex-valued signal $\mathbf{x}$ from $m$ `phaseless' quadratic equations of the form ${\psi }_i=|⟨{\mathbf{a}}_i,\mathbf{x}⟩|$. 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 $n$ is large. When $\{{\mathbf{a}}_i{\}}_{i=1}^m$ are independent Gaussian, STAF provably recovers exactly any $\mathbf{x}\in {\mathbb{R}}^n$ exponentially fast based on order of $n$ quadratic equations. STAF is also robust in the presence of additive noise of bounded support. Simulated tests involving real Gaussian $\{{\mathbf{a}}_i\}$ vectors demonstrate that STAF empirically reconstructs any $\mathbf{x}\in {\mathbb{R}}^n$ exactly from about $2.3n$ magnitude-only measurements, outperforming state-of-the-art approaches and narrowing the gap from the information-theoretic number of equations $m=2n-1$. Extensive experiments using synthetic data and real images corroborate markedly improved performance of STAF over existing alternatives.

21 pages, 12 figures

References in corpus (9)

• Identifying and attacking the saddle point problem in high-dimensional non-convex optimization
• Escaping From Saddle Points --- Online Stochastic Gradient for Tensor Decomposition
• Phaseless Rcovery using Gauss-Newton Method
• Low Rank Phase Retrieval
• Solving Systems of Random Quadratic Equations via Truncated Amplitude Flow
• Undersampled Phase Retrieval via Majorization-Minimization
• Reshaped Wirtinger Flow and Incremental Algorithm for Solving Quadratic System of Equations
• Phase Retrieval via Incremental Truncated Wirtinger Flow
• Inexact Alternating Optimization for Phase Retrieval In the Presence of Outliers

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