OPTIMAL RATES OF CONVERGENCE FOR NOISY SPARSE PHASE RETRIEVAL VIA THRESHOLDED WIRTINGER FLOW

This paper considers the noisy sparse phase retrieval problem: recovering a sparse signal x . .p from noisy quadratic measurements yj = (a.jx)² + .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 adaptively. Inspired by the Wirtinger Flow [IEEE Trans. Inform. Theory 61 (2015) 1985-2007] proposed for non-sparse and noiseless 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 aj's are independent standard Gaussian random vectors, provided that the sample size is sufficiently large compared to the sparsity of x.