We consider the fundamental problem of solving quadratic systems of m equations in n variables. We propose a novel method, which starting with an initial guess computed by means of a spectral method, proceeds by minimizing a nonconvex functional as in the Wirtinger flow approach. There are several key distinguishing features, most notably, a distinct objective functional and novel update rules, which operate in an adaptive fashion and drop terms bearing too much influence on the search direction. These careful selection rules provide a tighter initial guess, 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 linear time, i.e. in time proportional to reading the data and as soon as the ratio m/n between the number of equations and unknowns exceeds a fixed numerical constant. We extend the theory to deal with noisy systems and prove that our algorithms achieve a statistical accuracy, which is nearly un-improvable. We complement our theoretical study with numerical examples showing that solving random quadratic systems is both computationally and statistically not much harder than solving linear systems of the same size---hence the title of this paper. For instance, 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.

A foliation F on a Riemannian manifold M is hyperpolar if it admits a flat section, that is, a connected closed flat submanifold of M that intersects each leaf of F orthogonally. In this article we classify the hyperpolar homogeneous foliations on every Riemannian symmetric space M of noncompact type. These foliations are constructed as follows. Let  be an orthogonal subset of a set of simple roots associated with the symmetric space M. Then  determines a horospherical decomposition M = Fs ×ErankM−||×N, where Fs  is the Riemannian product of || symmetric spaces of rank one. Every hyperpolar homogeneous foliation on M is isometrically congruent to the product of the following objects: a particular homogeneous codimension one foliation on each symmetric space of rank one in Fs , a foliation by parallel affine subspaces on the Euclidean space ErankM−||, and the horocycle subgroup N of the parabolic subgroup of the isometry group of M determined by .

We describe a notion of ampleness for line bundles on orbifolds with cyclic quotient singularities that is related to embeddings in weighted projective space, and prove a global asymptotic expansion for a weighted Bergman kernel associated to such a line bundle.

No abstract uploaded!

No abstract uploaded!