|
Applied Math Seminar
Condition numbers of random matrices
|
|
For many numerical algorithms (e.g. for all known Linear Programming solvers) , their running time unfortunately depends not only on the size of the input, but also on how non-degenerate the input is. The non-degeneracy is usually measured with the condition number. Smale put forward a program to estimate the condition numbers of random inputs, and thus to control the complexity of numerical algorithms on most (=random) inputs. For matrix inputs, the condition number is the ratio of the largest to the smallest singular values. Spielman and Teng conjectured that the condition number of a random Bernoulii matrix (i.e. whose entries are +1, -1 independently with probability 1/2) is O(n) with high probability. Recently, Rudelson and later the author announced two independent positive solutions to this conjecture. The argument is based on a new small ball probability estimate of independent interest. Given numbers a_1, ..., a_n, what is the probability that their sum with randomly chosen signs is at most epsilon in absolute value? |