论文标题
可证明的样品有效的稀疏相检索，通过截短的功率法初始化
Provable Sample-Efficient Sparse Phase Retrieval Initialized by Truncated Power Method
论文作者
论文摘要
我们研究了稀疏的相位检索问题，从$ m $幅度的测量值中恢复了$ S $ -SPARSE长度 - $ n $信号。在最近的研究中，两阶段的非凸方法吸引了很多关注。尽管非跨性别性，但在适当初始化时，许多两阶段算法可将基础解决方案汇总到基础解决方案。但是，就样本复杂性而言，这些算法的瓶颈通常来自初始化阶段。尽管改进阶段通常仅需要$ m =ω（s \ log n）$测量值，但初始化阶段中广泛使用的光谱初始化需要$ m =ω（s^2 \ log n）$测量来产生所需的初始猜测，这会导致总样品复杂性订单，从而比必要的多。为了减少测量数量，我们提出了一种截断的功率方法，以替换非凸稀疏相检索算法的光谱初始化。我们证明$ m =ω（\ bar {s} s \ log n）$测量值，其中$ \ bar {s} $是基础信号的稳定稀疏性，足以产生所需的初始猜测。当基础信号仅包含很少的重要组件时，所提出的算法的样品复杂性为$ m =ω（s \ log n）$且最佳。数值实验表明，所提出的方法比最先进的算法更有效。
We study the sparse phase retrieval problem, recovering an $s$-sparse length-$n$ signal from $m$ magnitude-only measurements. Two-stage non-convex approaches have drawn much attention in recent studies for this problem. Despite non-convexity, many two-stage algorithms provably converge to the underlying solution linearly when appropriately initialized. However, in terms of sample complexity, the bottleneck of those algorithms often comes from the initialization stage. Although the refinement stage usually needs only $m=Ω(s\log n)$ measurements, the widely used spectral initialization in the initialization stage requires $m=Ω(s^2\log n)$ measurements to produce a desired initial guess, which causes the total sample complexity order-wisely more than necessary. To reduce the number of measurements, we propose a truncated power method to replace the spectral initialization for non-convex sparse phase retrieval algorithms. We prove that $m=Ω(\bar{s} s\log n)$ measurements, where $\bar{s}$ is the stable sparsity of the underlying signal, are sufficient to produce a desired initial guess. When the underlying signal contains only very few significant components, the sample complexity of the proposed algorithm is $m=Ω(s\log n)$ and optimal. Numerical experiments illustrate that the proposed method is more sample-efficient than state-of-the-art algorithms.
