Sparse Phase Retrieval via Truncated Amplitude Flow

Abstract

This paper develops a novel algorithm, termed \emph{SPARse Truncated Amplitude flow} (SPARTA), to reconstruct a sparse signal from a small number of magnitude-only measurements. It deals with what is also known as sparse phase retrieval (PR), which is \emph{NP-hard} in general and emerges in many science and engineering applications. Upon formulating sparse PR as an amplitude-based nonconvex optimization task, SPARTA works iteratively in two stages: In stage one, the support of the underlying sparse signal is recovered using an analytically well-justified rule, and subsequently, a sparse orthogonality-promoting initialization is obtained via power iterations restricted on the support; and, in the second stage, the initialization is successively refined by means of hard thresholding based gradient-type iterations. SPARTA is a simple yet effective, scalable, and fast sparse PR solver. On the theoretical side, for any $n$-dimensional $k$-sparse ($k\ll n$) signal $\mathbf{x}$ with minimum (in modulus) nonzero entries on the order of $(1/\sqrt{k})\Vert \mathbf{x}{\Vert }_2$, SPARTA recovers the signal exactly (up to a global unimodular constant) from about $k^2\log n$ random Gaussian measurements with high probability. Furthermore, SPARTA incurs computational complexity on the order of $k^{2}n\log n$ with total runtime proportional to the time required to read the data, which improves upon the state-of-the-art by at least a factor of $k$. Finally, SPARTA is robust against additive noise of bounded support. Extensive numerical tests corroborate markedly improved recovery performance and speedups of SPARTA relative to existing alternatives.

23 pages; 5 figures

References in corpus (11)

• Compressive Phase Retrieval via Generalized Approximate Message Passing
• Solving Large-scale Systems of Random Quadratic Equations via Stochastic Truncated Amplitude Flow
• A Nonconvex Splitting Method for Symmetric Nonnegative Matrix Factorization: Convergence Analysis and Optimality
• Undersampled Phase Retrieval via Majorization-Minimization
• An Elementary Proof of Convex Phase Retrieval in the Natural Parameter Space via the Linear Program PhaseMax
• Reshaped Wirtinger Flow and Incremental Algorithm for Solving Quadratic System of Equations
• Solving (most) of a set of quadratic equalities: Composite optimization for robust phase retrieval
• Compressed Sensing from Phaseless Gaussian Measurements via Linear Programming in the Natural Parameter Space
• Stochastic Methods for Composite and Weakly Convex Optimization Problems
• Solving Almost all Systems of Random Quadratic Equations
• Sublinear-Time Algorithms for Compressive Phase Retrieval

Cited by in corpus (8)

• Solving Systems of Random Quadratic Equations via Truncated Amplitude Flow
• Randomized Block Frank-Wolfe for Convergent Large-Scale Learning
• Compressed Sensing from Phaseless Gaussian Measurements via Linear Programming in the Natural Parameter Space
• Denoising Poisson Phaseless Measurements via Orthogonal Dictionary Learning
• Solving Almost all Systems of Random Quadratic Equations
• SPRSF: Sparse Phase Retrieval via Smoothing Function
• Non-Convex Structured Phase Retrieval
• Provable Low Rank Phase Retrieval