Block basis factorization for scalable kernel evaluation
From MaRDI portal
Abstract: Kernel methods are widespread in machine learning; however, they are limited by the quadratic complexity of the construction, application, and storage of kernel matrices. Low-rank matrix approximation algorithms are widely used to address this problem and reduce the arithmetic and storage cost. However, we observed that for some datasets with wide intra-class variability, the optimal kernel parameter for smaller classes yields a matrix that is less well approximated by low-rank methods. In this paper, we propose an efficient structured low-rank approximation method -- the Block Basis Factorization (BBF) -- and its fast construction algorithm to approximate radial basis function (RBF) kernel matrices. Our approach has linear memory cost and floating-point operations for many machine learning kernels. BBF works for a wide range of kernel bandwidth parameters and extends the domain of applicability of low-rank approximation methods significantly. Our empirical results demonstrate the stability and superiority over the state-of-art kernel approximation algorithms.
Recommendations
Cites work
- A Fast ULV Decomposition Solver for Hierarchically Semiseparable Representations
- A fast algorithm for particle simulations
- A fast block low-rank dense solver with applications to finite-element matrices
- A fast directional algorithm for high frequency acoustic scattering in two dimensions
- A kernel-independent adaptive fast multipole algorithm in two and three dimensions
- A sparse \({\mathcal H}\)-matrix arithmetic. II: Application to multi-dimensional problems
- A sparse matrix arithmetic based on \({\mathfrak H}\)-matrices. I: Introduction to \({\mathfrak H}\)-matrices
- Butterfly factorization
- Data-sparse approximation by adaptive \({\mathcal H}^2\)-matrices
- Efficient Algorithms for Computing a Strong Rank-Revealing QR Factorization
- Fast algorithms for hierarchically semiseparable matrices
- Fast approximation of matrix coherence and statistical leverage
- Finding structure with randomness: probabilistic algorithms for constructing approximate matrix decompositions
- Hierarchically compositional kernels for scalable nonparametric learning
- scientific article; zbMATH DE number 1069612 (Why is no real title available?)
- scientific article; zbMATH DE number 6781341 (Why is no real title available?)
- scientific article; zbMATH DE number 961607 (Why is no real title available?)
- Improving multifrontal methods by means of block low-rank representations
- Kernel methods for the approximation of nonlinear systems
- Methods of conjugate gradients for solving linear systems
- Multidimensional butterfly factorization
- On the Compression of Low Rank Matrices
- On the numerical rank of radial basis function kernels in high dimensions
- On the Nyström method for approximating a gram matrix for improved kernel-based learning
- Randomized Algorithms for Matrices and Data
- Randomized algorithms for the low-rank approximation of matrices
- Revisiting the Nyström method for improved large-scale machine learning
- Solution of Sparse Indefinite Systems of Linear Equations
- The black-box fast multipole method
- The Fast Gauss Transform
- The Fast Multipole Method I: Error Analysis and Asymptotic Complexity
- The fast multipole method: Numerical implementation
Cited in
(8)- Scalable Gaussian Process Computations Using Hierarchical Matrices
- Learning low-rank kernel matrices with column-based methods
- Fast and Accurate Gaussian Kernel Ridge Regression Using Matrix Decompositions for Preconditioning
- Structured Matrix Approximations via Tensor Decompositions
- Hierarchical matrix approximation for kernel-based scattered data interpolation
- Kernel Approximation on Algebraic Varieties
- Training very large scale nonlinear SVMs using alternating direction method of multipliers coupled with the hierarchically semi-separable kernel approximations
- Distributed-memory \(\mathcal{H}\)-matrix algebra. I: Data distribution and matrix-vector multiplication
This page was built for publication: Block basis factorization for scalable kernel evaluation
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5203970)
