An Elementary Proof of the Restricted Invertibility Theorem
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.
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.
- Srivastava Nikhil
- Princeton IAS