Optimal Rates of Convergence for Noisy Sparse Phase Retrieval via Thresholded Wirtinger Flow
Tony Cai, Xiaodong Li, and Zongming Ma
-
Abstract:
This paper considers the noisy sparse phase retrieval problem: recovering a sparse signal
x ∈ Rp from noisy quadratic measurements yj = (aj' x)2 + εj, j=1, ..., m, with independent sub-exponential noise ε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 method for noiseless phase retrieval proposed and analyzed in [12],
a novel thresholded gradient descent algorithm is proposed and it is shown to adaptively achieve the minimax rates of convergence over a wide range of sparsity levels when the aj's are independent standard Gaussian random vectors, provided that the sample size is sufficiently large compared to the sparsity of x.
- Paper: pdf file.