One popular method for dealing with large-scale data sets is sampling. For
example, by using the empirical statistical leverage scores as an importance
sampling distribution, the method of algorithmic leveraging samples and
rescales rows/columns of data matrices to reduce the data size before
performing computations on the subproblem. This method has been successful in
improving computational efficiency of algorithms for matrix problems such as
least-squares approximation, least absolute deviations approximation, and
low-rank matrix approximation. Existing work has focused on algorithmic issues
such as worst-case running times and numerical issues associated with providing
high-quality implementations, but none of it addresses statistical aspects of
this method.
In this paper, we provide a simple yet effective framework to evaluate the
statistical properties of algorithmic leveraging in the context of estimating
parameters in a linear regression model with a fixed number of predictors. We
show that from the statistical perspective of bias and variance, neither
leverage-based sampling nor uniform sampling dominates the other. This result
is particularly striking, given the well-known result that, from the
algorithmic perspective of worst-case analysis, leverage-based sampling
provides uniformly superior worst-case algorithmic results, when compared with
uniform sampling. Based on these theoretical results, we propose and analyze
two new leveraging algorithms. A detailed empirical evaluation of existing
leverage-based methods as well as these two new methods is carried out on both
synthetic and real data sets. The empirical results indicate that our theory is
a good predictor of practical performance of existing and new leverage-based
algorithms and that the new algorithms achieve improved performance.

本文在大数据集上提出了算法杠杆效应的采样方法，通过样本采集分布来提高算法的计算效率，并在固定预测因子的线性回归模型中，提出了一种简单有效的框架来评估算法杠杆的统计性能。其结果表明核心的采样方法的统计性能既不会因为采用杠杆采样而主导也不会因采用均匀采样而优于杠杆采样，但其在最坏分析情况下，杠杆采样与均匀采样相比都能提供更好的结果。在理论性能基础上，本文提出并分析了两种新的杠杆算法，并在合成和真实数据集上进行了详细的实证评估。

算法协同作用的统计视角

A Statistical Perspective on Algorithmic Leveraging

We revisit the matrix problems sparse null space and matrix sparsification,
and show that they are equivalent. We then proceed to seek algorithms for these
problems: We prove the hardness of approximation of these problems, and also
give a powerful tool to extend algorithms and heuristics for sparse
approximation theory to these problems.

矩阵问题 —— 稀疏零空间和矩阵稀疏化的问题已被证明是等价的，但其近似难度证明较难且算法需要拓展。