An elementary proof of the restricted invertibility theorem
By Daniel A. Spielman, Nikhil Srivastava. 2009
76 citations recorded by the source corpus.
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.
Subfields: Algebra and Number Theory, Applied Mathematics, Computational Theory and Mathematics
View Paper: https://www.semanticscholar.org/paper/60c3b1b9c07262ec0f22b8cfb883beae99f8c8cd
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Algebra and Number Theory
In Applied Mathematics
- Deanna Needell
- Joel A. Tropp
- Per-Gunnar Martinsson
- Stanislav Minsker
- Ramon van Handel
- Aaditya Ramdas
- Steven R. Howard
- Jon D. McAuliffe
In Computational Theory and Mathematics
- Joel A. Tropp
- Deanna Needell
- Per-Gunnar Martinsson
- Stanislav Minsker
- Aaditya Ramdas
- Jon D. McAuliffe
- Steven R. Howard
- Jasjeet S. Sekhon
Citations in the corpus
- Lower bounds for the smallest singular value of structured random matrices (2016, unknown): “MR2255338 (2008b:65060) [33] Spielman, D.”
- Paved with Good Intentions: Analysis of a Randomized Block Kaczmarz Method (2012, background): “ing result, Proposition 1.3, as a corollary of Proposition 3.1 also appears in the paper [BT91]. The last few years have witnessed some striking advances in this area. Indeed, Spielman and Srivastava [SS12] have recently invented an elementary proof of the Restricted Invertibility Principle. Their m”