Revisiting the Nystrom Method for Improved Large-Scale Machine Learning

Abstract

We reconsider randomized algorithms for the low-rank approximation of symmetric positive semi-definite (SPSD) matrices such as Laplacian and kernel matrices that arise in data analysis and machine learning applications. Our main results consist of an empirical evaluation of the performance quality and running time of sampling and projection methods on a diverse suite of SPSD matrices. Our results highlight complementary aspects of sampling versus projection methods; they characterize the effects of common data preprocessing steps on the performance of these algorithms; and they point to important differences between uniform sampling and nonuniform sampling methods based on leverage scores. In addition, our empirical results illustrate that existing theory is so weak that it does not provide even a qualitative guide to practice. Thus, we complement our empirical results with a suite of worst-case theoretical bounds for both random sampling and random projection methods. These bounds are qualitatively superior to existing bounds---e.g. improved additive-error bounds for spectral and Frobenius norm error and relative-error bounds for trace norm error---and they point to future directions to make these algorithms useful in even larger-scale machine learning applications.

60 pages, 15 color figures; updated proof of Frobenius norm bounds, added comparison to projection-based low-rank approximations, and an analysis of the power method applied to SPSD sketches

References in corpus (3)

• A Statistical Perspective on Algorithmic Leveraging
• On sparse representations of linear operators and the approximation of matrix products
• Spectral approximations in machine learning

Cited by in corpus (10)

• Computing active subspaces with Monte Carlo
• BlinkML: Efficient Maximum Likelihood Estimation with Probabilistic Guarantees
• The Singular Value Decomposition, Applications and Beyond
• Randomized methods to characterize large-scale vortical flow network
• Optimal Sampling Designs for Multi-dimensional Streaming Time Series with Application to Power Grid Sensor Data
• Online Tensor Methods for Learning Latent Variable Models
• Fourier Sparse Leverage Scores and Approximate Kernel Learning
• pylspack: Parallel algorithms and data structures for sketching, column subset selection, regression and leverage scores
• Efficient Non-oblivious Randomized Reduction for Risk Minimization with Improved Excess Risk Guarantee
• Co-factor analysis of citation networks