论文标题
随机预测的精确表达式：低级别近似和随机牛顿
Precise expressions for random projections: Low-rank approximation and randomized Newton
论文作者
论文摘要
通常希望通过将其投影到低维子空间来降低大数据集的维度。矩阵草图已成为一种非常有效地降低这种维度的强大技术。即使有关于草图最差的表现的广泛文献，但现有的保证通常与实践中观察到的差异截然不同。我们利用随机矩阵的光谱分析中的最新发展来开发新技术，这些技术为通过素描获得的随机投影矩阵的预期值提供了准确的表达。这些表达式可以用来表征各种常见的机器学习任务中尺寸降低的性能，从低级别近似到迭代随机优化。我们的结果适用于几种流行的草图方法，包括高斯和拉德马赫草图，它们可以根据数据的光谱特性对这些方法进行精确分析。经验结果表明，我们得出的表达式反映了这些草图方法的实际性能，直到低阶效应甚至不变因素。
It is often desirable to reduce the dimensionality of a large dataset by projecting it onto a low-dimensional subspace. Matrix sketching has emerged as a powerful technique for performing such dimensionality reduction very efficiently. Even though there is an extensive literature on the worst-case performance of sketching, existing guarantees are typically very different from what is observed in practice. We exploit recent developments in the spectral analysis of random matrices to develop novel techniques that provide provably accurate expressions for the expected value of random projection matrices obtained via sketching. These expressions can be used to characterize the performance of dimensionality reduction in a variety of common machine learning tasks, ranging from low-rank approximation to iterative stochastic optimization. Our results apply to several popular sketching methods, including Gaussian and Rademacher sketches, and they enable precise analysis of these methods in terms of spectral properties of the data. Empirical results show that the expressions we derive reflect the practical performance of these sketching methods, down to lower-order effects and even constant factors.
