BEGIN:VCALENDAR VERSION:2.0 PRODID:researchseminars.org CALSCALE:GREGORIAN X-WR-CALNAME:researchseminars.org BEGIN:VEVENT SUMMARY:Yuxin Chen (Princeton University) DTSTART:20201228T030000Z DTEND:20201228T034500Z DTSTAMP:20260423T023932Z UID:iccm2020/42 DESCRIPTION:Title: Solving Random Quadratic Systems of Equations Is Nearly as Easy as Solvi ng Linear Systems\nby Yuxin Chen (Princeton University) as part of ICC M 2020\n\n\nAbstract\nThis talk considers the fundamental problem of solvi ng quadratic systems of equations in n variables. We propose a novel metho d\, which starting with an initial guess computed by means of a spectral m ethod\, proceeds by minimizing a nonconvex functional as in the Wirtinger flow approach. There are several key distinguishing features\, most notabl y\, a distinct objective functional and novel update rules\, which operate in an adaptive fashion and drop terms bearing too much influence on the s earch direction. These careful selection rules provide a tighter initial g uess\, better descent directions\, and thus enhanced practical performance . On the theoretical side\, we prove that for certain unstructured models of quadratic systems\, our algorithms return the correct solution in linea r time\, i.e. in time proportional to reading the data as soon as the rati o between the number of equations and unknowns exceeds a fixed numerical c onstant. We extend the theory to deal with noisy systems and prove that ou r algorithms achieve a statistical accuracy\, which is nearly un-improvabl e. We complement our theoretical study with numerical examples showing tha t solving random quadratic systems is both computationally and statistical ly not much harder than solving linear systems of the same size---hence th e title of this work. For instance\, we demonstrate empirically that the c omputational cost of our algorithm is about four times that of solving a l east-squares problem of the same size.\n LOCATION:https://researchseminars.org/talk/iccm2020/42/ END:VEVENT END:VCALENDAR