  In this paper, we consider the sparse phase retrieval problem, recovering an
$s$-sparse signal $\bm{x}^{\natural}\in\mathbb{R}^n$ from $m$ phaseless samples
$y_i=|\langle\bm{x}^{\natural},\bm{a}_i\rangle|$ for $i=1,\ldots,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(\|\bm{x}^{\natural}\|_2/|x_{\min}^{\natural}|))$) steps, when
$\{\bm{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.

Numerical Analysis;Numerical Analysis