Improved Nyström low-rank approximation and error analysis

By Kai Zhang, Ivor Wai-Hung Tsang, James T. Kwok. International Conference on Machine Learning, 2008

349 citations recorded by the source corpus.

Subfields: Atomic and Molecular Physics, and Optics, Computational Mathematics, Computational Mechanics

View Paper: https://www.semanticscholar.org/paper/ed2f7914bf51168842f33618d50f1e5f21622548

How researchers see this paper

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

In Atomic and Molecular Physics, and Optics

In Computational Mathematics

In Computational Mechanics

Citations in the corpus

Large-scale manifold learning (2008, background): “More recently it has been studied for a variety of kernel-based algorithms and other algorithms involving symmetric positive semidefinite matrices (Williams & Seeger, 2000; Fine & Scheinberg, 2002; Fowlkes et al., 2004; Drineas & Mahoney, 2005; Karsmakers et al., 2007; Zhang et al., 2008; Kumar et a”
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.”
Covariate Shift in Hilbert Space: A Solution via Sorrogate Kernels (2013, background): “An interesting topic is how to choose useful landmark points to compute the surrogate kernel for model adaptation, based on sampling or clustering like in (Zhang et al., 2008).”
Parallel Spectral Clustering in Distributed Systems (2011, background): “Several papers (e.g., [32], [ 54 ]) have developed advanced sampling techniques, which can”
Nyström Method vs Random Fourier Features: A Theoretical and Empirical Comparison (2012, methodology): “We note that the empirical performance of the Nyström method may be improved by using a different implementation [21, 11].”
Nyströmformer: A Nystöm-based Algorithm for Approximating Self-Attention (2021, methodology): “Many variants such as Nystr¨om with k -means (Zhang, Tsang, and Kwok 2008; Zhang and Kwok 2010), randomized Nystr¨om (Li, Kwok, and L¨u 2010), Nystr¨om with spectral shift (Wang et al. 2014), Nystr ¨ om with pseudo landmarks, prototype method (Wang and Zhang 2013; Wang, Zhang, and Zhang 2016),…”
End-to-End Kernel Learning with Supervised Convolutional Kernel Networks (2016, methodology): “To perform end-to-end learning given labeled data, we use a simple but effective principle consisting of learning discriminative subspaces in RKHSs, where we project data.”
Learning Semantic Image Representations at a Large Scale (2014, background): “Nyström sampling methods suggests that more data-dependent feature selection approaches, notably K-means, works better than completely randomly sampling features [123, 67], while the theoretical bound still applies to these scenarios.”
Large Scale Spectral Clustering Via Landmark-Based Sparse Representation (2015, methodology): “[40] provide an error analysis of this method and use k-means to sample the sub-matrix.”
Matrix Coherence and the Nystrom Method (2010, methodology): “The Nystr¨om method has been shown to work well in practice for various applications ranging from manifold learning to image segmentation (Fowlkes et al. , 2004; Platt, 2004; Talwalkar et al. , 2008; Zhang et al. , 2008).”
Sampling Methods for the Nyström Method (2012, positive): “Although previous studies have compared uniform and non-uniform distributions in a more restrictive setting (Drineas et al., 2001; Zhang et al., 2008), our results are the first to compare uniform sampling with the sampling technique for which the Nyström method has theoretical guarantees.”
Memory Efficient Kernel Approximation (2014, methodology): “, 2009), Nyström with kmeans to obtain benchmark points (Zhang et al., 2008; Zhang & Kwok, 2010), and randomized Nyström (Li et al.”
Improved Bounds for the Nyström Method With Application to Kernel Classification (2011, methodology): “trict the analysis to the uniform sampling for the Nystr¨om method. Although diﬀerent sampling approaches have been suggested for 1 the Nystr¨om method (Drineas and Mahoney, 2005; Kumar et al., 2009; Zhang et al., 2008; Belabbas and Wolfe, 2009), according to (Kumar et al., 2009), for real-world dat”