论文标题
关于加权柱的限制可逆性的注释
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 r \ leq r \ leq \ mbox {rank rank {rank rank}（a）$ $σ_ {\ min}（a _ {\ Mathcal {s}} w _ {\ Mathcal {s}}}）^2 \ geq \ frac {（\ sqrt {r} - \ sqrt {k-1}）^2} {\ | w^{ - 1} \ | | _f^{2}} \ cdot \ cdot \ cdot \ cdot \ frac {r} $ w = \ mbox {diag}（w_1，\ ldots，w_m）$，$ w_i $是$ a $的$ i $ th列的重量。我们的结构是算法，并采用了由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 $σ_{\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}σ_{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.
