Sparse Phase Retrieval: Convex Algorithms and Limitations

Abstract

We consider the problem of recovering signals from their power spectral density. This is a classical problem referred to in literature as the phase retrieval problem, and is of paramount importance in many fields of applied sciences. In general, additional prior information about the signal is required to guarantee unique recovery as the mapping from signals to power spectral density is not one-to-one. In this paper, we assume that the underlying signals are sparse. Recently, semidefinite programming (SDP) based approaches were explored by various researchers. Simulations of these algorithms strongly suggest that signals upto $o(\sqrt{n})$ sparsity can be recovered by this technique. In this work, we develop a tractable algorithm based on reweighted $l_1$-minimization that recovers a sparse signal from its power spectral density for significantly higher sparsities, which is unprecedented. We discuss the square-root bottleneck of the existing convex algorithms and show that a $k$-sparse signal can be efficiently recovered using $O(k^{2}logn)$ phaseless Fourier measurements. We also show that a $k$-sparse signal can be recovered using only $O(klogn)$ phaseless measurements if we are allowed to design the measurement matrices.

6 pages, 2 figures

References in corpus (3)

• Sparse Signal Recovery from Quadratic Measurements via Convex Programming
• Simultaneously Structured Models with Application to Sparse and Low-rank Matrices
• Reconstruction of Integers from Pairwise Distances

Cited by in corpus (9)

• Bispectrum Inversion with Application to Multireference Alignment
• Optimal Spectral Initialization for Signal Recovery with Applications to Phase Retrieval
• Robust Compressive Phase Retrieval via Deep Generative Priors
• Reconstruction of signals from their autocorrelation and cross-correlation vectors, with applications to phase retrieval and blind channel estimation
• Fast and Robust Compressive Phase Retrieval with Sparse-Graph Codes
• Multiple Illumination Phaseless Super-Resolution (MIPS) with Applications To Phaseless DOA Estimation and Diffraction Imaging
• Robust Sparse Phase Retrieval Made Easy
• Sparse Phase Retrieval via Sparse PCA Despite Model Misspecification: A Simplified and Extended Analysis
• An Algorithm for Exact Super-resolution and Phase Retrieval