Share on Facebook Tweet on Twitter Share on LinkedIn Share by email
An Elementary Proof of the Restricted Invertibility Theorem

Speaker  Srivastava Nikhil

Affiliation  Princeton IAS

Host  Alexandra Kolla

Duration  00:57:06

Date recorded  10 February 2011

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.

©2011 Microsoft Corporation. All rights reserved.
> An Elementary Proof of the Restricted Invertibility Theorem