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.

Speaker Details

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.

Date:
Speakers:
Srivastava Nikhil
Affiliation:
Princeton IAS

    • Portrait of Jeff Running

      Jeff Running