This event has ended. View the official site or create your own event → Check it out
This event has ended. Create your own
View analytic
Tuesday, December 8 • 10:55 - 11:35
Solving Random Quadratic Systems of Equations Is Nearly as Easy as Solving Linear Systems

Sign up or log in to save this to your schedule and see who's attending!

This paper is concerned with finding a solution x to a quadratic system of equations y_i = |< a_i, 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 non-convex 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 rules---which effectively serve as a variance reduction scheme---provide a tighter initial guess, more robust descent directions, and thus enhanced practical performance. Further, this procedure also achieves a near-optimal 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 least-squares problem of the same size.

Tuesday December 8, 2015 10:55 - 11:35
Room 210 A

Attendees (5)