2020/05/03 by Jiaxin Xie, Xie, Jiaxin
Computer Science · Mathematics · #FOS: Mathematics #Functional Analysis (math.FA) #Geometric and Algebraic Topology #Mathematical Dynamics and Fractals #Polynomial and algebraic computation
paper · pdf · doi:10.48550/arxiv.2005.01070
openalex publication_date 2020/05/03 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The restricted invertibility theorem was originally introduced by Bourgain and Tzafriri in 1987 and has been considered as one of the most celebrated theorems in geometry and analysis. In this note, we present weighted versions of this theorem with slightly better estimates. Particularly, we show that for any A∈ℝn× m and k,r∈ℕ with k≤ r≤ rank(A), there exists a subset S of size k such that σmin(ASWS)2≥ \frac(√(r)-√(k-1))2‖W-1‖F2⋅\fracr∑i=1rσi(A)-2, where W=diag(w1,…,wm) with wi being the weight of the i-th column of A. Our constructions are algorithmic and employ the interlacing families of polynomials developed by Marcus, Spielman, and Srivastava.