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.

The effect of errors in variables in nonparametric regression estimation is examined. To account for errors in covariates, deconvolution is involved in the construction of a new class of kernel estimators. It is shown that optimal local and global rates of convergence of these kernel estimators can be characterized by the tail behavior of the characteristic function of the error distribution. In fact, there are two types of rates of convergence according to whether the error is ordinary smooth or super smooth. It is also shown that these results hold uniformly over a class of joint distributions of the response and the covariate, which is rich enough for many practical applications. Furthermore, to achieve optimality, we show that the convergence rates of all possible estimators have a lower bound possessed by the kernel estimators.

A practical and accessible introduction to the bootstrap methodnewly revised and updated Over the past decade, the application of bootstrap methods to new areas of study has expanded, resulting in theoretical and applied advances across various fields. Bootstrap Methods, Second Edition is a highly approachable guide to the multidisciplinary, real-world uses of bootstrapping and is ideal for readers who have a professional interest in its methods, but are without an advanced background in mathematics. Updated to reflect current techniques and the most up-to-date work on the topic, the Second Edition features: The addition of a second, extended bibliography devoted solely to publications from 19992007, which is a valuable collection of references on the latest research in the field A discussion of the new areas of applicability for bootstrap methods, including use in the pharmaceutical industry for estimating individual and population bioequivalence in clinical trials A revised chapter on when and why bootstrap fails and remedies for overcoming these drawbacks Added coverage on regression, censored data applications, P-value adjustment, ratio estimators, and missing data New examples and illustrations as well as extensive historical notes at the end of each chapter With a strong focus on application, detailed explanations of methodology, and complete coverage of modern developments in the field, Bootstrap Methods, Second Edition is an indispensable reference for applied statisticians, engineers, scientists, clinicians, and other practitioners who regularly use statistical methods in research. It is also suitable as a supplementary text

No abstract uploaded!

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.