Revisiting the Nystrom Method for Improved Large-Scale Machine Learning

2013/03/07 by Alex Gittens, Michael W. Mahoney, Gittens, Alex +1 · 15 citations
Computer Science · Engineering · Mathematics · #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Markov Chains and Monte Carlo Methods #Numerical Analysis (math.NA) #Sparse and Compressive Sensing Techniques #Stochastic Gradient Optimization Techniques

paper · pdf · doi:10.48550/arxiv.1303.1849

openalex publication_date 2013/03/07 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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.

Citations

• Finding Structure with Randomness: Probabilistic Algorithms for Constructing Approximate Matrix Decompositions

Cited by

• Approximation and learning with compositional tensor trains
• Determinant-Based Error Bounds for CUR Matrix Approximation: Oversampling and Volume Sampling
• Generalized Interlacing Families: New Error Bounds for CUR Matrix Decompositions
• Numerical Stability of the Nyström Method
• Accelerated decomposition of bistochastic kernel matrices by low rank approximation
• Even Faster Kernel Matrix Linear Algebra via Density Estimation
• SlimDiff: Training-Free, Activation-Guided Hands-free Slimming of Diffusion Models
• Linear Transformers Implicitly Discover Unified Numerical Algorithms
• The Singular Value Decomposition, Applications and Beyond
• Computing active subspaces with Monte Carlo
• Does block size matter in randomized block Krylov low-rank approximation?
• Online Tensor Methods for Learning Latent Variable Models
• Faster Low-Rank Approximation and Kernel Ridge Regression via the Block-Nyström Method
• Splitting-based randomized dynamical low-rank approximations for stiff matrix differential equations
• Generalized Reference Kernel With Negative Samples For Support Vector One-class Classification

Related

• Making the Nyström method highly accurate for low-rank approximations
• Fast deterministic approximation of symmetric indefinite kernel matrices with high dimensional datasets
• Randomized Nyström approximation of non-negative self-adjoint operators
• Fast and stable randomized low-rank matrix approximation
• Boosting Nyström Method