Computer Science/Discrete Mathematics Seminar I

What does the spectrum of a random matrix look like when we make no assumption whatsoever about the covariance pattern of its entries?  It may appear hopeless that anything useful can be said at this level of generality. Nonetheless, a widely used set of tools known as "matrix concentration inequalities" makes it possible to estimate at least the spectral norm of very general random matrices up to logarithmic factors in the dimension. On the other hand, it is well known that these inequalities fail to yield sharp results for even the simplest random matrix models.

In this talk I will describe a powerful new class of matrix concentration inequalities that achieve optimal results in many situations that are outside the reach of classical methods. Our results are easily applicable in concrete examples, and yield detailed nonasymptotic information on the full spectrum of essentially arbitrarily structured random matrices. These new inequalities arise from an unexpected phenomenon: the spectrum of random matrices is accurately captured by certain predictions of free probability theory under surprisingly minimal assumptions. Our proofs quantify the notion that it costs little to be free.

The talk is based on joint works with Afonso Bandeira and March Boedihardjo, and with Tatiana Brailovskaya. No prior background will be assumed.