Sample-Efficient Sparse Phase Retrieval via Stochastic Alternating Minimization

In this work, we propose a nonconvex stochastic alternating minimizing (SAM) method for sparse phase retrieval, where an <tex-math notation="LaTeX">s</tex-math> -sparse vector of length <tex-math notation="LaTeX">n</tex-math> is recovered from <tex-math notation="LaTeX">m</tex-math> phaseless linear measurements. In each iteration of SAM, a batch of measurements is chosen randomly to form a sparse constrained least square subproblem, and then we employ a hard-thresholding pursuit algorithm to solve the resulting subproblem. We prove that the proposed SAM algorithm finds the target vector in at most <tex-math notation="LaTeX">O(log m)</tex-math> steps from <tex-math notation="LaTeX">Ω (slog n)</tex-math> samples if provided the initial guess is in a neighbour of the ground truth. Thus, together with a desired initial guess (e.g. via a spectral method), our proposed SAM algorithm is guaranteed to have a successful sparse phase retrieval with finitely many iterations. Further, numerical experiments illustrates that SAM requires less measurements than state-of-the-art algorithms for sparse phase retrieval problem.