Fetching the paper…
Reading the bibliography…
We give the first algorithm for kernel Nystr\"om 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.
Advances in kernel methods
Bernhard Schölkopf, Alexander J. Smola, and Klaus-Robert Müller · 1999
Earlier work this paper cites.
Sparse greedy matrix approximation for machine learning
Alex J Smola and Bernhard Schökopf · 2000
Earlier work this paper cites.
Sampling techniques for kernel methods
Dimitris Achlioptas, Frank Mcsherry, and Bernhard Schölkopf · 2001
Earlier work this paper cites.
Using the Nyström method to speed up kernel machines
Christopher Williams and Matthias Seeger · 2001
Earlier work this paper cites.
Kernel independent component analysis
Francis Bach and Michael I. Jordan · 2002
Earlier work this paper cites.
Efficient SVM training using low-rank kernel representations
Shai Fine and Katya Scheinberg · 2002
Earlier work this paper cites.
The elements of statistical learning: data mining, inference and prediction
Trevor Hastie, Robert Tibshirani, and Jerome Friedman · 2002
Earlier work this paper cites.
Learning with kernels: support vector machines, regularization, optimization, and beyond
Bernhard Schölkopf and Alexander J Smola · 2002
Earlier work this paper cites.
Global versus local methods in nonlinear dimensionality reduction
Vin De Silva and Joshua B Tenenbaum · 2003
Earlier work this paper cites.
On the Nyström method for approximating a Gram matrix for improved kernel-based learning
Petros Drineas and Michael W Mahoney · 2005
Earlier work this paper cites.
FastMap, MetricMap, and Landmark MDS are all Nyström algorithms
John Platt · 2005
Earlier work this paper cites.
Kernels as features: On kernels, margins, and low-dimensional mappings
Maria-Florina Balcan, Avrim Blum, and Santosh Vempala · 2006
Earlier work this paper cites.
Detection of non-coding RNAs on the basis of predicted secondary structure formation free energy change
Andrew V Uzilov, Joshua M Keegan, and David H Mathews · 2006
Earlier work this paper cites.
Learning bounds for kernel regression using effective data dimensionality
Tong Zhang · 2006
Earlier work this paper cites.
Random features for large-scale kernel machines
Ali Rahimi and Benjamin Recht · 2007
Earlier work this paper cites.
Relative-error CUR matrix decompositions
Petros Drineas, Michael W Mahoney, and S Muthukrishnan · 2008
Earlier work this paper cites.
Improved Nyström low-rank approximation and error analysis
Kai Zhang, Ivor W. Tsang, and James T. Kwok · 2008
Earlier work this paper cites.
Unsupervised feature selection for the k k -means clustering problem
Christos Boutsidis, Michael W. Mahoney, and Petros Drineas · 2009
Earlier work this paper cites.
Spectral methods in machine learning: New strategies for very large datasets
Mohamed-Ali Belabbas and Patrick J. Wolfe · 2009
Earlier work this paper cites.
The WEKA data mining software: an update
Mark Hall, Eibe Frank, Geoffrey Holmes, Bernhard Pfahringer, Peter Reutemann, and Ian H Witten · 2009
Cited alongside, same era.
Weighted sums of random kitchen sinks: Replacing minimization with randomization in learning
Ali Rahimi and Benjamin Recht · 2009
Cited alongside, same era.
The spectral norm error of the naive Nyström extension
Alex Gittens · 2011
Cited alongside, same era.
Scikit-learn: Machine learning in Python
F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Prettenhofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and E. Duchesnay · 2011
Cited alongside, same era.
Fast approximation of matrix coherence and statistical leverage
Petros Drineas, Malik Magdon-Ismail, Michael W. Mahoney, and David P. Woodruff · 2012
Cited alongside, same era.
Fast randomized kernel ridge regression with statistical guarantees
Ahmed Alaoui and Michael W Mahoney · 2015
Later among the works it cites.
Dimensionality reduction for k-means clustering and low rank approximation
Michael B. Cohen, Sam Elder, Cameron Musco, Christopher Musco, and Madalina Persu · 2015
Later among the works it cites.
Fast relative-error approximation algorithm for ridge regression
Shouyuan Chen, Yang Liu, Michael Lyu, Irwin King, and Shengyu Zhang · 2015
Later among the works it cites.
Uniform sampling for matrix approximation
Michael B. Cohen, Yin Tat Lee, Cameron Musco, Christopher Musco, Richard Peng, and Aaron Sidford · 2015
Later among the works it cites.
Large-scale Nyström kernel matrix approximation using randomized SVD
Mu Li, Wei Bi, James T Kwok, and Bao-Liang Lu · 2015
Later among the works it cites.
Less is more: Nyström computational regularization
Alessandro Rudi, Raffaello Camoriano, and Lorenzo Rosasco · 2015
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Sanjiv Kumar, Mehryar Mohri, and Ameet Talwalkar · 2012
Cited alongside, same era.
Nyström method vs random Fourier features: A theoretical and empirical comparison
Tianbao Yang, Yu-feng Li, Mehrdad Mahdavi, Rong Jin, and Zhi-Hua Zhou · 2012
Cited alongside, same era.
Sharp analysis of low-rank kernel matrix approximations
Francis Bach · 2013
Cited alongside, same era.
Turning big data into tiny data: Constant-size coresets for k k -means, PCA, and projective clustering
Dan Feldman, Melanie Schmidt, and Christian Sohler · 2013
Cited alongside, same era.
Revisiting the Nyström method for improved large-scale machine learning
Alex Gittens and Michael Mahoney · 2013
Cited alongside, same era.
UCI machine learning repository, 2013
M. Lichman · 2013
Cited alongside, same era.
Fastfood - Computing Hilbert space expansions in loglinear time
Quoc Le, Tamás Sarlós, and Alexander Smola · 2013
Cited alongside, same era.
Later among the works it cites.
An introduction to matrix concentration inequalities
Joel A. Tropp · 2015
Later among the works it cites.
Randomized sketches for kernels: Fast and optimal non-parametric regression
Yun Yang, Mert Pilanci, and Martin J Wainwright · 2015
Later among the works it cites.
Optimal principal component analysis in distributed and streaming models
Christos Boutsidis, David P. Woodruff, and Peilin Zhong · 2016
Closest in time.
Analysis of Nyström method with sequential ridge leverage score sampling
Daniele Calandriello, Alessandro Lazaric, and Michal Valko · 2016
Closest in time.
Fast DPP sampling for Nyström with application to kernel methods
Chengtao Li, Stefanie Jegelka, and Suvrit Sra · 2016
Closest in time.
Feature selection for ridge regression with provable guarantees
Saurabh Paul and Petros Drineas · 2016
Closest in time.
Large scale kernel learning using block coordinate descent
Stephen Tu, Rebecca Roelofs, Shivaram Venkataraman, and Benjamin Recht · 2016
Closest in time.
On column selection in approximate kernel canonical correlation analysis
Weiran Wang · 2016
Closest in time.
Distributed adaptive sampling for kernel matrix approximation
Daniele Calandriello, Alessandro Lazaric, and Michal Valko · 2017
Closest in time.
Input sparsity time low-rank approximation via ridge leverage score sampling
Michael B. Cohen, Cameron Musco, and Christopher Musco · 2017
Closest in time.
Low-rank PSD approximation in input-sparsity time
Kenneth L. Clarkson and David P. Woodruff · 2017
Closest in time.
Probability and Computing: Randomization and Probabilistic Techniques in Algorithms and Data Analysis
Michael Mitzenmacher and Eli Upfal · 2017
Closest in time.