Improving CUR Matrix Decomposition and the Nyström Approximation via Adaptive Sampling

Abstract

The CUR matrix decomposition and the Nyström approximation are two important low-rank matrix approximation techniques. The Nyström method approximates a symmetric positive semidefinite matrix in terms of a small number of its columns, while CUR approximates an arbitrary data matrix by a small number of its columns and rows. Thus, CUR decomposition can be regarded as an extension of the Nyström approximation. In this paper we establish a more general error bound for the adaptive column/row sampling algorithm, based on which we propose more accurate CUR and Nyström algorithms with expected relative-error bounds. The proposed CUR and Nyström algorithms also have low time complexity and can avoid maintaining the whole data matrix in RAM. In addition, we give theoretical analysis for the lower error bounds of the standard Nyström method and the ensemble Nyström method. The main theoretical results established in this paper are novel, and our analysis makes no special assumption on the data matrices.

References in corpus (2)

• Fast approximation of matrix coherence and statistical leverage
• CUR from a Sparse Optimization Viewpoint

Cited by in corpus (51)

• Sketching as a Tool for Numerical Linear Algebra
• Randomized Matrix Decompositions using R
• Scalable Kernel K-Means Clustering with Nystrom Approximation: Relative-Error Bounds
• Randomized Nonnegative Matrix Factorization
• Robust CUR Decomposition: Theory and Imaging Applications
• Less is More: Nyström Computational Regularization
• Stochastic Gradient Descent, Weighted Sampling, and the Randomized Kaczmarz algorithm
• Nyströmformer: A Nyström-Based Algorithm for Approximating Self-Attention
• A Practical Guide to Randomized Matrix Computations with MATLAB Implementations
• CUR Algorithm for Partially Observed Matrices
• SPSD Matrix Approximation vis Column Selection: Theories, Algorithms, and Extensions
• Fast Parallel Randomized QR with Column Pivoting Algorithms for Reliable Low-rank Matrix Approximations
• A literature survey of matrix methods for data science
• Provably Correct Algorithms for Matrix Column Subset Selection with Selectively Sampled Data
• Towards More Efficient SPSD Matrix Approximation and CUR Matrix Decomposition
• The Singular Value Decomposition, Applications and Beyond
• Single-Pass PCA of Large High-Dimensional Data
• Compression Approaches for the Regularized Solutions of Linear Systems from Large-Scale Inverse Problems
• Mode-wise Tensor Decompositions: Multi-dimensional Generalizations of CUR Decompositions
• Near-Optimal Discrete Optimization for Experimental Design: A Regret Minimization Approach
• An Explicit Sampling Dependent Spectral Error Bound for Column Subset Selection
• Efficient Algorithms and Error Analysis for the Modified Nystrom Method
• Interpolation-Based Model Order Reduction for Polynomial Parametric Systems
• oASIS: Adaptive Column Sampling for Kernel Matrix Approximation
• Feature space approximation for kernel-based supervised learning
• Parallel MMF: a Multiresolution Approach to Matrix Computation
• Generic Coreset for Scalable Learning of Monotonic Kernels: Logistic Regression, Sigmoid and more
• Graph reduction with spectral and cut guarantees
• Superfast CUR Matrix Algorithms, Their Pre-Processing and Extensions
• Simple and Almost Assumption-Free Out-of-Sample Bound for Random Feature Mapping
• Data-driven Random Fourier Features using Stein Effect
• CUR Low Rank Approximation at Deterministic Sublinear Cost
• Modern Subsampling Methods for Large-Scale Least Squares Regression
• Relating Leverage Scores and Density using Regularized Christoffel Functions
• A Simple Approach to Optimal CUR Decomposition
• Accumulation of Sub-Sampling Matrices with Applications to Statistical Computation
• Empirical Evaluation of Kernel PCA Approximation Methods in Classification Tasks
• Incomplete Pivoted QR-based Dimensionality Reduction
• Quadruply Stochastic Gaussian Processes
• CUR Decompositions, Approximations, and Perturbations
• Fast Generalized Matrix Regression with Applications in Machine Learning
• Quantum Machine Learning For Classical Data
• Geometric Interpretation of Running Nyström-Based Kernel Machines and Error Analysis
• Gaussian Process Landmarking on Manifolds
• Bayesian Variable Selection for Single Index Logistic Model
• A theory of meta-factorization
• On Subspace Approximation and Subset Selection in Fewer Passes by MCMC Sampling
• Tighter bound of Sketched Generalized Matrix Approximation
• Seeing the Forest from the Trees in Two Looks: Matrix Sketching by Cascaded Bilateral Sampling
• Learning Hierarchical Feature Space Using CLAss-specific Subspace Multiple Kernel -- Metric Learning for Classification
• Large-scale Kernel Methods and Applications to Lifelong Robot Learning