Solving large-scale systems of random quadratic equations via stochastic truncated amplitude flow

Gang Wang, Georgios B. Giannakis, Jie Chen

Research output: Chapter in Book/Report/Conference proceedingConference contribution

2 Scopus citations

Abstract

This work develops a new iterative algorithm, which is called stochastic truncated amplitude flow (STAF), to recover an unknown signal x ϵ Rn from m "phaseless" quadratic equations of the form i = |aTi x|, 1 < i < m. This problem is also known as phase retrieval, which is NP-hard in general. Building on an amplitude-based nonconvex least-squares formulation, STAF proceeds in two stages: s1) Orthogonality-promoting initialization computed using a stochastic variance reduced gradient algorithm; and, s2) Refinements of the initial point through truncated stochastic gradient-type iterations. Both stages handle a single equation per iteration, therefore lending STAF well to Big Data applications. Specifically for independent Gaussian {ai}mi =1 vectors, STAF recovers exactly any x exponentially fast when there are about as many equations as unknowns. Finally, numerical tests demonstrate that STAF improves upon its competing alternatives.

Original languageEnglish (US)
Title of host publication25th European Signal Processing Conference, EUSIPCO 2017
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages1420-1424
Number of pages5
ISBN (Electronic)9780992862671
DOIs
StatePublished - Oct 23 2017
Event25th European Signal Processing Conference, EUSIPCO 2017 - Kos, Greece
Duration: Aug 28 2017Sep 2 2017

Publication series

Name25th European Signal Processing Conference, EUSIPCO 2017
Volume2017-January

Other

Other25th European Signal Processing Conference, EUSIPCO 2017
CountryGreece
CityKos
Period8/28/179/2/17

Keywords

  • Global optimum
  • Linear convergence
  • Phase retrieval
  • Stochastic nonconvex optimization
  • Stochastic variance reduced gradient

Fingerprint Dive into the research topics of 'Solving large-scale systems of random quadratic equations via stochastic truncated amplitude flow'. Together they form a unique fingerprint.

Cite this