You are currently browsing the tag archive for the ‘condition number’ tag.

This is my second Milliman lecture, in which I talk about recent applications of ideas from additive combinatorics (and in particular, from the inverse Littlewood-Offord problem) to the theory of discrete random matrices.
Read the rest of this entry »

Van Vu and I have recently uploaded our joint paper, “Random matrices: the circular law“, submitted to Contributions to Discrete Mathematics. In this paper we come close to fully resolving the circular law conjecture regarding the eigenvalue distribution of random matrices, for arbitrary choices of coefficient distribution.

More precisely, suppose we have an $n \times n$ matrix $N_n$ for some large n, where each coefficient $x_{ij}$ of $N_n$ is an independent identically distributed copy of a single random variable x (possibly complex-valued). x could be continuous (e.g. a Gaussian) or discrete (e.g. a Bernoulli random variable, taking values +1 and -1 with equal probability). For simplicity, let us normalise x to have mean 0 and variance 1 (in particular, the second moment is finite). This matrix will not be self-adjoint or normal, but we still expect it to be diagonalisable, with n complex eigenvalues. Heuristic arguments suggest that these eigenvalues should mostly have magnitude $O(\sqrt{n})$; for instance, one can see this by observing that the Hilbert-Schmidt norm (a.k.a. the Frobenius norm) $\hbox{tr} N_n^* N_n$, which can be shown to dominate the sum of squares of the magnitudes of the eigenvalues, is of size comparable to $n^2$ on the average. Because of this, it is customary to normalise the matrix by $1/\sqrt{n}$; thus let $\lambda_1,\ldots,\lambda_n$ be the n complex eigenvalues of $\frac{1}{\sqrt{n}} N_n$, arranged in any order.

Numerical evidence (as seen for instance here) soon reveals that these n eigenvalues appear to distribute themselves uniformly in the unit circle $\{ z \in {\Bbb C}: |z| \leq 1 \}$ in the limit $n \to \infty$. This phenomenon is known as the circular law. It can be made more precise; if we define the empirical spectral distribution $\mu_n: {\Bbb R}^2 \to [0,1]$ to be the function

$\mu_n(s,t) := \frac{1}{n} \# \{ 1 \leq k \leq n: \hbox{Re}(\lambda_k) \leq s; \hbox{Im}(\lambda_k) \leq t \}$

then with probability 1, $\mu_n$ should converge uniformly to the uniform distribution $\mu_\infty$ of the unit circle, defined as

$\mu_\infty(s,t) := \frac{1}{\pi} \hbox{mes}(\{ (x,y): |x|^2 + |y|^2 \leq 1; x \leq s; y \leq t \}.$

This statement is known as the circular law conjecture. In the case when x is a complex Gaussian, this law was verified by Mehta (using an explicit formula of Ginibre for the joint density function of the eigenvalues in this case). A strategy for attacking the general case was then formulated by Girko, although a fully rigorous execution of that strategy was first achieved by Bai (and then improved slightly by Bai and Silverstein). They established the circular law under the assumption that x had slightly better than bounded second moment (i.e. ${\Bbb E}|x|^{2+\delta} < \infty$ for some $\delta > 0$), but more importantly that the probability density function of x in the complex plane was bounded (in particular, this ruled out all discrete random variables, such as the Bernoulli random variable). The reason for this latter restriction was in order to control the event that the matrix $N_n$ (or more precisely $\frac{1}{\sqrt{n}} N_n - z I$ for various complex numbers z) becomes too ill-conditioned by having a very small least singular value.

In the last few years, work of Rudelson, of myself with Van Vu, and of Rudelson-Vershynin (building upon earlier work of Kahn, Komlos, and Szemerédi, and of Van and myself), have opened the way to control the condition number of random matrices even when the matrices are discrete, and so there have been a recent string of results using these techniques to extend the circular law to discrete settings. In particular, Gotze and Tikhomirov established the circular law for discrete random variables which were sub-Gaussian, which was then relaxed by Pan and Zhou to an assumption of bounded fourth moment. In our paper, we get very close to the ideal assumption of bounded second moment; we need ${\Bbb E} |x|^2 \log^C(1+|x|) < \infty$ for some $C > 16$. (The power of 16 in the logarithm can certainly be improved, though our methods do not allow the logarithm to be removed entirely.)

The main new difficulty that arises when relaxing the moment condition so close to the optimal one is that one begins to lose control on the largest singular value of $\frac{1}{\sqrt{n}} N_n$, i.e. on the operator norm of $\frac{1}{\sqrt{n}} N_n$. Under high moment assumptions (e.g. fourth moment) one can keep this operator norm bounded with reasonable probability (especially after truncating away some exceptionally large elements), but when the moment conditions are loosened, one can only bound this operator norm by a quantity bounded polynomially in n, even after truncation. This in turn causes certain metric entropy computations to become significantly more delicate, as one has to reduce the scale $\epsilon$ of the net below what one would ordinarily like to have.

This week I am in San Diego for the 39th ACM Symposium for the Theory of Computing (STOC). Today I presented my work with Van Vu on the condition number of randomly perturbed matrices, which was the subject of an earlier post on this blog. For this short talk (20 minutes), Van and I prepared some slides; of course, in such a short time frame one cannot hope to discuss many of the details of the result, but one can at least convey the statement of the result and a brief sketch of the main ideas in the proof.

One late update (which didn’t make it onto the slides): last week, an alternate proof of some cases of our main result (together with some further generalisations and other results, in particular a circular law for the eigenvalues of discrete random matrices) was obtained by Pan and Zhou, using earlier arguments by Rudelson and Vershynin.

[Update, June 16: It was pointed out to me that the Pan-Zhou result only recovers our result in the case when the unperturbed matrix has a spectral norm of $O(n^{1/2})$ (our result assumes that the unperturbed matrix has polynomial size). Slides also updated.]

I’ve arXived the paper “On the condition number of a randomly perturbed matrix”, authored with Van Vu, which will appear at STOC 2007. (This paper was actually finished and submitted several months ago, but for some reason I neglected to upload it to the arXiv until now.) Here we show that given an arbitrary $n \times n$ matrix M with polynomially bounded entries (in particular, M could be highly singular), a random discrete perturbation M+N, where N is (say) a random Bernoulli $\pm 1$ matrix, will have polynomially bounded condition number with high probability (specifically, given any A there exists a B such that the condition number is $O(n^B)$ with probability $1-O(n^{-A})$). This is the discrete analogue of an analogous result by Spielman and Teng for continuous random perturbations. The proof uses the inverse Littlewood-Offord technology as well as a discretisation lemma for generalized arithmetic progressions, both from our previous paper (which essentially addressed the M=0 case). It turns out that the effect of M is essentially just to add a few deterministic rows to a random matrix which one needs to obtain lower bounds for the least singular value.