| COMPUTER SCIENCE AND DISCRETE MATHEMATICS SEMINAR II | |
| Topic: | An Elementary Proof of the Restricted Invertibility Theorem |
| Speaker: | Nikhil Srivastava |
| Affiliation: | Member, School of Mathematics |
| Date: | Tuesday, November 9 |
| Time/Room: | 10:30am - 12:30pm/S-101 |
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.