Compact Random Feature Maps
arXiv:1312.4626
Abstract
Kernel approximation using randomized feature maps has recently gained a lot of interest. In this work, we identify that previous approaches for polynomial kernel approximation create maps that are rank deficient, and therefore do not utilize the capacity of the projected feature space effectively. To address this challenge, we propose compact random feature maps (CRAFTMaps) to approximate polynomial kernels more concisely and accurately. We prove the error bounds of CRAFTMaps demonstrating their superior kernel reconstruction performance compared to the previous approximation schemes. We show how structured random matrices can be used to efficiently generate CRAFTMaps, and present a single-pass algorithm using CRAFTMaps to learn non-linear multi-class classifiers. We present experiments on multiple standard data-sets with performance competitive with state-of-the-art results.
9 pages
Cited by in corpus (19)
- Randomized Nonlinear Component Analysis
- Quasi-Monte Carlo Feature Maps for Shift-Invariant Kernels
- How to Scale Up Kernel Methods to Be As Good As Deep Neural Nets
- Compact Nonlinear Maps and Circulant Extensions
- Large-Scale Approximate Kernel Canonical Correlation Analysis
- Learnable Fourier Features for Multi-Dimensional Spatial Positional Encoding
- Improved Fixed-Rank Nyström Approximation via QR Decomposition: Practical and Theoretical Aspects
- Randomized Numerical Linear Algebra: Foundations & Algorithms
- Random Features for Kernel Approximation: A Survey on Algorithms, Theory, and Beyond
- Scalable Nonlinear Learning with Adaptive Polynomial Expansions
- Relative Error Embeddings for the Gaussian Kernel Distance
- Faster Kernel Ridge Regression Using Sketching and Preconditioning
- Data Dependent Kernel Approximation using Pseudo Random Fourier Features
- Fast Landmark Subspace Clustering
- Sampled Softmax with Random Fourier Features
- Low-dimensional Interpretable Kernels with Conic Discriminant Functions for Classification
- Random Feature Maps via a Layered Random Projection (LaRP) Framework for Object Classification
- Learning Random Fourier Features by Hybrid Constrained Optimization
- Action Recognition with Kernel-based Graph Convolutional Networks