An Elementary Proof of the Restricted Invertibility Theorem

March 30, 2011

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 (i.e. spectral) norm has a large
coordinate subspace (i.e. a large column submatrix) on which it is
well-invertible (has singular values bounded away from zero). 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.

Joint work with Dan Spielman.