Efficient recovery of sparse signal from phaseless measurements

Abstract

This thesis is to study theories and efficient algorithms for sparse phase retrieval problem, and two non-convex methods are introduced in the work. The sparse phase retrieval problem is to recover an s-sparse signal x^♮ ∈ Rⁿ (s << n) from m phaseless samples y_i = │❬x^♮,a_i❭│ for i = 1, . . . ,m. Sparse phase retrieval problem arises in many applications related to signal and image processing. The task of the work is to develop efficient algorithms and theories for the problem using few number of measurements, especially in case of m < n. Existing gradient descent type methods for sparse phase retrieval are first-order and hence converge at most linearly. In the thesis, firstly, a Newton's approach named HTP for sparse phase retrieval has been introduced, which is guaranteed to find the underlying signal in finite steps using only m ～ O(s log(n/s)) Gaussian samples and the initialization is in a neighbourhood of the underlying sparse signal. Together with a spectral initialization, HTP is guaranteed to have an exact recovery from O(s² log n) samples. While the computational cost per iteration is the same order as first order methods, the proposed algorithm is quite efficient in terms of cpu time and numerical experiments illustrates that the proposed HTP is several times faster than state-of-the-art algorithms. Further, based on a standard alternating minimization for sparse phase retrieval, a novel stochastic version of alternating minimization method for the problem has been proposed in the work. By introducing a generalized RIP condition on the sensing matrix, theoretical justification for the finite step convergence (in at most O(log m) steps) of the proposed stochastic algorithm is provided. Numerical experiments show that the proposed stochastic algorithm requires less measurements than state-of-the-art algorithms.

Date of Award	2021
Original language	English
Awarding Institution	The Hong Kong University of Science and Technology
Supervisor	Jianfeng CAI (Supervisor) & Jingzhi Li (Supervisor)