Timezone: »
This paper is concerned with finding a solution x to a quadratic system of equations yi = < ai, x >^2, i = 1, 2, ..., m. We prove that it is possible to solve unstructured quadratic systems in n variables exactly from O(n) equations in linear time, that is, in time proportional to reading and evaluating the data. This is accomplished by a novel procedure, which starting from an initial guess given by a spectral initialization procedure, attempts to minimize a nonconvex objective. The proposed algorithm distinguishes from prior approaches by regularizing the initialization and descent procedures in an adaptive fashion, which discard terms bearing too much influence on the initial estimate or search directions. These careful selection ruleswhich effectively serve as a variance reduction schemeprovide a tighter initial guess, more robust descent directions, and thus enhanced practical performance. Further, this procedure also achieves a nearoptimal statistical accuracy in the presence of noise. Finally, we demonstrate empirically that the computational cost of our algorithm is about four times that of solving a leastsquares problem of the same size.
Author Information
Yuxin Chen (Stanford University)
Emmanuel Candes (Stanford University)
More from the Same Authors

2021 Oral: Adaptive Conformal Inference Under Distribution Shift »
Isaac Gibbs · Emmanuel Candes 
2021 Poster: Adaptive Conformal Inference Under Distribution Shift »
Isaac Gibbs · Emmanuel Candes 
2020 Poster: Achieving Equalized Odds by Resampling Sensitive Attributes »
Yaniv Romano · Stephen Bates · Emmanuel Candes 
2020 Poster: Classification with Valid and Adaptive Coverage »
Yaniv Romano · Matteo Sesia · Emmanuel Candes 
2020 Spotlight: Classification with Valid and Adaptive Coverage »
Yaniv Romano · Matteo Sesia · Emmanuel Candes 
2019 Poster: Conformalized Quantile Regression »
Yaniv Romano · Evan Patterson · Emmanuel Candes 
2019 Poster: Conformal Prediction Under Covariate Shift »
Ryan Tibshirani · Rina Barber · Emmanuel Candes · Aaditya Ramdas 
2015 Oral: Solving Random Quadratic Systems of Equations Is Nearly as Easy as Solving Linear Systems »
Yuxin Chen · Emmanuel Candes 
2014 Poster: A Differential Equation for Modeling Nesterovâ€™s Accelerated Gradient Method: Theory and Insights »
Weijie Su · Stephen Boyd · Emmanuel Candes 
2014 Spotlight: A Differential Equation for Modeling Nesterovâ€™s Accelerated Gradient Method: Theory and Insights »
Weijie Su · Stephen Boyd · Emmanuel Candes