Recursive Sampling for the Nyström Method

2016/05/24 by Cameron Musco, Christopher Musco, Musco, Cameron +1 · 1 citation
Computer Science · Physics and Astronomy · #Stochastic Gradient Optimization Techniques #Model Reduction and Neural Networks #Gaussian Processes and Bayesian Inference

paper · pdf · doi:10.48550/arxiv.1605.07583

Abstract

We give the first algorithm for kernel Nyström approximation that runs in *linear time in the number of training points* and is provably accurate for all kernel matrices, without dependence on regularity or incoherence conditions. The algorithm projects the kernel onto a set of s landmark points sampled by their *ridge leverage scores*, requiring just O(ns) kernel evaluations and O(ns²) additional runtime. While leverage score sampling has long been known to give strong theoretical guarantees for Nyström approximation, by employing a fast recursive sampling scheme, our algorithm is the first to make the approach scalable. Empirically we show that it finds more accurate, lower rank kernel approximations in less time than popular techniques such as uniformly sampled Nyström approximation and the random Fourier features method.

Cited by

• Eigenvalue Decay Implies Polynomial-Time Learnability for Neural Networks

Related

• Making the Nyström method highly accurate for low-rank approximations
• Sampling-based Nyström Approximation and Kernel Quadrature
• Boosting Nyström Method
• Faster Low-Rank Approximation and Kernel Ridge Regression via the Block-Nyström Method
• Local optimisation of Nyström samples through stochastic gradient descent