## Abstract

We consider the problem of recovering a signal x^{∗} ∈ ℝ^{n}, from magnitude-only measurements, y_{i} = | (a_{i}, x^{∗}} | for i = {1,2,⋯, m}. Also known as the phase retrieval problem, it is a fundamental challenge in nano-, bio- and astronomical imaging systems, and speech processing. The problem is ill-posed, and therefore additional assumptions on the signal and/or the measurements are necessary. In this paper, we first study the case where the underlying signal x^{∗} is s-sparse. We develop a novel recovery algorithm that we call Compressive Phase Retrieval with Alternating Minimization, or CoPRAM. Our algorithm is simple and can be obtained via a natural combination of the classical alternating minimization approach for phase retrieval, with the CoSaMP algorithm for sparse recovery. Despite its simplicity, we prove that our algorithm achieves a sample complexity of O (s^{2} log n) with Gaussian samples, which matches the best known existing results. It also demonstrates linear convergence in theory and practice and requires no extra tuning parameters other than the signal sparsity level s. We then consider the case where the underlying signal x^{∗} arises from structured sparsity models. We specifically examine the case of block-sparse signals with uniform block size of b and block sparsity k = s/b. For this problem, we design a recovery algorithm that we call Block CoPRAM that further reduces the sample complexity to O (ks log n). For sufficiently large block lengths of b = Θ(s), this bound equates to O (s log n). To our knowledge, this constitutes the first end-to-end linearly convergent family of algorithms for phase retrieval where the Gaussian sample complexity has a sub-quadratic dependence on the sparsity level of the signal.

Original language | English (US) |
---|---|

Pages (from-to) | 4918-4928 |

Number of pages | 11 |

Journal | Advances in Neural Information Processing Systems |

Volume | 2017-December |

State | Published - 2017 |

Event | 31st Annual Conference on Neural Information Processing Systems, NIPS 2017 - Long Beach, United States Duration: Dec 4 2017 → Dec 9 2017 |

## ASJC Scopus subject areas

- Computer Networks and Communications
- Information Systems
- Signal Processing