A message-passing approach to phase retrieval of sparse signals

Philip Schniter, Sundeep Rangan

Research output: Chapter in Book/Report/Conference proceedingChapter

Abstract

In phase retrieval, the goal is to recover a signal x∈ ℂ N from the magnitudes of linear measurements Ax∈ ℂ M. While recent theory has established that M ≈ 4 N intensity measurements are necessary and sufficient to recover generic x, there is great interest in reducing the number of measurements through the exploitation of sparse x, which is known as compressive phase retrieval. In this work, we detail a novel, probabilistic approach to compressive phase retrieval based on the generalized approximate message passing (GAMP) algorithm. We then present a numerical study of the proposed PR-GAMP algorithm, demonstrating its excellent phase-transition behavior, robustness to noise, and runtime. For example, to successfully recover K-sparse signals, approximately M≥2Klog2(N/K) intensity measurements suffice when K ≪ N and A has i.i.d Gaussian entries. When recovering a 6k-sparse 65k-pixel grayscale image from 32k randomly masked and blurred Fourier intensity measurements, PR-GAMP achieved 99% success rate with a median runtime of only 12. 6 seconds. Compared to the recently proposed CPRL, sparse-Fienup, and GESPAR algorithms, experiments show that PR-GAMP has a superior phase transition and orders-of-magnitude faster runtimes as the problem dimensions increase.

Original languageEnglish (US)
Title of host publicationApplied and Numerical Harmonic Analysis
PublisherSpringer International Publishing
Pages177-204
Number of pages28
Edition9783319201870
DOIs
StatePublished - 2015

Publication series

NameApplied and Numerical Harmonic Analysis
Number9783319201870
ISSN (Print)2296-5009
ISSN (Electronic)2296-5017

Keywords

  • Belief propagation
  • Compressed sensing
  • Message passing
  • Phase retrieval
  • Sparsity

ASJC Scopus subject areas

  • Applied Mathematics

Fingerprint Dive into the research topics of 'A message-passing approach to phase retrieval of sparse signals'. Together they form a unique fingerprint.

Cite this