Optimal Rates of Convergence for Noisy Sparse Phase Retrieval via Thresholded Wirtinger Flow
arXiv:1506.03382
Abstract
This paper considers the noisy sparse phase retrieval problem: recovering a sparse signal from noisy quadratic measurements , , with independent sub-exponential noise . The goals are to understand the effect of the sparsity of 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 's are independent standard Gaussian random vectors, provided that the sample size is sufficiently large compared to the sparsity of .
arXiv comment28 pages, 4 figures
References in corpus (8)
- Sparse principal component analysis and iterative thresholding
- Optimally Tuned Iterative Reconstruction Algorithms for Compressed Sensing
- Truncated Power Method for Sparse Eigenvalue Problems
- Alternating Projection, Ptychographic Imaging and Phase Synchronization
- Phase Retrieval with Application to Optical Imaging
- Gradient Hard Thresholding Pursuit for Sparsity-Constrained Optimization
- Sparse CCA: Adaptive Estimation and Computational Barriers
- Minimax rate of convergence and the performance of ERM in phase recovery
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