An elementary proof of the restricted invertibility theorem
An elementary proof of the restricted invertibility theorem
复制标题
限制可逆性定理的基本证明
DOI：
--
复制
发表时间：
2009
期刊：
影响因子：
--
通讯作者：
N. Srivastava
中科院分区：
文献类型：
--
作者：
D. Spielman;N. Srivastava
我们给出了Bourain和Tzafriri的限制可逆性定理的一个推广的初等证明，该定理大体上说，任何具有单位长度的列和有界算子范数的矩阵都有一个大的坐标子空间，在这个子空间上它是良好可逆的。我们的证明给出了这一结果的最紧致的已知形式，是构造性的，并提供了寻找所需子空间的确定性多项式时间算法。
We give an elementary proof of a generalization of Bourgain and Tzafriri’s Restricted Invertibility Theorem, which says roughly that any matrix with columns of unit length and bounded operator norm has a large coordinate subspace on which it is well-invertible. Our proof gives the tightest known form of this result, is constructive, and provides a deterministic polynomial time algorithm for finding the desired subspace.