On the condition number of a randomly perturbed matrix

12 March, 2007 in math.CO, math.PR, math.SP, paper | Tags: condition number, Littlewood-Offord theorems, random matrices | by Terence Tao

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.

10 comments

Comments feed for this article

14 March, 2007 at 11:08 am

There is an interesting (to some) random matrix problem that when scaled by sqrt{n} the empirical distribution of an n times n matrix A with i.i.d. complex valued entries with mean zero and unit variance, converges to uniform distribution on the unit disk (“Girko’s circular law” – the non-Hermitian analogue of Wigner’s semicircle law).
Bai has shown that the essential problem is to get a bound on the probability that (zI-A) has a small singular value(which has been done only under certain conditions on the distribution of the entries). A much weaker bound than the type that you have in this paper is needed. I wonder if your results don’t actually settle this problem?

15 March, 2007 at 9:53 am

Terence Tao

Dear MK, Thank you for the interesting suggestion, which we will look into! My co-author Van pointed out to me that there is some precedent for this type of connection: a recent paper by Gotze and Tikhomirov uses (modifications of) some earlier work of Rudelson on bounding the least singular value of random matrices to justify a circular law in certain cases. Our work does share many features in common with Rudelson’s work, including the treatment of various exceptional directions and the use of inverse Littlewood-Offord technology.

15 March, 2007 at 12:43 pm

van vu

Dear MK,

Thanks for pointing it out. I have a quick look at a recent paper of Gotze and Tikhomirov and it seemed that our result can be applied directly to zI-A, and so one can skip
lots of calculations there.

There was another paper of Girko that we could not comprehend, about central limit theorem for the determinant of a random matrix (where the entries can have very general distributions, not just gaussians). Have you seen that ?

15 March, 2007 at 11:08 pm

Gil Kalai

Dear all, There are many nice open problems around the random 0-1 matrices and connections to Sperner’s theorem and Littlewood-Offord. Here is one problem which might be the most bizarre:

let $p_n(k)$ be the probability that a random n by n 0-1 matrix has determinant equal to k. So $p_n(0)$ is exponentially small and $p_n(k)$ is probably even smaller when k is not zero. (maybe $n^{-Kn}$ , this is interesting but not yet bizarre)

The question is if $p_n(2)=o(p_n(1)).$

Here are two heuristics in favor and against it.

Heuristic 1: the determinant as a sum of n! signed random product clearly behave smoothly. OK, $p_n(0)$ is sort of a singular value, but you can expect that $p_n(i)$ will be similar to $p_n(j)$ when $i$ and $j$ are small (in absolute value) (even just $n^{o(n)}$ .) Certainly $p_1(n)$ and $p_2(n)$ are very close.

Apropos this. Jeff Kahn challenged to prove that for $\pm 1$ n by n matrices the permanent is zero with probability o(1). There you can also expect smoothness of the probabilities (beside that obvious parity condition.)

Heuristic 2: what is the probability that det = 0 (mod p) for a prime p? Well, 0-1 matrices should behave like random matrix mod p with entries 0,1,,…,p-1. But there the answer (denote it $s_p$ } is known:
it is this familiar infinite product. (Not too far from 1/p.)

The probability $r_p$ that a random such matrix has determinant 1 (mod p) is $(1-s_k)/(p-1)$ .

Next we can assume that the behavior is independent for different primes. So you get the prediction that the probability for 0-1 matrices that det = 1 differ by a constant from the probability that det = a power of 2.

And the probability that $\det = 2^k$ should perhaps be similar for different $k = o(n\log n)$ .

All in all $p_n(2)$ is smaller than $p_n(1)$ by a factor of n or $n\log n$ or so.

And by this strange heuristic if |j| is not too large, $p_n(j)$ depends on how many prime factors $j$ has.

Heuristic 2 is rather dubious but perhaps enough to shed some doubts.

16 March, 2007 at 5:51 am

vanvu

Dear Gil,

To me, Heuristic 2 looks like the situation with sieves in number theory. For very small
p, the independence look OK. But for relatively large p, it is quite wrong. If we do sieve the trivial way (before Brunn), the estimate was quite miserable.

16 March, 2007 at 2:11 pm

Dear Vu and Tao, Gotze and Tikhomirov apparently need Gaussian tails for the entries, so one point of interest would be to remove all such assumptions (Bai has a Lindeberg type condition to reduce the circular law problem to one of estimating smallest singular values and perhaps there should be no more assumptions on the entries at all?).
I do not know which paper of Girko you refer to, but his claimed proofs of circular law are incomplete as he skips over this issue of small singular values of ZI-A. There are also some other nonHermitian random matrix problems which were held up by this issue so far and should be accessible now (assuming there is no catch in extending your result to complex matrices).

16 March, 2007 at 4:10 pm

vanvu

Dear MK,

If I understand well, there is a standard machinery to reduce the CL to the problem of estimating the smallest singular value. If it is true, then what would be the most general assumption for which this machinery works ? (Then we just have to check whether our result still hold under that assumption; it is certainly hold for complex entries.)

Btw, can we know your full name ? (You can send private email to us if not want to disclose it here).

Thanks, Van Vu

17 March, 2007 at 10:21 am

Manjunath Krishnapur

The machinery for reducing CL to estimating small singular values is in Bai’s 1997 paper “Circular law” (Ann. Probab.) The recent book of Bai and Silverstein seems to say that the weakest known condition is (A is the $n \times n$ random matrix)

$n^{-2} \sum_{i,j} E[ |A_{ij}|^{2+s} ; |A_{ij}|>n^t ] \to 0$

for any t>0 and some s>0. (page 326, “Spectral analysis of large dimensional random matrices”).
And thanks for confirming that your theorems remain valid for complex matrices!

17 March, 2007 at 12:13 pm

Gil Kalai

Dear all. Thanks for your comment, Van. Sure, if Heuristic 2 can be improved a la Brunn this is even better. I suppose my question is whether the probability that an n by n matrix with entries 0/1 (or plus or minus one,) has determinant equal to k, depends in a strong way on the arithmetic of k. Heuristic 2 suggests that this IS the case and this is an appealing conjecture simply because it will be more interesting.

For matrices with entries plus or minus one I would expect the probability for the permanent to be equal to 2k behave very smoothly for k, like the probability of a length n! random walk from the origin landing in location 2k. But for determinants the heuristic will suggest a very different and nicer picture.

12 June, 2007 at 2:23 pm

STOC talk: The condition number of a randomly perturbed matrix « What’s new

[...] 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 [...]

	Terence Tao on From Bose-Einstein condensates…
	Terence Tao on Non-commutative Freiman theore…
	Bob Jerrard on From Bose-Einstein condensates…
	Ben Green on Non-commutative Freiman theore…
	Harald on Non-commutative Freiman theore…
	Ben Green on Non-commutative Freiman theore…
	liuxiaochuan on WordPress blocked again by gre…
	ioannis parissis on Random Martingales and localiz…
	Harald on Non-commutative Freiman theore…
	Harald on Non-commutative Freiman theore…
	Dave G on Random Martingales and localiz…
	Non-commutative Frei… on Freiman’s theorem for so…
	Non-commutative Frei… on (Ben Green) The Polynomial Fre…
	Non-commutative Frei… on Open question: noncommutative …
	Non-commutative Frei… on An elementary non-commutative …

On the condition number of a randomly perturbed matrix

Recent Comments

Articles by others

Diversions

Mathematics

Selected articles

The sciences

Top Posts

Archives

Categories

Tags

The Polymath Blog

Mathematics in Australia

10 comments

For commenters