Parallel Coordinate Descent Algorithms for Sparse Phase Retrieval

Abstract

In this paper, we study the sparse phase retrieval problem, that is, to estimate a sparse signal from a small number of noisy magnitude-only measurements. We propose an iterative soft-thresholding with exact line search algorithm (STELA). It is a parallel coordinate descent algorithm, which has several attractive features: i) fast convergence, as the approximate problem solved at each iteration exploits the original problem structure, ii) low complexity, as all variable updates have a closed-form expression, iii) easy implementation, as no hyperparameters are involved, and iv) guaranteed convergence to a stationary point for general measurements. These advantages are also demonstrated by numerical tests.