Sparse Phase Retrieval via Truncated Amplitude Flow

DOI10.1109/TSP.2017.2771733MaRDI QIDQ4621558zbMATH OpenFDO

Authors Gang Wang, L. Zhang, Mehmet Akçakaya, Jie Chen, Georgios B. Giannakis

Publication date 12 February 2019

Published in IEEE Transactions on Signal Processing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1611.07641

Mathematics Subject Classification ID

Signal theory (characterization, reconstruction, filtering, etc.) (94A12)

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 ($klln$) signal $$ with minimum (in modulus) nonzero entries on the order of $$, SPARTA recovers the signal exactly (up to a global unimodular constant) from about $k^{2}logn$ random Gaussian measurements with high probability. Furthermore, SPARTA incurs computational complexity on the order of $k^{2}nlogn$ 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.

Cited in

(22)

• Phase retrieval from Fourier measurements with masks
• Phase retrieval with PhaseLift algorithm
• Recovery under side constraints
• Constructing confidence intervals for the signals in sparse phase retrieval
• Implicit regularization in nonconvex statistical estimation: gradient descent converges linearly for phase retrieval, matrix completion, and blind deconvolution
• The recovery of complex sparse signals from few phaseless measurements
• Sparse signal recovery from phaseless measurements via hard thresholding pursuit
• Perturbed Amplitude Flow for Phase Retrieval
• Robust phase retrieval via median-truncated smoothed amplitude flow
• The numerics of phase retrieval
• The sampling complexity on nonconvex sparse phase retrieval problem
• Finding robust minimizer for non-convex phase retrieval
• Convex and Nonconvex Optimization Are Both Minimax-Optimal for Noisy Blind Deconvolution Under Random Designs
• Compressive phase retrieval: Optimal sample complexity with deep generative priors
• Provable sample-efficient sparse phase retrieval initialized by truncated power method
• Robust amplitude method with \(L_{1/2}\)-regularization for compressive phase retrieval
• Performance bounds of the intensity-based estimators for noisy phase retrieval
• Truncated amplitude flow with coded diffraction patterns
• Phasebook: a survey of selected open problems in phase retrieval
• Optimal sparse phase retrieval via a quasi-Bayesian approach
• Sparse recovery from quadratic measurements with external field
• Sparse signal recovery from phaseless measurements via _1² - _2² minimization

This page was built for publication: Sparse Phase Retrieval via Truncated Amplitude Flow

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4621558)