Recursive Sampling for the Nystrom Method
We give the first algorithm for kernel Nystrom 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^2) additional runtime. While leverage score sampling has long been known to give strong theoretical guarantees for Nystrom 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 kernel approximations in less time than popular techniques such as classic Nystrom approximation and the random Fourier features method.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Spectral Clustering using Eigenspectrum Shape Based Nystrom Sampling
Spectral clustering has shown a superior performance in analyzing the cluster structure. However, its computational complexity limits its application in analyzing large-scale data. To address this problem, many low-rank …
ClusteringWhy Size Matters: Feature Coding as Nystrom Sampling
Recently, the computer vision and machine learning community has been in favor of feature extraction pipelines that rely on a coding step followed by a linear classifier, due to their overall simplicity, well understood …
Computational EfficiencyLocalization from structured distance matrices via low-rank matrix recovery
We study the problem of determining the configuration of $n$ points by using their distances to $m$ nodes, referred to as anchor nodes. One sampling scheme is Nystrom sampling, which assumes known distances between the a…
Pack only the essentials: Adaptive dictionary learning for kernel ridge regression
One of the major limits of kernel ridge regression (KRR) is that storing and manipulating the kernel matrix K_n for n samples requires O(n^2) space, which rapidly becomes unfeasible for large n. Nystrom approximations re…
Scalable Spectral Clustering with Nystrom Approximation: Practical and Theoretical Aspects
Spectral clustering techniques are valuable tools in signal processing and machine learning for partitioning complex data sets. The effectiveness of spectral clustering stems from constructing a non-linear embedding base…
Clustering