Often used as importance sampling probabilities, leverage scores have become indispensable in randomized algorithms for linear algebra, optimization, graph theory, and machine learning. A major body of work seeks to adapt these scores to low-rank approximation problems. However, existing "low-rank leverage scores" can be difficult to compute, often work for just a single application, and are sensitive to matrix perturbations. We show how to avoid these issues by exploiting connections between low-rank approximation and regularization. Specifically, we employ ridge leverage scores, which are simply standard leverage scores computed with respect to an $\ell_2$ regularized input. Importance sampling by these scores gives the first unified solution to two of the most important low-rank sampling problems: $(1+\epsilon)$ error column subset selection and $(1+\epsilon)$ error projection-cost preservation. Moreover, ridge leverage scores satisfy a key monotonicity property that does not hold for any prior low-rank leverage scores. Their resulting robustness leads to two sought-after results in randomized linear algebra. 1) We give the first input-sparsity time low-rank approximation algorithm based on iterative column sampling, resolving an open question posed in [LMP13], [CLM+15], and [AM15]. 2) We give the first single-pass streaming column subset selection algorithm whose real-number space complexity has no dependence on stream length.

该研究提出了一种新的基于采样策略的算法来计算矩阵的最优低秩逼近，相较于之前基于随机投影的算法，该方法可适用于稀疏结构等场景，并在核矩阵逼近算法方面表现最优。

通过Ridge Leverage Score抽样进行输入稀疏时间低秩逼近