Sparse signal recovery from phaseless measurements via hard thresholding pursuit

Cai，Jian Feng1; Li，Jingzhi2; Lu，Xiliang3; You，Juntao1

2022

10.1016/j.acha.2021.10.002

APPLIED AND COMPUTATIONAL HARMONIC ANALYSIS   影响因子和分区

1063-5203

1096-603X

In this paper, we consider the sparse phase retrieval problem, recovering an s-sparse signal x∈R from m phaseless samples y=|〈x,a〉| for i=1,…,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⁡(‖x‖/|x|)) steps, when {a} are i.i.d. standard Gaussian random vector with m∼O(slog⁡(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(slog⁡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.

Finite-step convergence Nonconvex algorithms Sparse phase retrieval

SCI ; EI

英语

其他

WOS:000707855000004

20214211033498

Computational efficiency ; Iterative methods ; Signal reconstruction

Information Theory and Signal Processing:716.1 ; Numerical Methods:921.6

MATHEMATICS

2-s2.0-85117106634

Scopus

1.Department of Mathematics,The Hong Kong University of Science and Technology,Kowloon,Clear Water Bay,Hong Kong
2.Department of Mathematics,International Center of Mathematics,Guangdong Provincial Key Laboratory for Computational Science and Material Design,Southern University of Science and Technology,Shenzhen,518005,China
3.School of Mathematics and Statistics,Hubei Key Laboratory of Computational Science,Wuhan University,Wuhan,430072,China

Cai，Jian Feng,Li，Jingzhi,Lu，Xiliang,et al. Sparse signal recovery from phaseless measurements via hard thresholding pursuit[J]. APPLIED AND COMPUTATIONAL HARMONIC ANALYSIS,2022,56:367-390.

Cai，Jian Feng,Li，Jingzhi,Lu，Xiliang,&You，Juntao.(2022).Sparse signal recovery from phaseless measurements via hard thresholding pursuit.APPLIED AND COMPUTATIONAL HARMONIC ANALYSIS,56,367-390.

Cai，Jian Feng,et al."Sparse signal recovery from phaseless measurements via hard thresholding pursuit".APPLIED AND COMPUTATIONAL HARMONIC ANALYSIS 56(2022):367-390.