Solving systems of random quadratic equations via truncated amplitude flow

Research output: Contribution to journalArticle

42 Citations (Scopus)

Abstract

This paper presents a new algorithm, termed truncated amplitude flow (TAF), to recover an unknown vector x from a system of quadratic equations of the form yi=|{ai, x}|2, where a-i's are given random measurement vectors. This problem is known to be NP-hard in general. We prove that as soon as the number of equations is on the order of the number of unknowns, TAF recovers the solution exactly (up to a global unimodular constant) with high probability and complexity growing linearly with both the number of unknowns and the number of equations. Our TAF approach adapts the amplitude-based empirical loss function and proceeds in two stages. In the first stage, we introduce an orthogonality-promoting initialization that can be obtained with a few power iterations. Stage two refines the initial estimate by successive updates of scalable truncated generalized gradient iterations, which are able to handle the rather challenging nonconvex and nonsmooth amplitude-based objective function. In particular, when vectors x and ai's are real valued, our gradient truncation rule provably eliminates erroneously estimated signs with high probability to markedly improve upon its untruncated version. Numerical tests using synthetic data and real images demonstrate that our initialization returns more accurate and robust estimates relative to spectral initializations. Furthermore, even under the same initialization, the proposed amplitude-based refinement outperforms existing Wirtinger flow variants, corroborating the superior performance of TAF over state-of-the-art algorithms.

Original languageEnglish (US)
Article number8049465
Pages (from-to)773-794
Number of pages22
JournalIEEE Transactions on Information Theory
Volume64
Issue number2
DOIs
StatePublished - Feb 1 2018

Fingerprint

performance

Keywords

  • Amplitude-based cost function
  • Linear convergence to global minimum
  • Nonconvex optimization
  • Orthogonality-promoting initialization
  • Phase retrieval
  • Truncated gradient

Cite this

Solving systems of random quadratic equations via truncated amplitude flow. / Wang, Gang; Giannakis, Georgios B; Eldar, Yonina C.

In: IEEE Transactions on Information Theory, Vol. 64, No. 2, 8049465, 01.02.2018, p. 773-794.

Research output: Contribution to journalArticle

@article{d31b22522d1b4a7fb157b87a904a02aa,
title = "Solving systems of random quadratic equations via truncated amplitude flow",
abstract = "This paper presents a new algorithm, termed truncated amplitude flow (TAF), to recover an unknown vector x from a system of quadratic equations of the form yi=|{ai, x}|2, where a-i's are given random measurement vectors. This problem is known to be NP-hard in general. We prove that as soon as the number of equations is on the order of the number of unknowns, TAF recovers the solution exactly (up to a global unimodular constant) with high probability and complexity growing linearly with both the number of unknowns and the number of equations. Our TAF approach adapts the amplitude-based empirical loss function and proceeds in two stages. In the first stage, we introduce an orthogonality-promoting initialization that can be obtained with a few power iterations. Stage two refines the initial estimate by successive updates of scalable truncated generalized gradient iterations, which are able to handle the rather challenging nonconvex and nonsmooth amplitude-based objective function. In particular, when vectors x and ai's are real valued, our gradient truncation rule provably eliminates erroneously estimated signs with high probability to markedly improve upon its untruncated version. Numerical tests using synthetic data and real images demonstrate that our initialization returns more accurate and robust estimates relative to spectral initializations. Furthermore, even under the same initialization, the proposed amplitude-based refinement outperforms existing Wirtinger flow variants, corroborating the superior performance of TAF over state-of-the-art algorithms.",
keywords = "Amplitude-based cost function, Linear convergence to global minimum, Nonconvex optimization, Orthogonality-promoting initialization, Phase retrieval, Truncated gradient",
author = "Gang Wang and Giannakis, {Georgios B} and Eldar, {Yonina C.}",
year = "2018",
month = "2",
day = "1",
doi = "10.1109/TIT.2017.2756858",
language = "English (US)",
volume = "64",
pages = "773--794",
journal = "IEEE Transactions on Information Theory",
issn = "0018-9448",
publisher = "IEEE",
number = "2",

}

TY - JOUR

T1 - Solving systems of random quadratic equations via truncated amplitude flow

AU - Wang, Gang

AU - Giannakis, Georgios B

AU - Eldar, Yonina C.

PY - 2018/2/1

Y1 - 2018/2/1

N2 - This paper presents a new algorithm, termed truncated amplitude flow (TAF), to recover an unknown vector x from a system of quadratic equations of the form yi=|{ai, x}|2, where a-i's are given random measurement vectors. This problem is known to be NP-hard in general. We prove that as soon as the number of equations is on the order of the number of unknowns, TAF recovers the solution exactly (up to a global unimodular constant) with high probability and complexity growing linearly with both the number of unknowns and the number of equations. Our TAF approach adapts the amplitude-based empirical loss function and proceeds in two stages. In the first stage, we introduce an orthogonality-promoting initialization that can be obtained with a few power iterations. Stage two refines the initial estimate by successive updates of scalable truncated generalized gradient iterations, which are able to handle the rather challenging nonconvex and nonsmooth amplitude-based objective function. In particular, when vectors x and ai's are real valued, our gradient truncation rule provably eliminates erroneously estimated signs with high probability to markedly improve upon its untruncated version. Numerical tests using synthetic data and real images demonstrate that our initialization returns more accurate and robust estimates relative to spectral initializations. Furthermore, even under the same initialization, the proposed amplitude-based refinement outperforms existing Wirtinger flow variants, corroborating the superior performance of TAF over state-of-the-art algorithms.

AB - This paper presents a new algorithm, termed truncated amplitude flow (TAF), to recover an unknown vector x from a system of quadratic equations of the form yi=|{ai, x}|2, where a-i's are given random measurement vectors. This problem is known to be NP-hard in general. We prove that as soon as the number of equations is on the order of the number of unknowns, TAF recovers the solution exactly (up to a global unimodular constant) with high probability and complexity growing linearly with both the number of unknowns and the number of equations. Our TAF approach adapts the amplitude-based empirical loss function and proceeds in two stages. In the first stage, we introduce an orthogonality-promoting initialization that can be obtained with a few power iterations. Stage two refines the initial estimate by successive updates of scalable truncated generalized gradient iterations, which are able to handle the rather challenging nonconvex and nonsmooth amplitude-based objective function. In particular, when vectors x and ai's are real valued, our gradient truncation rule provably eliminates erroneously estimated signs with high probability to markedly improve upon its untruncated version. Numerical tests using synthetic data and real images demonstrate that our initialization returns more accurate and robust estimates relative to spectral initializations. Furthermore, even under the same initialization, the proposed amplitude-based refinement outperforms existing Wirtinger flow variants, corroborating the superior performance of TAF over state-of-the-art algorithms.

KW - Amplitude-based cost function

KW - Linear convergence to global minimum

KW - Nonconvex optimization

KW - Orthogonality-promoting initialization

KW - Phase retrieval

KW - Truncated gradient

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

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

U2 - 10.1109/TIT.2017.2756858

DO - 10.1109/TIT.2017.2756858

M3 - Article

VL - 64

SP - 773

EP - 794

JO - IEEE Transactions on Information Theory

JF - IEEE Transactions on Information Theory

SN - 0018-9448

IS - 2

M1 - 8049465

ER -