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.