Scalable Solvers of Random Quadratic Equations via Stochastic Truncated Amplitude Flow

Research output: Contribution to journalArticle

12 Citations (Scopus)

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

Fingerprint

Additive noise
Experiments

Keywords

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

Cite this

Scalable Solvers of Random Quadratic Equations via Stochastic Truncated Amplitude Flow. / Wang, Gang; Giannakis, Georgios B; Chen, Jie.

In: IEEE Transactions on Signal Processing, Vol. 65, No. 8, 7815432, 15.04.2017, p. 1961-1974.

Research output: Contribution to journalArticle

@article{a2744dbdf8b94e0eb71df600819e21d8,
title = "Scalable Solvers of Random Quadratic Equations via Stochastic Truncated Amplitude Flow",
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.",
keywords = "Kaczmarz algorithm, Nonconvex optimization, phase retrieval, variance reduction",
author = "Gang Wang and Giannakis, {Georgios B} and Jie Chen",
year = "2017",
month = "4",
day = "15",
doi = "10.1109/TSP.2017.2652392",
language = "English (US)",
volume = "65",
pages = "1961--1974",
journal = "IEEE Transactions on Signal Processing",
issn = "1053-587X",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
number = "8",

}

TY - JOUR

T1 - Scalable Solvers of Random Quadratic Equations via Stochastic Truncated Amplitude Flow

AU - Wang, Gang

AU - Giannakis, Georgios B

AU - Chen, Jie

PY - 2017/4/15

Y1 - 2017/4/15

N2 - 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.

AB - 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.

KW - Kaczmarz algorithm

KW - Nonconvex optimization

KW - phase retrieval

KW - variance reduction

UR - http://www.scopus.com/inward/record.url?scp=85015039837&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85015039837&partnerID=8YFLogxK

U2 - 10.1109/TSP.2017.2652392

DO - 10.1109/TSP.2017.2652392

M3 - Article

VL - 65

SP - 1961

EP - 1974

JO - IEEE Transactions on Signal Processing

JF - IEEE Transactions on Signal Processing

SN - 1053-587X

IS - 8

M1 - 7815432

ER -