A Fast and Provable Algorithm for Sparse Phase Retrieval
share
We study the sparse phase retrieval problem, which aims to recover a sparse signal from a limited number of phaseless measurements. Existing algorithms for sparse phase retrieval primarily rely on first-order methods with linear convergence rate. In this paper, we propose an efficient second-order algorithm based on Newton projection, which maintains the same per-iteration computational complexity as popular first-order methods. The proposed algorithm is theoretically guaranteed to converge to the ground truth (up to a global sign) at a quadratic convergence rate after at most O(log (‖𝐱^♮ ‖ /x_min^♮)) iterations, provided a sample complexity of O(s^2log n), where 𝐱^♮∈ℝ^n represents an s-sparse ground truth signal. Numerical experiments demonstrate that our algorithm not only outperforms state-of-the-art methods in terms of achieving a significantly faster convergence rate, but also excels in attaining a higher success rate for exact signal recovery from noise-free measurements and providing enhanced signal reconstruction in noisy scenarios.
READ FULL TEXT