标题： 关于带权列的限制可逆性注记 显示英文标题

标题： A note on restricted invertibility with weighted columns

摘要： 限制可逆性定理最初由 Bourgain 和 Tzafriri 在$1987$中引入，被认为是几何和分析领域中最著名的定理之一。 在本笔记中，我们给出了该定理的加权版本，并稍有改进的估计。 特别地，我们证明了对于任意的 $A\in\mathbb{R}^{n\times m}$ 和 $k,r\in\mathbb{N}$ 满足 $k\leq r\leq \mbox{rank}(A)$，存在一个大小为 $k$ 的子集 $\mathcal{S}$，使得 $\sigma_{\min}(A_{\mathcal{S}}W_{\mathcal{S}})^2\geq \frac{(\sqrt{r}-\sqrt{k-1})^2}{\|W^{-1}\|_F^{2}}\cdot\frac{r}{\sum_{i=1}^{r}\sigma_{i}(A)^{-2}}$，其中 $W=\mbox{diag}(w_1,\ldots,w_m)$，$w_i$ 是 $A$ 的第 $i$列的权重。 我们的构造是算法性的，并采用了 Marcus、Spielman 和 Srivastava 发展的交错多项式族。 显示英文摘要

摘要： 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\in\mathbb{R}^{n\times m}$ and $k,r\in\mathbb{N}$ with $k\leq r\leq \mbox{rank}(A)$, there exists a subset $\mathcal{S}$ of size $k$ such that $\sigma_{\min}(A_{\mathcal{S}}W_{\mathcal{S}})^2\geq \frac{(\sqrt{r}-\sqrt{k-1})^2}{\|W^{-1}\|_F^{2}}\cdot\frac{r}{\sum_{i=1}^{r}\sigma_{i}(A)^{-2}}$, where $W=\mbox{diag}(w_1,\ldots,w_m)$ with $w_i$ 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.