Scalable Solvers of Random Quadratic Equations via Stochastic Truncated Amplitude Flow

DOI10.1109/TSP.2017.2652392zbMATH Open1414.94653arXiv1610.09540MaRDI QIDQ4620719FDOQ4620719

Georgios B. Giannakis, Gang Wang, Jie Chen

Publication date: 8 February 2019

Published in: IEEE Transactions on Signal Processing (Search for Journal in Brave)

Abstract: A novel approach termed emph{stochastic truncated amplitude flow} (STAF) is developed to reconstruct an unknown $n$-dimensional real-/complex-valued signal $$ from $m$ `phaseless' quadratic equations of the form $$. This problem, also known as phase retrieval from magnitude-only information, is emph{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 is useful when $n$ is large. When $$ are independent Gaussian, STAF provably recovers exactly any $$ 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 $$ vectors demonstrate that STAF empirically reconstructs any $$ 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.

Full work available at URL: https://arxiv.org/abs/1610.09540

Mathematics Subject Classification ID

Signal theory (characterization, reconstruction, filtering, etc.) (94A12)

Cited In (7)

• PhaseMax: Stable guarantees from noisy sub-Gaussian measurements
• Smoothed amplitude flow-based phase retrieval algorithm
• A Spectral Estimation Framework for Phase Retrieval via Bregman Divergence Minimization
• Phase retrieval with PhaseLift algorithm
• Wirtinger gradient descent methods for low-dose Poisson phase retrieval
• Truncated amplitude flow with coded diffraction patterns
• Asynchronous variance-reduced block schemes for composite non-convex stochastic optimization: block-specific steplengths and adapted batch-sizes

This page was built for publication: Scalable Solvers of Random Quadratic Equations via Stochastic Truncated Amplitude Flow

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4620719)