Timezone: »

Solving Random Systems of Quadratic Equations via Truncated Generalized Gradient Flow
Gang Wang · Georgios Giannakis

Wed Dec 07 09:00 AM -- 12:30 PM (PST) @ Area 5+6+7+8 #45 #None
This paper puts forth a novel algorithm, termed \emph{truncated generalized gradient flow} (TGGF), to solve for $\bm{x}\in\mathbb{R}^n/\mathbb{C}^n$ a system of $m$ quadratic equations $y_i=|\langle\bm{a}_i,\bm{x}\rangle|^2$, $i=1,2,\ldots,m$, which even for $\left\{\bm{a}_i\in\mathbb{R}^n/\mathbb{C}^n\right\}_{i=1}^m$ random is known to be \emph{NP-hard} in general. We prove that as soon as the number of equations $m$ is on the order of the number of unknowns $n$, TGGF recovers the solution exactly (up to a global unimodular constant) with high probability and complexity growing linearly with the time required to read the data $\left\{\left(\bm{a}_i;\,y_i\right)\right\}_{i=1}^m$. Specifically, TGGF proceeds in two stages: s1) A novel \emph{orthogonality-promoting} initialization that is obtained with simple power iterations; and, s2) a refinement of the initial estimate by successive updates of scalable \emph{truncated generalized gradient iterations}. The former is in sharp contrast to the existing spectral initializations, while the latter handles the rather challenging nonconvex and nonsmooth \emph{amplitude-based} cost function. Numerical tests demonstrate that: i) The novel orthogonality-promoting initialization method returns more accurate and robust estimates relative to its spectral counterparts; and ii) even with the same initialization, our refinement/truncation outperforms Wirtinger-based alternatives, all corroborating the superior performance of TGGF over state-of-the-art algorithms.

Author Information

Gang Wang (University of Minnesota)

Gang Wang received the B.Eng. degree in Electrical Engineering and Automation from the Beijing Institute of Technology, Beijing, China, in 2011. He is currently a Ph.D. candidate in the Department of Electrical and Computer Engineering at the University of Minnesota. His research interests focus on the areas of high-dimensional statistical learning, and nonconvex optimization, and deep learning. He received the National Scholarship from China in 2014, the Student Travel Grant from the Signal Processing Community in 2016, and a Best Student Paper Award at the 2017 European Signal Processing Conference.

Georgios Giannakis (University of Minnesota)

More from the Same Authors