Provable Sample-Efficient Sparse Phase Retrieval Initialized by Truncated Power Method

Abstract

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=\Omega (s\log n)$ measurements, the widely used spectral initialization in the initialization stage requires $m=\Omega (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=\Omega (\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=\Omega (s\log n)$ and optimal. Numerical experiments illustrate that the proposed method is more sample-efficient than state-of-the-art algorithms.

References in corpus (12)

• Phase Retrieval via Wirtinger Flow: Theory and Algorithms
• Generalized power method for sparse principal component analysis
• Sparse principal component analysis and iterative thresholding
• A Geometric Analysis of Phase Retrieval
• Optimal Spectral Initialization for Signal Recovery with Applications to Phase Retrieval
• Efficient Compressive Phase Retrieval with Constrained Sensing Vectors
• Sparse Signal Recovery from Phaseless Measurements via Hard Thresholding Pursuit
• Scaling and Scalability: Provable Nonconvex Low-Rank Tensor Estimation from Incomplete Measurements
• Nearly optimal bounds for the global geometric landscape of phase retrieval
• Sample-Efficient Sparse Phase Retrieval via Stochastic Alternating Minimization
• Towards Sample-Optimal Compressive Phase Retrieval with Sparse and Generative Priors
• Hadamard Wirtinger Flow for Sparse Phase Retrieval

Cited by in corpus (1)

• Subspace Phase Retrieval