No abstract uploaded!

No abstract uploaded!

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.

Community detection is a fundamental problem in social network analysis. It is desirable to have fast community detection algorithm that applicable to large-scale networks we see today and also have reliable community detection results. This paper proposes Spectral Clustering On Ratios-of-eigenvectors (SCORE) as such an algorithm. The algorithm is fast in computation, is applicable to real large networks, and is competitive in real data performance when applied to some representative data sets in this area. We study the algorithm with the Degree-Corrected Block Model (DCBM). Compare to most works in this area that focus on the much narrower Block Models, our analysis is more difficult and requires new techniques. The novelty of our algorithm lies in that it uses entry-wise ratios between leading eigenvectors of the adjacency to reduce a seemingly hard problem to a problem that is very much tractable.

Let $(X,\alpha)$ be a K\"ahler manifold of dimension $n$, and let $[\omega] \in H^{1,1}(X,\mathbb{R})$. We study the problem of specifying the Lagrangian phase of $\omega$ with respect to $\alpha$, which is described by the nonlinear elliptic equation \[ \sum_{i=1}^{n} \arctan(\la_i)= h(x) \] where $\la_i$ are the eigenvalues of $\omega$ with respect to $\alpha$. When $h(x)$ is a topological constant, this equation corresponds to the deformed Hermitian-Yang-Mills (dHYM) equation, and is related by Mirror Symmetry to the existence of special Lagrangian submanifolds of the mirror. We introduce a notion of subsolution for this equation, and prove a priori $C^{2,\beta}$ estimates when $|h|>(n-2)\frac{\pi}{2}$ and a subsolution exists. Using the method of continuity we show that the dHYM equation admits a smooth solution in the supercritical phase case, whenever a subsolution exists. Finally, we discover some stability-type cohomological obstructions to the existence of solutions to the dHYM equation and we conjecture that when these obstructions vanish the dHYM equation admits a solution. We confirm this conjecture for complex surfaces.