DIMACS Theoretical Computer Science Seminar

Title: An Elementary Proof of the Restricted Invertibility Theorem

Speaker: Nikhil Srivastava, IAS

Date: Wednesday, February 9, 2011 11:00-12:00pm

Location: DIMACS Center, CoRE Bldg, Room 431, Rutgers University, Busch Campus, Piscataway, NJ


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.