Speaker：Jianfeng Cai(The Hong Kong University of Science and Technology)

Time：2022-10-21, 16:00

Location：Tencent Meeting ID：869-197-552（No Password）

Abstract:

We study the sparse phase retrieval problem, recovering an s-sparse length-n signal x from m magnitude-only measurements. Two-stage non-convex approaches have drawn much attention in recent studies for this problem. Despite non-convexity, most two-stage algorithms like projected gradient descent and its variants are guaranteed to achieve linear convergence when appropriately initialized. However, in terms of sample complexity, the bottleneck of most existing non-convex algorithms usually comes from the first stage, namely the initialization stage. The widely used spectral method requires m>=O(s^2 log n) measurements to produce a desired initial guess, which dominates non-convex algorithms. To reduce the number of measurements, we propose a simple truncated power method as an initialization strategy for non-convex algorithms in this work. Theoretically, we show that m>=O(s' s log n) measurements are sufficient to recover the signal, where s'=||x||_2^2/||x||_{\infty}^2 is the stable sparsity of x. When the underlying signal contains at least one significant component, s'=O(1), and our sample complexity m>=O(s log n) is nearly optimal. Numerical experiments illustrate that the proposed method is more sample-efficient than state-of-the-art algorithms.