BZPEERPapers, people, evidence and research pathsDiscover
Research tools
Network
Opportunities
Account
Source author record
Van Vu appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.
Catalog footprint
Research graph
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.
Published work
Classical anti-concentration results focus on the random sum $S := \sum _{i=1}^n ξ_i v_i$, where $ξ_i$ are independent random variables and $v_i$ are real numbers. In this paper, we prove new concentration results concerning the random sum $S := \sum_{i=1}^n w_{π_i } v_i $, where $w_i , v_i$ are real numbers and $π$ is a random permutation.
The Davis-Kahan-Wedin $\sin Θ$ theorem describes how the singular subspaces of a matrix change when subjected to a small perturbation. This classic result is sharp in the worst case scenario. In this paper, we prove a stochastic version of the Davis-Kahan-Wedin $\sin Θ$ theorem when the perturbation is a Gaussian random matrix. Under certain structural assumptions, we obtain an optimal bound that significantly improves upon the classic Davis-Kahan-Wedin $\sin Θ$ theorem. One of our key tools is a new perturbation bound for the singular values, which may be of independent interest.
Matrix perturbation inequalities, such as Weyl's theorem (concerning the singular values) and the Davis-Kahan theorem (concerning the singular vectors), play essential roles in quantitative science; in particular, these bounds have found application in data analysis as well as related areas of engineering and computer science. In many situations, the perturbation is assumed to be random, and the original matrix has certain structural properties (such as having low rank). We show that, in this scenario, classical perturbation results, such as Weyl and Davis-Kahan, can be improved significantly. We believe many of our new bounds are close to optimal and also discuss some applications.
Most of the existing chest X-ray datasets include labels from a list of findings without specifying their locations on the radiographs. This limits the development of machine learning algorithms for the detection and localization of chest abnormalities. In this work, we describe a dataset of more than 100,000 chest X-ray scans that were retrospectively collected from two major hospitals in Vietnam. Out of this raw data, we release 18,000 images that were manually annotated by a total of 17 experienced radiologists with 22 local labels of rectangles surrounding abnormalities and 6 global labels of suspected diseases. The released dataset is divided into a training set of 15,000 and a test set of 3,000. Each scan in the training set was independently labeled by 3 radiologists, while each scan in the test set was labeled by the consensus of 5 radiologists. We designed and built a labeling platform for DICOM images to facilitate these annotation procedures. All images are made publicly available (https://www.physionet.org/content/vindr-cxr/1.0.0/) in DICOM format along with the labels of both the training set and the test set.
A community of $n$ individuals splits into two camps, Red and Blue. The individuals are connected by a social network, which influences their colors. Everyday, each person changes his/her color according to the majority among his/her neighbors. Red (Blue) wins if everyone in the community becomes Red (Blue) at some point. We study this process when the underlying network is the random Erdos-Renyi graph $G(n, p)$. With a balanced initial state ($n/2$ person in each camp), it is clear that each color wins with the same probability. Our study reveals that for any constants $p$ and $\varepsilon$, there is a constant $C$ such that if one camp has $n/2 +C$ individuals, then it wins with probability at least $1 - \varepsilon$. The surprising key fact here is that $C$ does not depend on $n$, the population of the community. When $p=1/2$ and $\varepsilon =.1$, one can set $C$ as small as 6. If the aim of the process is to choose a candidate, then this means it takes only $6$ "defectors" to win an election unanimously with overwhelming odd.
We discuss recent progress many problems in random matrix theory of a combinatorial nature, including several breakthroughs that solve long standing famous conjectures.
Eigenvectors of large matrices (and graphs) play an essential role in combinatorics and theoretical computer science. The goal of this survey is to provide an up-to-date account on properties of eigenvectors when the matrix (or graph) is random.
We introduce a new procedure for generating the binomial random graph/hypergraph models, referred to as \emph{online sprinkling}. As an illustrative application of this method, we show that for any fixed integer $k\geq 3$, the binomial $k$-uniform random hypergraph $H^{k}_{n,p}$ contains $N:=(1-o(1))\binom{n-1}{k-1}p$ edge-disjoint perfect matchings, provided $p\geq \frac{\log^{C}n}{n^{k-1}}$, where $C:=C(k)$ is an integer depending only on $k$. Our result for $N$ is asymptotically best optimal and for $p$ is optimal up to the $polylog(n)$ factor.
The theory of random matrices contains many central limit theorems. We have central limit theorems for eigenvalues statistics, for the log-determinant and log-permanent, for limiting distribution of individual eigenvalues in the bulk, and many others. In this notes, we discuss the following problem: Is it possible to prove the law of the iterated logarithm? We illustrate this possibility by showing that this is indeed the case for the log of the permanent of random Bernoulli matrices and pose open questions concerning several other matrix parameters.
We discuss several questions concerning sum-free sets in groups, raised by Erdős in his survey "Extremal problems in number theory" (Proceedings of the Symp. Pure Math. VIII AMS) published in 1965. Among other things, we give a characterization for large sets $A$ in an abelian group $G$ which do not contain a subset $B$ of fixed size $k$ such that the sum of any two different elements of $B$ do not belong to $A$ (in other words, $B$ is sum-free with respect to $A$). Erdős, in the above mentioned survey, conjectured that if $|A|$ is sufficiently large compared to $k$, then $A$ contains two elements that add up to zero. This is known to be true for $k \leq 3$. We give counterexamples for all $k \ge 4$. On the other hand, using the new characterization result, we are able to prove a positive result in the case when $|G|$ is not divisible by small primes.
We prove anti-concentration results for polynomials of independent random variables with arbitrary degree. Our results extend the classical Littlewood-Offord result for linear polynomials, and improve several earlier estimates. We discuss applications in two different areas. In complexity theory, we prove near optimal lower bounds for computing the Parity, addressing a challenge in complexity theory posed by Razborov and Viola, and also address a problem concerning OR functions. In random graph theory, we derive a general anti-concentration result on the number of copies of a fixed graph in a random graph.
Let $A$ be an $n \times n$ matrix, $X$ be an $n \times p$ matrix and $Y = AX$. A challenging and important problem in data analysis, motivated by dictionary learning and other practical problems, is to recover both $A$ and $X$, given $Y$. Under normal circumstances, it is clear that this problem is underdetermined. However, in the case when $X$ is sparse and random, Spielman, Wang and Wright showed that one can recover both $A$ and $X$ efficiently from $Y$ with high probability, given that $p$ (the number of samples) is sufficiently large. Their method works for $p \ge C n^2 \log^ 2 n$ and they conjectured that $p \ge C n \log n$ suffices. The bound $n \log n$ is sharp for an obvious information theoretical reason. In this paper, we show that $p \ge C n \log^4 n$ suffices, matching the conjectural bound up to a polylogarithmic factor. The core of our proof is a theorem concerning $l_1$ concentration of random matrices, which is of independent interest. Our proof of the concentration result is based on two ideas. The first is an economical way to apply the union bound. The second is a refined version of Bernstein's concentration inequality for the sum of independent variables. Both have nothing to do with random matrices and are applicable in general settings.
For fixed $m > 1$, we study the product of $m$ independent $N \times N$ elliptic random matrices as $N$ tends to infinity. Our main result shows that the empirical spectral distribution of the product converges, with probability $1$, to the $m$-th power of the circular law, regardless of the joint distribution of the mirror entries in each matrix. This leads to a new kind of universality phenomenon: the limit law for the product of independent random matrices is independent of the limit laws for the individual matrices themselves. Our result also generalizes earlier results of Götze-Tikhomirov and O'Rourke-Soshnikov concerning the product of independent iid random matrices.
Gaps (or spacings) between consecutive eigenvalues are a central topic in random matrix theory. The goal of this paper is to study the tail distribution of these gaps in various random matrix models. We give the first repulsion bound for random matrices with discrete entries and the first super-polynomial bound on the probability that a random graph has simple spectrum, along with several applications.
In this paper, we present and analyze a simple and robust spectral algorithm for the stochastic block model with $k$ blocks, for any $k$ fixed. Our algorithm works with graphs having constant edge density, under an optimal condition on the gap between the density inside a block and the density between the blocks. As a co-product, we settle an open question posed by Abbe et. al. concerning censor block models.
Finding a hidden partition in a random environment is a general and important problem, which contains as subproblems many famous questions, such as finding a hidden clique, finding a hidden coloring, finding a hidden bipartition etc. In this paper, we provide a simple SVD algorithm for this purpose, answering a question of McSherry. This algorithm is very easy to implement and works for sparse graphs with optimal density.
In this paper, we establish some local universality results concerning the correlation functions of the zeroes of random polynomials with independent coefficients. More precisely, consider two random polynomials $f =\sum_{i=1}^n c_i ξ_i z^i$ and $\tilde f =\sum_{i=1}^n c_i \tilde ξ_i z^i$, where the $ξ_i$ and $\tilde ξ_i$ are iid random variables that match moments to second order, the coefficients $c_i$ are deterministic, and the degree parameter $n$ is large. Our results show, under some light conditions on the coefficients $c_i$ and the tails of $ξ_i, \tilde ξ_i$, that the correlation functions of the zeroes of $f$ and $\tilde f$ are approximately the same. As an application, we give some answers to the classical question `"How many zeroes of a random polynomials are real?" for several classes of random polynomial models. Our analysis relies on a general replacement principle, motivated by some recent work in random matrix theory. This principle enables one to compare the correlation functions of two random functions $f$ and $\tilde f$ if their log magnitudes $\log |f|, \log|\tilde f|$ are close in distribution, and if some non-concentration bounds are obeyed.
Roots of random polynomials have been studied exclusively in both analysis and probability for a long time. A famous result by Ibragimov and Maslova, generalizing earlier fundamental works of Kac and Erdos-Offord, showed that the expectation of the number of real roots is $\frac{2}π \log n + o(\log n)$. In this paper, we determine the true nature of the error term by showing that the expectation equals $\frac{2}π\log n + O(1)$. Prior to this paper, such estimate has been known only in the gaussian case, thanks to works of Edelman and Kostlan.
Let $M_n = (ξ_{ij})_{1 \leq i,j \leq n}$ be a real symmetric random matrix in which the upper-triangular entries $ξ_{ij}, i<j$ and diagonal entries $ξ_{ii}$ are independent. We show that with probability tending to 1, $M_n$ has no repeated eigenvalues. As a corollary, we deduce that the Erd{\H o}s-Renyi random graph has simple spectrum asymptotically almost surely, answering a question of Babai.
Let $A_n$ be an $n$ by $n$ random matrix whose entries are independent real random variables with mean zero, variance one and with subexponential tail. We show that the logarithm of $|\det A_n|$ satisfies a central limit theorem. More precisely, \begin{eqnarray*}\sup_{x\in {\mathbf {R}}}\biggl|{\mathbf {P}}\biggl(\frac{\log(|\det A_n|)-({1}/{2})\log (n-1)!}{\sqrt{({1}/{2})\log n}}\le x\biggr)-{\mathbf {P}}\bigl(\mathbf {N}(0,1)\le x\bigr)\biggr|\\\qquad\le\log^{-{1}/{3}+o(1)}n.\end{eqnarray*}
As an extension of Polya's classical result on random walks on the square grids ($\Z^d$), we consider a random walk where the steps, while still have unit length, point to different directions. We show that in dimensions at least 4, the returning probability after $n$ steps is at most $n^{-d/2 - d/(d-2) +o(1)}$, which is sharp. The real surprise is in dimensions 2 and 3. In dimension 2, where the traditional grid walk is recurrent, our upper bound is $n^{-ω(1)}$, which is much worse than higher dimensions. In dimension 3, we prove an upper bound of order $n^{-4 +o(1)}$. We discover a new conjecture concerning incidences between spheres and points in $\R^3$, which, if holds, would improve the bound to $n^{-9/2 +o(1)}$, which is consistent % with the $d \ge 4$ case. to the $d \ge 4$ case. This conjecture resembles Szemerédi-Trotter type results and is of independent interest.
We present a concentration result concerning random weighted projections in high dimensional spaces. As applications, we prove (1) New concentration inequalities for random quadratic forms; (2) The infinity norm of most unit eigenvectors of a random $\pm 1$ matrix is of order $O( \sqrt { \log n/n})$; (3) An estimate on the threshold for the local semi-circle law which is tight up to a $\sqrt {\log n}$ factor.
Consider a random matrix of the form $W_n = M_n + D_n$, where $M_n$ is a Wigner matrix and $D_n$ is a real deterministic diagonal matrix ($D_n$ is commonly referred to as an external source in the mathematical physics literature). We study the universality of the local eigenvalue statistics of $W_n$ for a general class of Wigner matrices $M_n$ and diagonal matrices $D_n$. Unlike the setting of many recent results concerning universality, the global semicircle law fails for this model. However, we can still obtain the universal sine kernel formula for the correlation functions. This demonstrates the remarkable phenomenon that local laws are more resilient than global ones. The universality of the correlation functions follows from a four moment theorem, which we prove using a variant of the approach used earlier by Tao and Vu.
Let $W_n= \frac{1}{\sqrt n} M_n$ be a Wigner matrix whose entries have vanishing third moment, normalized so that the spectrum is concentrated in the interval $[-2,2]$. We prove a concentration bound for $N_I = N_I(W_n)$, the number of eigenvalues of $W_n$ in an interval $I$. Our result shows that $N_I$ decays exponentially with standard deviation at most $O(\log^{O(1)} n)$. This is best possible up to the constant exponent in the logarithmic term. As a corollary, the bulk eigenvalues are localized to an interval of width $O(\log^{O(1)} n/n)$; again, this is optimal up to the exponent. These results strengthen recent results of Erdos, Yau and Yin (under the extra assumption of vanishing third
We consider random matrices whose entries are f(<Xi,Xj>) or f(||Xi-Xj||^2) for iid vectors Xi in R^p with normalized distribution. Assuming that f is sufficiently smooth and the distribution of Xi's is sufficiently nice, El Karoui [17] showed that the spectral distributions of these matrices behave as if f is linear in the Marchenko--Pastur limit. When Xi's are Gaussian vectors, variants of this phenomenon were recently proved for varying kernels, i.e. when f may depend on p, by Cheng and Singer [13]. Two results are shown in this paper: first it is shown that for a large class of distributions the regularity assumptions on f in El Karoui's results can be reduced to minimal; and secondly it is shown that the Gaussian assumptions in Cheng--Singer's result can be removed, answering a question posed in [13] about the universality of the limiting spectral distribution.
We establish a central limit theorem for the log-determinant $\log|\det(M_n)|$ of a Wigner matrix $M_n$, under the assumption of four matching moments with either the GUE or GOE ensemble. More specifically, we show that this log-determinant is asymptotically distributed like $N(\log \sqrt{n!} - 1/2 \log n, 1/2 \log n)_\R$ when one matches moments with GUE, and $N(\log \sqrt{n!} - 1/4 \log n, 1/4 \log n)_\R$ when one matches moments with GOE.
Let $M_n$ be a random matrix of size $n\times n$ and let $λ_1,...,λ_n$ be the eigenvalues of $M_n$. The empirical spectral distribution $μ_{M_n}$ of $M_n$ is defined as $$μ_{M_n}(s,t)=\frac{1}{n}# \{k\le n, \Re(λ_k)\le s; \Im(λ_k)\le t\}.$$ The circular law theorem in random matrix theory asserts that if the entries of $M_n$ are i.i.d. copies of a random variable with mean zero and variance $σ^2$, then the empirical spectral distribution of the normalized matrix $\frac{1}{σ\sqrt{n}}M_n$ of $M_n$ converges almost surely to the uniform distribution $μ_\cir$ over the unit disk as $n$ tends to infinity. In this paper we show that the empirical spectral distribution of the normalized matrix of $M_n$, a random matrix whose rows are independent random $(-1,1)$ vectors of given row-sum $s$ with some fixed integer $s$ satisfying $|s|\le (1-o(1))n$, also obeys the circular law. The key ingredient is a new polynomial estimate on the least singular value of $M_n$.
We study the eigenvalues of the covariance matrix $\frac{1}{n}M^*M$ of a large rectangular matrix $M=M_{n,p}=(ζ_{ij})_{1\leq i\leq p;1\leq j\leq n}$ whose entries are i.i.d. random variables of mean zero, variance one, and having finite $C_0$th moment for some sufficiently large constant $C_0$. The main result of this paper is a Four Moment theorem for i.i.d. covariance matrices (analogous to the Four Moment theorem for Wigner matrices established by the authors in [Acta Math. (2011) Random matrices: Universality of local eigenvalue statistics] (see also [Comm. Math. Phys. 298 (2010) 549--572])). We can use this theorem together with existing results to establish universality of local statistics of eigenvalues under mild conditions. As a byproduct of our arguments, we also extend our previous results on random Hermitian matrices to the case in which the entries have finite $C_0$th moment rather than exponential decay.
In this paper, we survey some recent progress on rigorously establishing the universality of various spectral statistics of Wigner Hermitian random matrix ensembles, focusing on the Four Moment Theorem and its refinements and applications, including the universality of the sine kernel and the Central limit theorem of several spectral parameters. We also take the opportunity here to issue some errata for some of our previous papers in this area.
A sequence $A$ of elements an additive group $G$ is {\it incomplete} if there exists a group element that {\it can not} be expressed as a sum of elements from $A$. The study of incomplete sequences is a popular topic in combinatorial number theory. However, the structure of incomplete sequences is still far from being understood, even in basic groups. The main goal of this paper is to give a characterization of incomplete sequences in the vector space $F_p^d$, where $d$ is a fixed integer and $p$ is a large prime. As an application, we give a new proof for a recent result by Gao-Ruzsa-Thangadurai on the Olson's constant of $\F_p^2$ and partially answer their conjecture concerning $F_p^3$.
The purpose of this note is to establish a Central Limit Theorem for the number of eigenvalues of a Wigner matrix in an interval. The proof relies on the correct aymptotics of the variance of the eigenvalue counting function of GUE matrices due to Gustavsson, and its extension to large families of Wigner matrices by means of the Tao and Vu Four Moment Theorem and recent localization results by Erdös, Yau and Yin.
Let eta_i be iid Bernoulli random variables, taking values -1,1 with probability 1/2. Given a multiset V of n integers v_1,..., v_n, we define the concentration probability as rho(V) := sup_{x} Pr(v_1 eta_1+...+ v_n eta_n=x). A classical result of Littlewood-Offord and Erdos from the 1940s asserts that if the v_i are non-zero, then rho(V) is O(n^{-1/2}). Since then, many researchers obtained improved bounds by assuming various extra restrictions on V. About 5 years ago, motivated by problems concerning random matrices, Tao and Vu introduced the Inverse Littlewood-Offord problem. In the inverse problem, one would like to give a characterization of the set V, given that rho(V) is relatively large. In this paper, we introduce a new method to attack the inverse problem. As an application, we strengthen a previous result of Tao and Vu, obtaining an optimal characterization for V. This immediately implies several classical theorems, such as those of Sarkozy-Szemeredi and Halasz. The method also applies in the continuous setting and leads to a simple proof for the beta-net theorem of Tao and Vu, which plays a key role in their recent studies of random matrices. All results extend to the general case when V is a subset of an abelian torsion-free group and eta_i are independent variables satisfying some weak conditions.
Consider the eigenvalues $λ_i(M_n)$ (in increasing order) of a random Hermitian matrix $M_n$ whose upper-triangular entries are independent with mean zero and variance one, and are exponentially decaying. By Wigner's semicircular law, one expects that $λ_i(M_n)$ concentrates around $γ_i \sqrt n$, where $\int_{-\infty}^{γ_i} ρ_{sc} (x) dx = \frac{i}{n}$ and $ρ_{sc}$ is the semicircular function. In this paper, we show that if the entries have vanishing third moment, then for all $1\le i \le n$ $$\E |λ_i(M_n)-\sqrt{n} γ_i|^2 = O(\min(n^{-c} \min(i,n+1-i)^{-2/3} n^{2/3}, n^{1/3+\eps})) ,$$ for some absolute constant $c>0$ and any absolute constant $\eps>0$. In particular, for the eigenvalues in the bulk ($\min \{i, n-i\}=Θ(n)$), $$\E |λ_i(M_n)-\sqrt{n} γ_i|^2 = O(n^{-c}). $$ \noindent A similar result is achieved for the rate of convergence. As a corollary, we show that the four moment condition in the Four Moment Theorem is necessary, in the sense that if one allows the fourth moment to change (while keeping the first three moments fixed), then the \emph{mean} of $λ_i(M_n)$ changes by an amount comparable to $n^{-1/2}$ on the average. We make a precise conjecture about how the expectation of the eigenvalues vary with the fourth moment.
We survey some recent progress on rigorously establishing the universality of various spectral statistics of Wigner random matrix ensembles, focusing in particular on the Four Moment Theorem and its applications.
The four moment theorem asserts, roughly speaking, that the joint distribution of a small number of eigenvalues of a Wigner random matrix (when measured at the scale of the mean eigenvalue spacing) depends only on the first four moments of the entries of the matrix. In this paper, we extend the four moment theorem to also cover the coefficients of the \emph{eigenvectors} of a Wigner random matrix. A similar result (with different hypotheses) has been proved recently by Knowles and Yin, using a different method. As an application, we prove some central limit theorems for these eigenvectors. In another application, we prove a universality result for the resolvent, up to the real axis. This implies universality of the inverse matrix.
We give a new bound on the probability that the random sum $ξ_1 v_1 +...+ ξ_n v_n$ belongs to a ball of fixed radius, where the $ξ_i$ are iid Bernoulli random variables and the $v_i$ are vectors in $\R^d$. As an application, we prove a conjecture of Frankl and Füredi (raised in 1988), which can be seen as the high dimensional version of the classical Littlewood-Offord-Erd\H os theorem.
A well known conjecture of Wigner, Dyson, and Mehta asserts that the (appropriately normalized) $k$-point correlation functions of the eigenvalues of random $n \times n$ Wigner matrices in the bulk of the spectrum converge (in various senses) to the $k$-point correlation function of the Dyson sine process in the asymptotic limit $n \to \infty$. There has been much recent progress on this conjecture, in particular it has been established under a wide variety of decay, regularity, and moment hypotheses on the underlying atom distribution of the Wigner ensemble, and using various notions of convergence. Building upon these previous results, we establish new instances of this conjecture with weaker hypotheses on the atom distribution and stronger notions of convergence. In particular, assuming only a finite moment condition on the atom distribution, we can obtain convergence in the vague sense, and assuming an additional regularity condition, we can upgrade this convergence to locally $L^1$ convergence.
We consider the ensemble of $n \times n$ Wigner hermitian matrices $H = (h_{\ell k})_{1 \leq \ell,k \leq n}$ that generalize the Gaussian unitary ensemble (GUE). The matrix elements $h_{k\ell} = \bar h_{\ell k}$ are given by $h_{\ell k} = n^{-1/2} (x_{\ell k} + \sqrt{-1} y_{\ell k})$, where $x_{\ell k}, y_{\ell k}$ for $1 \leq \ell < k \leq n$ are i.i.d. random variables with mean zero and variance 1/2, $y_{\ell\ell}=0$ and $x_{\ell \ell}$ have mean zero and variance 1. We assume the distribution of $x_{\ell k}, y_{\ell k}$ to have subexponential decay. In a recent paper, four of the authors recently established that the gap distribution and averaged $k$-point correlation of these matrices were \emph{universal} (and in particular, agreed with those for GUE) assuming additional regularity hypotheses on the $x_{\ell k}, y_{\ell k}$. In another recent paper, the other two authors, using a different method, established the same conclusion assuming instead some moment and support conditions on the $x_{\ell k}, y_{\ell k}$. In this short note we observe that the arguments of these two papers can be combined to establish universality of the gap distribution and averaged $k$-point correlations for all Wigner matrices (with subexponentially decaying entries), with no extra assumptions.
In this paper, we consider the universality of the local eigenvalue statistics of random matrices. Our main result shows that these statistics are determined by the first four moments of the distribution of the entries. As a consequence, we derive the universality of eigenvalue gap distribution and $k$-point correlation and many other statistics (under some mild assumptions) for both Wigner Hermitian matrices and Wigner real symmetric matrices.
This is a continuation of our earlier paper on the universality of the eigenvalues of Wigner random matrices. The main new results of this paper are an extension of the results in that paper from the bulk of the spectrum up to the edge. In particular, we prove a variant of the universality results of Soshnikov for the largest eigenvalues, assuming moment conditions rather than symmetry conditions. The main new technical observation is that there is a significant bias in the Cauchy interlacing law near the edge of the spectrum which allows one to continue ensuring the delocalization of eigenvectors.
Computing the first few singular vectors of a large matrix is a problem that frequently comes up in statistics and numerical analysis. Given the presence of noise, exact calculation is hard to achieve, and the following problem is of importance: \vskip2mm \centerline {\it How much a small perturbation to the matrix changes the singular vectors ?} \vskip2mm Answering this question, classical theorems, such as those of Davis-Kahan and Wedin, give tight estimates for the worst-case scenario. In this paper, we show that if the perturbation (noise) is random and our matrix has low rank, then better estimates can be obtained. Our method relies on high dimensional geometry and is different from those used an earlier papers.
In this paper we prove the semi-circular law for the eigenvalues of regular random graph $G_{n,d}$ in the case $d\rightarrow \infty$, complementing a previous result of McKay for fixed $d$. We also obtain a upper bound on the infinity norm of eigenvectors of Erdős-Rényi random graph $G(n,p)$, answering a question raised by Dekel-Lee-Linial.
We show that the absolute value of the determinant of a matrix with random independent (but not necessarily iid) entries is strongly concentrated around its mean. As an application, we show that the Godsil-Gutman and Barvinok estimators for the permanent of a strictly positive matrix give sub-exponential approximation ratios with high probability.