Optimal Rates of Convergence for Noisy Sparse Phase Retrieval via Thresholded Wirtinger Flow

Abstract

This paper considers the noisy sparse phase retrieval problem: recovering a sparse signal $x\in {\mathbb{R}}^p$ from noisy quadratic measurements $y_j=(a_j^{\prime }x{)}^2+{\epsilon }_j$, $j=1,\dots ,m$, with independent sub-exponential noise ${\epsilon }_j$. The goals are to understand the effect of the sparsity of $x$ on the estimation precision and to construct a computationally feasible estimator to achieve the optimal rates. Inspired by the Wirtinger Flow [12] proposed for noiseless and non-sparse phase retrieval, a novel thresholded gradient descent algorithm is proposed and it is shown to adaptively achieve the minimax optimal rates of convergence over a wide range of sparsity levels when the $a_j$'s are independent standard Gaussian random vectors, provided that the sample size is sufficiently large compared to the sparsity of $x$.

28 pages, 4 figures

Cited by in corpus (7)

• Rapid, Robust, and Reliable Blind Deconvolution via Nonconvex Optimization
• Sparse Nonlinear Regression: Parameter Estimation and Asymptotic Inference
• Reshaped Wirtinger Flow and Incremental Algorithm for Solving Quadratic System of Equations
• Accelerated Wirtinger Flow: A fast algorithm for ptychography
• Compressed Sensing from Phaseless Gaussian Measurements via Linear Programming in the Natural Parameter Space
• Corruption Robust Phase Retrieval via Linear Programming
• On Stein's Identity and Near-Optimal Estimation in High-dimensional Index Models