Timezone: »

Solving Most Systems of Random Quadratic Equations
Gang Wang · Georgios Giannakis · Yousef Saad · Jie Chen

Mon Dec 04 06:30 PM -- 10:30 PM (PST) @ Pacific Ballroom #163
This paper deals with finding an $n$-dimensional solution $\bm{x}$ to a system of quadratic equations $y_i=|\langle\bm{a}_i,\bm{x}\rangle|^2$, $1\le i \le m$, which in general is known to be NP-hard. We put forth a novel procedure, that starts with a \emph{weighted maximal correlation initialization} obtainable with a few power iterations, followed by successive refinements based on \emph{iteratively reweighted gradient-type iterations}. The novel techniques distinguish themselves from prior works by the inclusion of a fresh (re)weighting regularization. For certain random measurement models, the proposed procedure returns the true solution $\bm{x}$ with high probability in time proportional to reading the data $\{(\bm{a}_i;y_i)\}_{1\le i \le m}$, provided that the number $m$ of equations is some constant $c>0$ times the number $n$ of unknowns, that is, $m\ge cn$. Empirically, the upshots of this contribution are: i) perfect signal recovery in the high-dimensional regime given only an \emph{information-theoretic limit number} of equations; and, ii) (near-)optimal statistical accuracy in the presence of additive noise. Extensive numerical tests using both synthetic data and real images corroborate its improved signal recovery performance and computational efficiency relative to state-of-the-art approaches.

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)
Yousef Saad (University of Minnesota)
Jie Chen (Beijing Institute of Technology)

More from the Same Authors