An elementary proof of the restricted invertibility theorem |
| |
Authors: | Daniel A. Spielman Nikhil Srivastava |
| |
Affiliation: | 1.Department of Computer Science, Program in Applied Mathematics,Yale University,New Haven,USA;2.Department of Computer Science,Yale University,New Haven,USA |
| |
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. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|