An elementary proof of the restricted invertibility theorem

DOI10.1007/s11856-011-0194-2zbMath1261.46007arXiv0911.1114OpenAlexW2034070643MaRDI QIDQ1760392

Daniel A. Spielman, Nikhil Srivastava

Publication date: 13 November 2012

Published in: Israel Journal of Mathematics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/0911.1114

zbMATH Keywords

Kadison-Singer problemrestricted invertibility of matricesrestricted invertibility theorem

Mathematics Subject Classification ID

Local theory of Banach spaces (46B07) Norms of matrices, numerical range, applications of functional analysis to matrix theory (15A60) General (adjoints, conjugates, products, inverses, domains, ranges, etc.) (47A05)

Related Items (20)

Restricted invertibility of continuous matrix functions ⋮ Lower bounds for the smallest singular value of structured random matrices ⋮ Sampling discretization and related problems ⋮ Interlacing families. III: Sharper restricted invertibility estimates ⋮ RESTRICTED INVERTIBILITY AND THE BANACH–MAZUR DISTANCE TO THE CUBE ⋮ Constructing Linear-Sized Spectral Sparsification in Almost-Linear Time ⋮ Proportional Volume Sampling and Approximation Algorithms for A-Optimal Design ⋮ Infinite dimensional restricted invertibility ⋮ Interactions of computational complexity theory and mathematics ⋮ Small Ball Probability for the Condition Number of Random Matrices ⋮ Restricted Invertibility Revisited ⋮ Paved with good intentions: analysis of a randomized block Kaczmarz method ⋮ A few remarks on sampling of signals with small spectrum ⋮ Extracting a basis with fixed block inside a matrix ⋮ Randomized block Kaczmarz method with projection for solving least squares ⋮ Subset selection for matrices with fixed blocks ⋮ Invertibility threshold for $H^{∞}$ trace algebras, and effective matrix inversions ⋮ On a new method for controlling the entire spectrum in the problem of column subset selection ⋮ The legacy of Jean Bourgain in geometric functional analysis ⋮ The Kadison-Singer problem

Cites Work

• Invertibility of ``large submatrices with applications to the geometry of Banach spaces and harmonic analysis
• Revisiting the Bourgain-Tzafriri restricted invertibility theorem
• Twice-ramanujan sparsifiers
• John's decompositions: Selecting a large part
• Unnamed Item
• Unnamed Item

This page was built for publication: An elementary proof of the restricted invertibility theorem