Poster
A Fast and Provable Algorithm for Sparse Phase Retrieval
Jian-Feng Cai · Yu Long · Ruixue WEN · Jiaxi Ying
Halle B #234
Abstract:
We study the sparse phase retrieval problem, which seeks to recover a sparse signal from a limited set of magnitude-only measurements. In contrast to prevalent sparse phase retrieval algorithms that primarily use first-order methods, we propose an innovative second-order algorithm that employs a Newton-type method with hard thresholding. This algorithm overcomes the linear convergence limitations of first-order methods while preserving their hallmark per-iteration computational efficiency. We provide theoretical guarantees that our algorithm converges to the s-sparse ground truth signal x♮∈Rn (up to a global sign) at a quadratic convergence rate after at most O(log(‖x♮‖/x♮min)) iterations, using Ω(s2logn) Gaussian random samples. Numerical experiments show that our algorithm achieves a significantly faster convergence rate than state-of-the-art methods.
Chat is not available.