Return to Colloquia & Seminar listing
Invertibility of random matricesMathematical Physics & Probability
|Speaker: ||Roman Vershynin, UC Davis|
|Location: ||1147 MSB|
|Start time: ||Wed, Oct 3 2007, 4:10PM|
While developing algorithms for the first computers, Von Neumann and
Goldstine discovered problems with ill-conditioned inputs. Matrix
inversion algorithms break down for matrices with big condition number,
which is the ratio of the largest to the smallest singular values. They
then experimented with large square matrices with random i.i.d. entries,
and came to the conclusion that the condition number of random matrices
should be linear in the dimension.
Von Neumann-Goldstine's prediction and its refinement by Smale was proved
only for Gaussian matrices by Edelman in 1985. The simplest unsolved case
has been for Bernoulli matrices, whose entries are 1 or -1 with equal
probability. I will describe a recent solution of Von Neumann-Golstine
conjecture. It holds for all random matrices whose independent entries
have bounded fourth moment.
One new probabilistic ingredient in this work is a development of
Littlewood-Offord theory of anti-concentration inequalities. I will
describe its connections with ergodic theory and additive combinatorics.
This is a joint work with Mark Rudelson.