An Elementary Proof of the Restricted Invertibility Theorem


February 10, 2011


Srivastava Nikhil


Princeton IAS


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.


Srivastava Nikhil

Nikhil is interested in spectral graph theory, linear algebra, and convex geometry. He is currently a postdoc at the IAS; previously, he received a PhD from Dan Spielman at Yale, and spent three summers at MSR.