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.