Solving Systems of Random Quadratic Equations via Truncated Amplitude Flow

By G. Wang, Georgios B. Giannakis, Yonina C. Eldar. IEEE Transactions on Information Theory, 2016

387 citations recorded by the source corpus.

This paper presents a new algorithm, termed <italic>truncated amplitude flow</italic> (TAF), to recover an unknown vector <inline-formula> <tex-math notation="LaTeX">$ {x}$ </tex-math></inline-formula> from a system of quadratic equations of the form <inline-formula> <tex-math notation="LaTeX">$y_{i}=|\langle {a}_{i}, {x}\rangle |^{2}$ </tex-math></inline-formula>, where <inline-formula> <tex-math notation="LaTeX">$ {a}_{i}$ </tex-math></inline-formula>’s are given random measurement vectors. This problem is known to be <italic>NP-hard</italic> 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 <italic>amplitude-based</italic> empirical loss function and proceeds in two stages. In the first stage, we introduce an <italic>orthogonality-promoting</italic> initialization that can be obtained with a few power iterations. Stage two refines the initial estimate by successive updates of scalable <italic>truncated generalized gradient iterations</italic>, which are able to handle the rather challenging nonconvex and nonsmooth amplitude-based objective function. In particular, when vectors <inline-formula> <tex-math notation="LaTeX">$ {x}$ </tex-math></inline-formula> and <inline-formula> <tex-math notation="LaTeX">${a}_{i}$ </tex-math></inline-formula>’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.

Subfields: Computational Mechanics, Computer Vision and Pattern Recognition, Statistical and Nonlinear Physics

View Paper: https://www.semanticscholar.org/paper/cd1ae30a4d4e9367dc21a7606275e7faec710e3a

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Mechanics

In Computer Vision and Pattern Recognition

In Statistical and Nonlinear Physics

Citations in the corpus

Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview (2018, methodology): “This method has multiple variants [86], [87], and has been shown to be robust against noise.”
Implicit Regularization in Nonconvex Statistical Estimation: Gradient Descent Converges Linearly for Phase Retrieval, Matrix Completion, and Blind Deconvolution (2017, methodology): “We expect our leave-one-out analysis to accommodate other variants of spectral initialization studied in the literature [12,25,83,88,118].”
PhaseMax: Convex Phase Retrieval via Basis Pursuit (2016, methodology): “2 We see that PhaseMax requires the same sample complexity (number of required measurements) as compared to PhaseLift, TWF, and TAW, when used together with the truncated spectral initializer [17].”
"Convex Until Proven Guilty": Dimension-Free Acceleration of Gradient Descent on Non-Convex Functions (2017, methodology): “…learning and statistics have seen a shift toward large scale non-convex problems, including methods for matrix completion (Koren et al., 2009), phase retrieval (Candès et al., 2015; Wang et al., 2016), dictionary learning (Mairal et al., 2008), and neural network training (LeCun et al., 2015).”