Sampling Methods for the Nyström Method

By Sanjiv Kumar, Mehryar Mohri, Ameet Talwalkar. 2012

364 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

Less is More: Nyström Computational Regularization (2015, background): “Extensive experimental analysis shows that the considered approach achieves state of the art performances on benchmark large scale datasets.”
Memory Efficient Kernel Approximation (2014, methodology): “Diﬀerent Nystr¨om sampling strategies are analyzed and compared in (Kumar, Mohri, and Talwalkar, 2012; Gittens and Mahoney, 2013).”
Learning Semantic Image Representations at a Large Scale (2014, methodology): “The implication of linking Nyström sampling theory to current learning pipelines has several immediate consequences: first, it clarifies why random sampling or K-means produce very reasonable dictionaries that are able to perform well in terms of classification accuracy [123, 19, 67]; more important”
Comprehensive analysis of single cell ATAC-seq data with SnapATAC (2021, methodology): “To improve the scalability of SnapATAC, an ef ﬁ cient technique to generate low-rank matrix approximations — the Nyström method 21 — is used to generate the low-rank embedding for large-scale datasets (Methods section).”
Improved Bounds for the Nyström Method With Application to Kernel Classification (2011, unknown): “In order to exploit the compressive sensing theory (Cand´es and Romberg, 2007), we introduce the deﬁnition of the coherence µ for the eigevenvector matrix Intuitively, the coherence measures the degree to which the eigenvectors in V are correlated with the canonical bases.”
Covariate Shift in Hilbert Space: A Solution via Sorrogate Kernels (2013, unknown): “, 2008)(Kumar et al., 2012).”
On the Global Optima of Kernelized Adversarial Representation Learning (2019, methodology): “, CIFAR-100), the Nyström method with data sampling [18] can be adopted.”
From Dependence to Causation (2016, methodology): “, wm} is a subset of the data {xi}i=1 sampled at random, or m representative data prototypes computed using a clustering algorithm (Kumar et al., 2012).”
Revisiting the Nystrom Method for Improved Large-scale Machine Learning (2013, methodology): “(Kumar et al., 2012) Ω(1) opt2 + O( 2n √ ` ) ‖A‖2 optF + O(n( k ` ) ) ‖A‖2 – this work, Lemma 4 Ω ( μk ln k (1− )2 ) opt2(1 + n ` ) optF + O( )opt? opt?(1 + O( −1))”
Local Group Invariant Representations via Orbit Embeddings (2016, background): “Several schemes for identifying the landmark points have been studied in the literature, including random sampling, sampling based on leverage scores, and clustering based landmark selection [19,21].”
Auditing Deep Learning processes through Kernel-based Explanatory Models (2019, result): “Note that, while any sampling policy for landmarks is admissible, in (Kumar et al., 2012) it is demonstrated that uniform sampling without replacement achieves results comparable with alternative, more resource-consuming policies.”
Federated Kernelized Multi-Task Learning (2018, methodology): “Succinctly, a rank-l approximation of K could be constructed via the Nyström method [9] with l cluster centers of the original columns (which could be done once centrally).”