We study subset selection for matrices defined as follows: given a matrix
$\matX \in \R^{n \times m}$ ($m > n$) and an oversampling parameter $k$ ($n \le
k \le m$), select a subset of $k$ columns from $\matX$ such that the
pseudo-inverse of the subsampled matrix has as smallest norm as possible. In
this work, we focus on the Frobenius and the spectral matrix
证明对于任意实值矩阵 X，在正整数 r≥k 的情况下，存在 X 的 r 个列的子集，将 X 投影到其中一个列的线性组合中，得出的结果将是 Frobenius 范数下的 X 的最佳秩 - k 逼近的一个近似值等于 sqrt ((r + 1)/(r-k +1))。并提出一个确定性算法可在 O (r n m^ω log m) 时间内找到这样的列的子集，其中 ω 是矩阵乘法的指数。同样，我们提供了一种更快的随机算法，可在 O (r n m^2) 时间内进行运算。