A review of Nyström methods for large-scale machine learning
Information FusionPublished 16 March 2015
Shiliang Sun, Jing Zhao, Jiang Zhu
Citations66
SJR quartileQ1
SJR score4.13
SNIP4.60
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
This paper introduces various Nystrom methods, reviews different sampling methods for the Nystrom method and summarize them from the perspectives of both theoretical analysis and practical performance, and discusses some open machine learning problems related to Nystrom Methods.
Abstract
Generating a low-rank matrix approximation is very important in large-scale machine learning applications. The standard Nyström method is one of the state-of-the-art techniques to generate such an approximation. It has got rapid developments since being applied to Gaussian process regression. Several enhanced Nyström methods such as ensemble Nyström, modified Nyström and SS-Nyström have been proposed. In addition, many sampling methods have been developed. In this paper, we review the Nyström methods for large-scale machine learning. First, we introduce various Nyström methods. Second, we review different sampling methods for the Nyström methods and summarize them from the perspectives of both theoretical analysis and practical performance. Then, we list several typical machine learning applications that utilize the Nyström methods. Finally, we make our conclusions after discussing some open machine learning problems related to Nyström methods.
Keywords
Computer ScienceEngineeringPhysics and Astronomy
IEEE Transactions on Pattern Analysis and Machine IntelligenceNormalized cuts and image segmentation
15,696 Citations2000Jianbo Shi, Jitendra Malik
ScienceA Global Geometric Framework for Nonlinear Dimensionality Reduction
13,740 Citations2000Joshua B. Tenenbaum, Vin de Silva +1 more
An approach to solving dimensionality reduction problems that uses easily measured local metric information to learn the underlying global geometry of a data set and efficiently computes a globally optimal solution, and is guaranteed to converge asymptotically to the true structure.
The MIT Press eBooksLearning with Kernels
9,548 Citations2001Bernhard Schölkopf, Alexander J. Smola
Learning with Kernels provides an introduction to SVMs and related kernel methods that provide all of the concepts necessary to enable a reader equipped with some basic mathematical knowledge to enter the world of machine learning using theoretically well-founded yet easy-to-use kernel algorithms.
On Spectral Clustering: Analysis and an algorithm
7,751 Citations2001Andrew Y. Ng, Michael I. Jordan +1 more
A simple spectral clustering algorithm that can be implemented using a few lines of Matlab is presented, and tools from matrix perturbation theory are used to analyze the algorithm, and give conditions under which it can be expected to do well.
IEEE Transactions on Pattern Analysis and Machine IntelligenceAn efficient k-means clustering algorithm: analysis and implementation
5,568 Citations2002Tapas Kanungo, David M. Mount +4 more
This work presents a simple and efficient implementation of Lloyd's k-means clustering algorithm, which it calls the filtering algorithm, and establishes the practical efficiency of the algorithm's running time.
Foundations of Computational MathematicsExact Matrix Completion via Convex Optimization
5,061 Citations2009Emmanuel J. Candès, Benjamin Recht
The MIT Press eBooksLaplacian Eigenmaps and Spectral Techniques for Embedding and Clustering
4,535 Citations2002Mikhail Belkin, Partha Niyogi
The algorithm provides a computationally efficient approach to nonlinear dimensionality reduction that has locality preserving properties and a natural connection to clustering.
Journal of the American Statistical AssociationLearning With Kernels: Support Vector Machines, Regularization, Optimization, and Beyond
4,326 Citations2003Christopher K. I. Williams
Learning with Kernels provides an introduction to SVMs and related kernel methods that provide all of the concepts necessary to enable a reader equipped with some basic mathematical knowledge to enter the world of machine learning using theoretically well-founded yet easy-to-use kernel algorithms.
SIAM ReviewFinding Structure with Randomness: Probabilistic Algorithms for Constructing Approximate Matrix Decompositions
3,942 Citations2011Nathan Halko, Per‐Gunnar Martinsson +1 more
This work surveys and extends recent research which demonstrates that randomization offers a powerful tool for performing low-rank matrix approximation, and presents a modular framework for constructing randomized algorithms that compute partial matrix decompositions.
Inverse ProblemsSparsity and incoherence in compressive sampling
2,074 Citations2007Emmanuel J. Candès, Justin Romberg
It is shown that ℓ1 minimization recovers x0 exactly when the number of measurements exceeds S, and μ is the largest entry in U properly normalized: .
IEEE Transactions on Pattern Analysis and Machine IntelligenceThe CMU pose, illumination, and expression database
1,779 Citations2003Terence Sim, Simon Baker +1 more
In the Fall of 2000, a database of more than 40,000 facial images of 68 people was collected using the Carnegie Mellon University 3D Room to imaged each person across 13 different poses, under 43 different illumination conditions, and with four different expressions.
Using the Nyström Method to Speed Up Kernel Machines
1,522 Citations2000Christopher K. I. Williams, Matthias Seeger
It is shown that an approximation to the eigendecomposition of the Gram matrix can be computed by the Nystrom method (which is used for the numerical solution of eigenproblems) and the computational complexity of a predictor using this approximation is O(m2n).
IEEE Transactions on Pattern Analysis and Machine IntelligenceSpectral grouping using the nystrom method
1,326 Citations2004Charless C. Fowlkes, Serge Belongie +2 more
The contribution of this paper is a method that substantially reduces the computational requirements of grouping algorithms based on spectral partitioning making it feasible to apply them to very large grouping problems.
Medical Entomology and ZoologyTemplates for the Solution of Algebraic Eigenvalue Problems: A Practical Guide
1,119 Citations1987James Demmel, Jack Dongarra +3 more
Edinburgh Research ExplorerMulti-task Gaussian Process Prediction
851 Citations2007Edwin V. Bonilla, Kian Ming A. Chai +1 more
A model that learns a shared covariance function on input-dependent features and a "free-form" covariance matrix over tasks allows for good flexibility when modelling inter-task dependencies while avoiding the need for large amounts of data for training.
Proceedings of the National Academy of SciencesCUR matrix decompositions for improved data analysis
806 Citations2009Michael W. Mahoney, Petros Drineas
An algorithm is presented that preferentially chooses columns and rows that exhibit high “statistical leverage” and exert a disproportionately large “influence” on the best low-rank fit of the data matrix, obtaining improved relative-error and constant-factor approximation guarantees in worst-case analysis, as opposed to the much coarser additive-error guarantees of prior work.
On the Nyström Method for Approximating a Gram Matrix for Improved Kernel-Based Learning
751 Citations2005Petros Drineas, Michael W. Mahoney
An algorithm to compute an easily-interpretable low-rank approximation to an n × n Gram matrix G such that computations of interest may be performed more rapidly.
Using the triangle inequality to accelerate k-means
658 Citations2003Charles Elkan
The accelerated k-means algorithm is shown how to accelerate dramatically, while still always computing exactly the same result as the standard algorithm, and is effective for datasets with up to 1000 dimensions, and becomes more and more effective as the number k of clusters increases.
Efficient svm training using low-rank kernel representations
595 Citations2002Shai Fine, Katya Scheinberg
This work shows that for a low rank kernel matrix it is possible to design a better interior point method (IPM) in terms of storage requirements as well as computational complexity and derives an upper bound on the change in the objective function value based on the approximation error and the number of active constraints (support vectors).
SIAM Journal on ComputingFast Monte Carlo Algorithms for Matrices II: Computing a Low-Rank Approximation to a Matrix
553 Citations2006Petros Drineas, Ravi Kannan +1 more
Two simple and intuitive algorithms are presented which compute a description of a low-rank approximation of a singular value decomposition (SVD) to an matrix of rank not greater than a specified rank, and which are qualitatively faster than the SVD.
SIAM Journal on Matrix Analysis and ApplicationsRelative-Error $CUR$ Matrix Decompositions
468 Citations2008Petros Drineas, Michael W. Mahoney +1 more
These two algorithms are the first polynomial time algorithms for such low-rank matrix approximations that come with relative-error guarantees; previously, in some cases, it was not even known whether such matrix decompositions exist.
PLoS GeneticsPCA-Correlated SNPs for Structure Identification in Worldwide Human Populations
304 Citations2007Peristera Paschou, Elad Ziv +5 more
A novel algorithm is presented that is effectively used for the analysis of admixed populations without having to trace the origin of individuals, and can be easily applied on large genome-wide datasets, facilitating the identification of population substructure, stratification assessment in multi-stage whole-genome association studies, and the study of demographic history in human populations.
Journal of Machine Learning ResearchFast approximation of matrix coherence and statistical leverage
299 Citations2012Petros Drineas, Malik Magdon‐Ismail +2 more
A randomized algorithm is proposed that takes as input an arbitrary n × d matrix A, with n ≫ d, and returns, as output, relative-error approximations to all n of the statistical leverage scores.
Improved Nyström low-rank approximation and error analysis
296 Citations2008Kai Zhang, Ivor W. Tsang +1 more
An error analysis that directly relates the Nyström approximation quality with the encoding powers of the landmark points in summarizing the data is presented, and the resultant error bound suggests a simple and efficient sampling scheme, the k-means clustering algorithm, for NyStröm low-rank approximation.
Sampling methods for the Nyström method
235 Citations2012Sanjiv Kumar, Mehryar Mohri +1 more
This work reports results of extensive experiments that provide a detailed comparison of various fixed and adaptive sampling techniques, and demonstrates the performance improvement associated with the ensemble Nystrom method when used in conjunction with either fixed or adaptive sampling schemes.
Kernel Independent Component Analysis
231 Citations2014Xianchuan Yu, Dan Hu +1 more
IEEE Transactions on Neural NetworksClustered Nyström Method for Large Scale Manifold Learning and Dimension Reduction
220 Citations2010Kai Zhang, James T. Kwok
The (non-probabilistic) error analysis justifies a “clustered Nyström method” that uses the k-means clustering centers as landmark points and can be applied to scale up a wide variety of algorithms that depend on the eigenvalue decomposition of kernel matrix.
Nyström Method vs Random Fourier Features: A Theoretical and Empirical Comparison
218 Citations2012Tianbao Yang, Yu-Feng Li +3 more
It is shown that when there is a large gap in the eigen-spectrum of the kernel matrix, approaches based on the Nystrom method can yield impressively better generalization error bound than random Fourier features based approach.
Large-scale manifold learning
208 Citations2008Ameet Talwalkar, Sanjiv Kumar +1 more
This paper addresses the computational challenges of nonlinear dimensionality reduction via Isomap and Laplacian Eigenmaps, using a graph containing about 18 million nodes and 65 million edges and shows that the Nystrom approximation is superior to the column-sampling method.
Fast Monte-Carlo algorithms for finding low-rank approximations
180 Citations2002Alan Frieze, Ramachandran Kannan +1 more
This paper develops an algorithm which is qualitatively faster provided the entries of the matrix are sampled according to a natural probability distribution and the algorithm takes time polynomial in k, 1//spl epsiv/, log(1//spl delta/) only, independent of m, n.
Matrix approximation and projective clustering via volume sampling
174 Citations2006Amit Deshpande, Luis Rademacher +2 more
arXiv (Cornell University)Fast approximation of matrix coherence and statistical leverage
170 Citations2011Petros Drineas, Malik Magdon‐Ismail +2 more
Proceedings of the National Academy of SciencesSpectral methods in machine learning and new strategies for very large datasets
161 Citations2009Mohamed-Ali Belabbas, Patrick J. Wolfe
Two new algorithms for the approximation of positive-semidefinite kernels based on the Nyström method are presented, each of which demonstrates the improved performance of the approach relative to existing methods.
arXiv (Cornell University)Improving CUR Matrix Decomposition and the Nyström Approximation via Adaptive Sampling
149 Citations2013Shusen Wang, Zhihua Zhang
On the Impact of Kernel Approximation on Learning Accuracy
127 Citations2010Corinna Cortes, Mehryar Mohri +1 more
Sampling Techniques for the Nystrom Method
116 Citations2009Sanjiv Kumar, Mehryar Mohri +1 more
This work presents novel experiments with several real world datasets, and suggests that uniform sampling without replacement, in addition to being more efficient both in time and space, produces more effective approximations.
Ensemble Nystrom Method
115 Citations2009Sanjiv Kumar, Mehryar Mohri +1 more
A new family of algorithms based on mixtures of Nystrom approximation, ensemble Nystrom algorithms, that yield more accurate low-rank approximations than the standard Nystrom method are introduced.
Making large-scale nyström approximation possible
87 Citations2010Mu Li, James T. Kwok +1 more
An accurate and scalable Nystrom scheme that first samples a large column subset from the input matrix, but then only performs an approximate SVD on the inner submatrix by using the recent randomized low-rank matrix approximation algorithms.
On sampling-based approximate spectral decomposition
86 Citations2009Sanjiv Kumar, Mehryar Mohri +1 more
This paper addresses the problem of approximate singular value decomposition of large dense matrices that arises naturally in many machine learning applications and proposes an efficient adaptive sampling technique to select informative columns from the original matrix.
Neural ComputationDensity-Weighted Nyström Method for Computing Large Kernel Eigensystems
77 Citations2008Kai Zhang, James T. Kwok
An efficient algorithm is proposed to enforce such weighting in practice, which has the same complexity as the original Nystrm method and hence is notably cheaper than several other alternatives.
Proceedings - International Conference on Pattern Recognition/Proceedings/International Conference on Pattern RecognitionMultitask learning for EEG-based biometrics
76 Citations2008Shiliang Sun
Experimental results on EEG-based personal identification show the effectiveness of the proposed multitask learning approach to biometrics based on electroencephalogram signals.
Time and space efficient spectral clustering via column sampling
68 Citations2011Mu Li, Xiaochen Lian +2 more
This paper proposes a time- and space-efficient spectral clustering algorithm which can scale to very large data sets and applies it to the task of image segmentation.
arXiv (Cornell University)Near-Optimal Column-Based Matrix Reconstruction
66 Citations2011Christos Boutsidis, Petros Drineas +1 more
Applied IntelligenceMulti-view Laplacian twin support vector machines
63 Citations2014Xijiong Xie, Shiliang Sun
Inspired by the recent success of multi-view learning, this paper proposes multi-View Laplacian twin support vector machines, whose dual optimization problems are quadratic programming problems, and extends them to kernel multi- view LaplACian twin Support vector machines.
Large-scale SVD and manifold learning
61 Citations2013Ameet Talwalkar, Sanjiv Kumar +2 more
Memory Efficient Kernel Approximation
54 Citations2014Si Si, Cho‐Jui Hsieh +1 more
arXiv (Cornell University)The spectral norm error of the naive Nystrom extension
51 Citations2011Alex Gittens
This paper provides the first relative-error bound on the spectral norm error incurred in this process, which follows from a natural connection between the Nystrom extension and the column subset selection problem.
Near Optimal Column-Based Matrix Reconstruction
50 Citations2011Christos Boutsidis, Petros Drineas +1 more
Academic press library in signal processingKernel Methods and Support Vector Machines
38 Citations2014John Shawe‐Taylor, Shiliang Sun
The aim of this article is to promote the applications and developments of kernel methods through the detailed survey of some important kernel techniques.
NeurocomputingMultitask centroid twin support vector machines
37 Citations2014Xijiong Xie, Shiliang Sun
Inspired by the recent success of multitask learning which trains multiple related tasks simultaneously, the proposed centroid twin support vector machines are extended to the multitasking learning scenario and proposed multitask centroid Twin Support vector machines.
Fast embedding of sparse music similarity graphs
35 Citations2003John Platt
This paper applies fast sparse multidimensional scaling (MDS) to a large graph of music similarity, with 267K vertices that represent artists, albums, and tracks; and 3.22M edges that represent similarity between those entities.
Lecture notes in computer scienceVariational Dependent Multi-output Gaussian Process Dynamical Systems
33 Citations2014Jing Zhao, Shiliang Sun
The proposed model has superiority on modeling dynamical systems under the more reasonable assumption and the fully Bayesian learning framework and can be flexibly extended to handle regression problems.
A novel greedy algorithm for Nyström approximation
28 Citations2011Ahmed Farahat, Ali Ghodsi +1 more
A novel recursive algorithm for calculating the Nystrom approximation, and an effective greedy criterion for column selection are presented, and a very efficient variant is proposed for greedy sampling, which works on random partitions of data instances.
Data Mining and Knowledge DiscoveryFast density-weighted low-rank approximation spectral clustering
26 Citations2010Fanhua Shang, Licheng Jiao +3 more
A density-weighted low-rank approximation spectral clustering algorithm to operate those representative exemplars on the global underlying structure of data manifold and outperforms the state-of-the-art spectral clusters and original AP algorithms in terms of speed, memory usage, and quality.
Scientific Repository (Petra Christian University)Observations on the Nyström Method for Gaussian Process Prediction
26 Citations2002C.S. Jr. Williams, CE Rasmussen +2 more
Neural Information Processing SystemsFast Embedding of Sparse Similarity Graphs
24 Citations2003John Platt
This paper applies fast sparse multidimensional scaling (MDS) to a large graph of music similarity, with 267K vertices that represent artists, albums, and tracks; and 3.22M edges that represent similarity between those entities.
Nonlinear Combination of Multiple Kernels for Support Vector Machines
20 Citations2010Jinbo Li, Shiliang Sun
This paper proposes SVMs based on the nonlinear combination of multiple kernels (NCMK) which surmounts the drawback of previous MKL by the potential to exploit more information and shows that the method can be formulated as a semi-definite programming (SDP) problem then solved by interior-point algorithms.
On sparse representations of linear operators and the approximation of matrix products
20 Citations2008Mohamed-Ali Belabbas, Patrick J. Wolfe
This paper represents a linear operator by a sum of rank-one operators, and shows how a sparse representation that guarantees a low approximation error for the product can be obtained from analyzing an induced quadratic form.
Can matrix coherence be efficiently and accurately estimated
20 Citations2011Mehryar Mohri, Ameet Talwalkar
A novel sampling-based algorithm for estimating coherence is introduced, associated estimation guarantees are presented and the results of extensive experiments for coherence estimation are reported, revealing the extent to which coherence assumptions made in a number of recent machine learning publications are testable.
Philosophical Transactions of the Royal Society A Mathematical Physical and Engineering SciencesOn landmark selection and sampling in high-dimensional data analysis
17 Citations2009Mohamed-Ali Belabbas, Patrick J. Wolfe
This work provides an introduction to spectral methods for linear and nonlinear dimension reduction, emphasizing ways to overcome the computational limitations currently faced by practitioners with massive datasets.
Infinite mixtures of multivariate Gaussian processes
16 Citations2013Shiliang Sun
A new model called the infinite mixture of multivariate Gaussian processes, which can be used to learn vector-valued functions and applied to multitask learning, is presented.
arXiv (Cornell University)Improving CUR Matrix Decomposition and the Nystr\"{o}m Approximation via Adaptive Sampling
15 Citations2013Shusen Wang, Zhihua Zhang
Tangent space intrinsic manifold regularization for data representation
13 Citations2013Shiliang Sun
A new regularization method called tangent space intrinsic manifold regularization is presented, which is intrinsic to data manifold and favors linear functions on the manifold and Experimental results including comparisons with state-of-the-art techniques show the effectiveness of the proposed method.
The Astronomical JournalOBJECTIVE IDENTIFICATION OF INFORMATIVE WAVELENGTH REGIONS IN GALAXY SPECTRA
12 Citations2014Ching-Wa Yip, Michael W. Mahoney +5 more
IEEE/SP 13th Workshop on Statistical Signal Processing, 2005A signal processing application of randomized low-rank approximations
10 Citations2005Peter A. Parker, Patrick J. Wolfe +1 more
Quantitative simulation results are provided to indicate that near-optimal nulling performance, as measured in terms of signal-to-interference-plus-noise ratio, may be achieved via straightforward modifications of the randomized algorithms described above.
Machine LearningThe matrix ridge approximation: algorithms and applications
9 Citations2014Zhihua Zhang
Empirical studies in spectral clustering and Gaussian process regression show that the matrix ridge approximation with the EM iteration is potentially useful.
NeurocomputingA novel multiple Nyström-approximating kernel discriminant analysis
9 Citations2013Zhe Wang, Wenbo Jie +1 more
The experimental results show that the proposed Multiple Nystrom-Approximating Kernel Discriminant Analysis (MNKDA) can achieve an effective and efficient performance than the classical MKDA.
Single-task and multitask sparse Gaussian processes
8 Citations2013Jiang Zhu, Shiliang Sun
Experimental results show that the single-task sparse Gaussian processes are comparable to one state-of-the-art method, and the multitask sparsity regularizer can generate multitask sparseGaussian processes which are more effective than those obtained from other methods.
Efficient Algorithms and Error Analysis for the Modified Nystrom Method
8 Citations2014Shusen Wang, Zhihua Zhang
This paper proposes a simple column selection algorithm that is more efficient and easier to implement than and nearly as accurate as the state-of-the-art algorithm and establishes a lower error bound for the modified Nystr\"om method.
arXiv (Cornell University)The Modified Nystrom Method: Theories, Algorithms, and Extension.
6 Citations2014Shusen Wang, Luo Luo +1 more
Tests on real-world datasets demonstrate that the proposed column selection algorithm is both efficient and accurate and that the SS-Nystr\"om method always leads to much higher kernel approximation accuracy than the standard/modified Nystr \"om method.
Adaptive beamforming using fast low-rank covariance matrix approximations
5 Citations2008Daniel N. Spendley, Patrick J. Wolfe
Simulation results demonstrate that the latter method, explicitly designed for the efficient approximation of symmetric positive semi-definite matrices, yields performance and robustness characteristics that offer encouragement for its use in practical beamforming applications.
Mathematical Problems in EngineeringSemisupervised Tangent Space Discriminant Analysis
3 Citations2015Yang Zhou, Shiliang Sun
A new regularizer using tangent spaces is developed, which not only can capture the local manifold structure from both labeled and unlabeled data, but also has the complementarity with the Laplacian regularizer.
…