This is an announcement for the paper "An elementary proof of the Restricted Invertibility Theorem" by Daniel A. Spielman and Nikhil Srivastava.

Abstract: 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.

Archive classification: math.FA

The source file(s), restrict.tex: 13698 bytes, is(are) stored in gzipped form as 0911.1114.gz with size 5kb. The corresponding postcript file has gzipped size 58kb.

Submitted from: nikhil.srivastava@yale.edu

The paper may be downloaded from the archive by web browser from URL

http://front.math.ucdavis.edu/0911.1114

or

http://arXiv.org/abs/0911.1114

or by email in unzipped form by transmitting an empty message with subject line

uget 0911.1114

or in gzipped form by using subject line

get 0911.1114

to: math@arXiv.org.