Restricted invertibility revisited

DOI10.1007/978-3-319-44479-6_27MaRDI QIDQ4604394zbMATH OpenOpenAlexFDO

Authors Assaf Naor, Pierre Youssef

Publication date 26 February 2018

Published in A Journey Through Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

restricted invertibility of matricesrestricted invertibility theorem

Mathematics Subject Classification ID

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

Abstract: Suppose that $m,ninmathbbN$ and that $A:mathbb{R}^{m}omathbb{R}^n$ is a linear operator. It is shown here that if $k,rinmathbbN$ satisfy $$ then there exists a subset $sigmasubseteq1,ldots,m$ with $|sigma|=k$ such that the restriction of $A$ to $mathbb{R}^{sigma}subseteqmathbb{R}^m$ is invertible, and moreover the operator norm of the inverse $A^{-1}:A(mathbb{R}^{sigma})omathbb{R}^m$ is at most a constant multiple of the quantity $sqrtmr/((r-k)su{m}_{i=r}^{m}mathsf{s}_i(A{)}^2)$, where $mathsf{s}_1(A)geqslantldotsgeqslantmathsf{s}_m(A)$ are the singular values of $A$. This improves over a series of works, starting from the seminal Bourgain--Tzafriri Restricted Invertibility Principle, through the works of Vershynin, Spielman--Srivastava and Marcus--Spielman--Srivastava. In particular, this directly implies an improved restricted invertibility principle in terms of Schatten--von Neumann norms.

Recommendations

• An elementary proof of the restricted invertibility theorem
• scientific article; zbMATH DE number 4144774
• Infinite dimensional restricted invertibility
• Invertibility of ``large submatrices with applications to the geometry of Banach spaces and harmonic analysis
• A note on column subset selection

Cites work

• scientific article; zbMATH DE number 3650737 (Why is no real title available?)
• scientific article; zbMATH DE number 3124239 (Why is no real title available?)
• scientific article; zbMATH DE number 4205183 (Why is no real title available?)
• scientific article; zbMATH DE number 4144774 (Why is no real title available?)
• scientific article; zbMATH DE number 3944534 (Why is no real title available?)
• scientific article; zbMATH DE number 4056349 (Why is no real title available?)
• scientific article; zbMATH DE number 4103727 (Why is no real title available?)
• scientific article; zbMATH DE number 18574 (Why is no real title available?)
• scientific article; zbMATH DE number 194266 (Why is no real title available?)
• scientific article; zbMATH DE number 2053394 (Why is no real title available?)
• scientific article; zbMATH DE number 775021 (Why is no real title available?)
• scientific article; zbMATH DE number 803215 (Why is no real title available?)
• scientific article; zbMATH DE number 967931 (Why is no real title available?)
• scientific article; zbMATH DE number 3061616 (Why is no real title available?)
• A combinatorial problem; stability and order for models and theories in infinitary languages
• A proportional Dvoretzky-Rogers factorization result
• Absolut p-summierende Abbildungen in normierten Räumen
• An elementary proof of the restricted invertibility theorem
• Column subset selection, matrix factorization, and eigenvalue optimization
• Covariance estimation for distributions with \({2+\varepsilon}\) moments
• Interlacing families. I: Bipartite Ramanujan graphs of all degrees
• Interlacing families. II: Mixed characteristic polynomials and the Kadison-Singer problem
• Interlacing families. III: Sharper restricted invertibility estimates
• Invertibility of ``large submatrices with applications to the geometry of Banach spaces and harmonic analysis
• John's decompositions: Selecting a large part
• On circulant matrices
• On the density of families of sets
• Positive linear maps of operator algebras
• RESTRICTED INVERTIBILITY AND THE BANACH–MAZUR DISTANCE TO THE CUBE
• Ramanujan graphs and the solution of the Kadison-Singer problem
• Shattering news
• Sparse quadratic forms and their geometric applications [following Batson, Spielman, and Srivastava].
• The Banach-Mazur distance to the cube and the Dvoretzky-Rogers factorization
• Twice-Ramanujan sparsifiers

Cited in

(23)

• Restricted invertibility of continuous matrix functions
• Limitations of the invertible-map equivalences
• Stable recovery and the coordinate small-ball behaviour of random vectors
• Interlacing families. III: Sharper restricted invertibility estimates
• scientific article; zbMATH DE number 4144774 (Why is no real title available?)
• Average-case analysis of the Gaussian elimination with partial pivoting
• Circular law for sparse random regular digraphs
• Random matrices: overcrowding estimates for the spectrum
• Invertibility of ``large submatrices with applications to the geometry of Banach spaces and harmonic analysis
• An involution on restricted Laguerre histories and its applications
• An elementary proof of the restricted invertibility theorem
• Subset selection for matrices with fixed blocks
• Sampling discretization and related problems
• On the estimate of the distance to non-invertibility
• A note on column subset selection
• The cylindrical width of transitive sets
• Anderson-Bernoulli localization at large disorder on the 2D lattice
• Putting \(t\)-invertibility to use
• On a new method for controlling the entire spectrum in the problem of column subset selection
• On the Banach-Mazur distance to cross-polytope
• Small ball probability for the condition number of random matrices
• Overlaps, eigenvalue gaps, and pseudospectrum under real Ginibre and absolutely continuous perturbations
• Revisiting the Bourgain-Tzafriri restricted invertibility theorem

This page was built for publication: Restricted invertibility revisited

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4604394)