Title:  An Elementary Proof of the Restricted Invertibility Theorem

Speaker:  Nikhil Srivastava, IAS

Abstract:

We give an elementary proof of a generalization of Bourgain and
Tzafriri's Restricted Invertibility Theorem, which says roughly that
any matrix with columns of unit length and bounded operator norm has a
large coordinate subspace on which it is well-invertible. Our proof
gives the tightest known form of this result, is constructive, and
provides a deterministic polynomial time algorithm for finding the
desired subspace.

Joint work with Dan Spielman.