Improved Fixed-Rank Nyström Approximation via QR Decomposition: Practical and Theoretical Aspects
arXiv:1708.03218 · doi:10.1016/j.neucom.2019.06.070
Abstract
The Nystrom method is a popular technique that uses a small number of landmark points to compute a fixed-rank approximation of large kernel matrices that arise in machine learning problems. In practice, to ensure high quality approximations, the number of landmark points is chosen to be greater than the target rank. However, for simplicity the standard Nystrom method uses a sub-optimal procedure for rank reduction. In this paper, we examine the drawbacks of the standard Nystrom method in terms of poor performance and lack of theoretical guarantees. To address these issues, we present an efficient modification for generating improved fixed-rank Nystrom approximations. Theoretical analysis and numerical experiments are provided to demonstrate the advantages of the modified method over the standard Nystrom method. Overall, the aim of this paper is to convince researchers to use the modified method, as it has nearly identical computational complexity, is easy to code, has greatly improved accuracy in many cases, and is optimal in a sense that we make precise.
arXiv commentAccepted in Neurocomputing. arXiv admin note: text overlap with arXiv:1612.06470
References in corpus (11)
- Fast approximation of matrix coherence and statistical leverage
- Practical sketching algorithms for low-rank matrix approximation
- Recursive Sampling for the Nyström Method
- Sharp analysis of low-rank kernel matrix approximations
- Linearized Kernel Dictionary Learning
- Scalable Kernel K-Means Clustering with Nystrom Approximation: Relative-Error Bounds
- Compact Random Feature Maps
- Fast DPP Sampling for Nyström with Application to Kernel Methods
- Convex Formulation for Kernel PCA and its Use in Semi-Supervised Learning
- Fixed-Rank Approximation of a Positive-Semidefinite Matrix from Streaming Data
- Towards More Efficient SPSD Matrix Approximation and CUR Matrix Decomposition
Cited by in corpus (5)
- Rapid Robust Principal Component Analysis: CUR Accelerated Inexact Low Rank Estimation
- Scalable Spectral Clustering with Nystrom Approximation: Practical and Theoretical Aspects
- Perturbations of CUR Decompositions
- CUR Decompositions, Approximations, and Perturbations
- Stability of Sampling for CUR Decompositions