Fast, sample-efficient algorithms for structured phase retrieval

Gauri Jagatap, Chinmay Hegde

    Research output: Contribution to journalConference articlepeer-review


    We consider the problem of recovering a signal x ∈ ℝn, from magnitude-only measurements, yi = | (ai, 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 (s2 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 languageEnglish (US)
    Pages (from-to)4918-4928
    Number of pages11
    JournalAdvances in Neural Information Processing Systems
    StatePublished - 2017
    Event31st Annual Conference on Neural Information Processing Systems, NIPS 2017 - Long Beach, United States
    Duration: Dec 4 2017Dec 9 2017

    ASJC Scopus subject areas

    • Computer Networks and Communications
    • Information Systems
    • Signal Processing


    Dive into the research topics of 'Fast, sample-efficient algorithms for structured phase retrieval'. Together they form a unique fingerprint.

    Cite this