论文标题
通过硬阈值追踪从无量音测量中恢复稀疏信号
Sparse Signal Recovery from Phaseless Measurements via Hard Thresholding Pursuit
论文作者
论文摘要
在本文中，我们考虑稀疏的相位检索问题，恢复了$ s $ -sparse信号$ \ bm {x}^{\ natural} \ in \ mathbb {r} $ i = 1，\ ldots，m $。现有的稀疏相检索算法通常是一阶，因此最多线性地收敛。受压缩传感中的硬阈值追踪（HTP）算法的启发，我们提出了一种有效的二阶算法，用于稀疏相位检索。从理论上讲，我们提出的算法可以保证在有限的情况下具有精确的稀疏信号恢复（尤其是$ o（\ log m + \ log（\ | \ | \ | \ | \ | \ | \ | \ | $ \ {\ bm {a} _i \} _ {i = 1}^{m} $是i.i.d.标准高斯随机向量，带有$ M \ sim O（s \ log（n/s））$，初始化位于基础稀疏信号的邻域。与光谱初始化一起，我们的算法可以从$ O（s^2 \ log n）$样本中具有精确的恢复。由于我们提出的算法的计算成本与流行的一阶算法相同，因此我们的算法非常有效。实验结果表明，我们的算法可能比现有稀疏相检索算法快几倍。
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.
