Sparse Signal Recovery from Phaseless Measurements via Hard Thresholding Pursuit

Abstract

In this paper, we consider the sparse phase retrieval problem, recovering an $s$-sparse signal ${\mathbf{x}}^{♮}\in {\mathbb{R}}^n$ from $m$ phaseless samples $y_i=|⟨{\mathbf{x}}^{♮},{\mathbf{a}}_i⟩|$ for $i=1,\dots ,m$. Existing sparse phase retrieval algorithms are usually first-order and hence converge at most linearly. Inspired by the hard thresholding pursuit (HTP) algorithm in compressed sensing, we propose an efficient second-order algorithm for sparse phase retrieval. Our proposed algorithm is theoretically guaranteed to give an exact sparse signal recovery in finite (in particular, at most $O(\log m+\log (\Vert {\mathbf{x}}^{♮}{\Vert }_2/|x_{\min }^{♮}|))$) steps, when $\{{\mathbf{a}}_i{\}}_{i=1}^m$ are i.i.d. standard Gaussian random vector with $m\sim O(s\log (n/s))$ and the initialization is in a neighborhood of the underlying sparse signal. Together with a spectral initialization, our algorithm is guaranteed to have an exact recovery from $O(s^2\log n)$ samples. Since the computational cost per iteration of our proposed algorithm is the same order as popular first-order algorithms, our algorithm is extremely efficient. Experimental results show that our algorithm can be several times faster than existing sparse phase retrieval algorithms.

Cited by in corpus (4)

• Sample-Efficient Sparse Phase Retrieval via Stochastic Alternating Minimization
• Provable Sample-Efficient Sparse Phase Retrieval Initialized by Truncated Power Method
• Subspace Phase Retrieval
• Instance optimality in phase retrieval