On the Nyström Method for Approximating a Gram Matrix for Improved Kernel-Based Learning

By Petros Drineas, Michael W. Mahoney. 2005

1,164 citations recorded by the source corpus.

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

Optimal Rates for Random Fourier Features (2015, background): “We also propose a RFF approximation to derivatives of a kernel with a theoretical study on its approximation quality.”
Scalable Kernel Methods via Doubly Stochastic Gradients (2014, methodology): “kernel matrix, the generalization ability after using low-rank approximation is typically of order O(1/ √ r + 1/ √ n) [4, 5], which implies that the rank needs to be nearly linear in the number of data points! Thus, in order for kernel methods to achieve the best generalization ability, low-rank app”
Nyströmformer: A Nystöm-based Algorithm for Approximating Self-Attention (2021, background): “(Fanuel, Schreurs, and Suykens 2019) developed DAS (Deterministic Adaptive Sampling) and RAS (Randomized Adaptive Sampling) algorithms to promote diversity of landmarks selection.”
Finding Structure with Randomness: Probabilistic Algorithms for Constructing Approximate Matrix Decompositions (2009, methodology): “When the input matrixA is positive semidefinite, the Nyström method can be used to improve the quality of standard factorizations at almost no additional cost; see [48] and its bibliography.”
Using Neural Network Formalism to Solve Multiple-Instance Problems (2016, background): “Regarding the choice of MIL paradigm we argue that there is only little difference between embedded-space and bag-space paradigms, because (i) many machine learning methods that accept fixed-length feature vectors can be used with kernels (or kernels on top of kernels [18,20]); (ii) kernels can be v”
Domain Generalization by Marginal Transfer Learning (2017, methodology): “We examine two such techniques in the context of marginal transfer learning, the Nystr¨om approximation (Williams and Seeger, 2001; Drineas and Mahoney, 2005) and random Fourier features.”
LatentGNN: Learning Efficient Non-local Relations for Visual Recognition (2019, methodology): “The most well known approaches in this category are random Fourier features (Rahimi & Recht, 2008; 2009) and the Nystr¨om method (Williams & Seeger, 2001; Drineas & Mahoney, 2005).”
Learning Deep Representations with Probabilistic Knowledge Transfer (2018, background): “This process can be viewed as a Nyström-like approximation of the full similarity matrix [11], and it was experimentally established that it speeds up the training process, while it does not negatively impact the learned representation.”
TAIL BOUNDS FOR ALL EIGENVALUES OF A SUM OF RANDOM MATRICES (2011, background): “cal properties of Banach spaces [LM93, SD01, Ver10]. Since then, the nonasymptotic theory has found applications in areas including theoretical computer science [Ach03, Vem04, SS08], machine learning [DM05], optimization [Nem07, So09], and numerical linear algebra [DM10, HMT11, Mah11]. As is the cas”
Multi-modal estimation with kernel embeddings for learning motion models (2013, methodology): “As suggested in [5], we use a Nyström method for generating low-rank approximations to the Gram matrix [32], which can then be inverted in O(N(2)) cost using the Woodbury identity.”
Handbook of Big Data (2016, background): “The AN, therefore, makes no attempt to guess at pleasing and much less optimal values for such graphical parameters as font size of variable labels and margin size in blockplots.”
Compact Random Feature Maps (2013, background): “To solve this challenge, several schemes have been proposed to explicitly approximate the kernel matrix, including low-rank approximations (Blum, 2006) (Bach & Jordan, 2005), sampling individual entries (Achlioptas et al., 2002), or discarding entire rows (Drineas & Mahoney, 2005).”
Online sketching hashing (2015, methodology): “An extensive body of algorithms exist, including CUR decomposition [5], random projection [31, 22], column sampling method [7, 1], and Nyström method [6].”