The Condition Number of a Random Matrix: From von Neumann-Goldstine to Spielman-Teng

Video of this lecture

COMPUTER SCIENCE AND DISCRETE MATHEMATICS SEMINAR I
Topic:The Condition Number of a Random Matrix: From von Neumann-Goldstine to Spielman-Teng
Speaker:Van Vu
Affiliation:Rutgers, The State University of New Jersey
Date:Monday, September 27
Time/Room:11:15am - 12:15pm/S-101
Video Link:https://video.ias.edu/csdm/vu

The condition number of a matrix is at the heart of numerical linear algebra. In the 1940s von-Neumann and Goldstine, motivated by the problem of inverting, posed the following question: (1) What is the condition number of a random matrix ? During the years, this question was raised again and again, by various researchers (Smale, Demmel etc). About ten years ago, motivated by "Smoothed Analysis", Spielman and Teng raised a more general question: (2) What is the condition number of a randomly perturbed matrix ? In this talk, I am going to first survey recent progresses concerning these questions, with many new open questions. Next, I will focus on a recent result with Tao, which gives the exact distribution for (1), extending an earlier work (for the Gaussian case) of Edelman and answering a question of Spielman and Teng.