An Elementary Proof of the Restricted Invertibility Theorem

Date

February 10, 2011

Speaker

Srivastava Nikhil

Affiliation

Princeton IAS

Overview

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.

Speakers

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.