Scalable Solvers of Random Quadratic Equations via Stochastic Truncated Amplitude Flow

Gang Wang, Georgios B. Giannakis, Jie Chen

Research output: Contribution to journalArticlepeer-review

26 Scopus citations

Abstract

A novel approach termed stochastic truncated amplitude flow (STAF) is developed to reconstruct an unknown n-dimensional real-/complex-valued signal x fromm "phaseless" quadratic equations of the form Ψi = |ai, x|. This problem, also known as phase retrieval from magnitude-only information, is NP-hard in general. Adopting an amplitude-based nonconvex formulation, STAF leads to an iterative solver comprising two stages: s1) Orthogonality-promoting initialization through a stochastic variance reduced gradient algorithm; and, s2) a series of iterative refinements of the initialization using stochastic truncated gradient iterations. Both stages involve a single equation per iteration, thus rendering STAF a simple, scalable, and fast approach amenable to large-scale implementations that are useful when n is large. When {ai}m i=1 are independent Gaussian, STAF provably recovers exactly any x ϵ Rn exponentially fast based on order of n quadratic equations. STAF is also robust in the presence of additive noise of bounded support. Simulated tests involving real Gaussian {ai} vectors demonstrate that STAF empirically reconstructs any x ϵ Rn exactly from about 2.3n magnitude-only measurements, outperforming state-of-the-art approaches and narrowing the gap from the information-theoretic number of equations m = 2n - 1. Extensive experiments using synthetic data and real images corroborate markedly improved performance of STAF over existing alternatives.

Original languageEnglish (US)
Article number7815432
Pages (from-to)1961-1974
Number of pages14
JournalIEEE Transactions on Signal Processing
Volume65
Issue number8
DOIs
StatePublished - Apr 15 2017

Bibliographical note

Funding Information:
This work was supported in part by NSF under Grant 1500713 and Grant 1514056.

Publisher Copyright:
© 2017 IEEE.

Keywords

  • Kaczmarz algorithm
  • Nonconvex optimization
  • phase retrieval
  • variance reduction

Fingerprint

Dive into the research topics of 'Scalable Solvers of Random Quadratic Equations via Stochastic Truncated Amplitude Flow'. Together they form a unique fingerprint.

Cite this