The Unreasonable Effectiveness of Structured Random Orthogonal Embeddings

Abstract

We examine a class of embeddings based on structured random matrices with orthogonal rows which can be applied in many machine learning applications including dimensionality reduction and kernel approximation. For both the Johnson-Lindenstrauss transform and the angular kernel, we show that we can select matrices yielding guaranteed improved performance in accuracy and/or speed compared to earlier methods. We introduce matrices with complex entries which give significant further accuracy improvement. We provide geometric and Markov chain-based perspectives to help understand the benefits, and empirical results which suggest that the approach is helpful in a wider range of applications.

References in corpus (2)

• Orthogonal Random Features
• Structured adaptive and random spinners for fast machine learning computations

Cited by in corpus (20)

• Rethinking Attention with Performers
• A Theoretical Perspective on Hyperdimensional Computing
• Generalisation error in learning with random features and the hidden manifold model
• Compressing RNNs for IoT devices by 15-38x using Kronecker Products
• Masked Language Modeling for Proteins via Linearly Scalable Long-Context Transformers
• Random Features for Kernel Approximation: A Survey on Algorithms, Theory, and Beyond
• Reservoir Computing meets Recurrent Kernels and Structured Transforms
• Billion-scale Network Embedding with Iterative Random Projection
• Fast Learning in Reproducing Kernel Krein Spaces via Signed Measures
• Improved Subsampled Randomized Hadamard Transform for Linear SVM
• Structured Monte Carlo Sampling for Nonisotropic Distributions via Determinantal Point Processes
• Unlocking Pixels for Reinforcement Learning via Implicit Attention
• On Learning the Transformer Kernel
• Manifold Regularization for Kernelized LSTD
• Towards a Unified Quadrature Framework for Large-Scale Kernel Machines
• Revisiting RIP guarantees for sketching operators on mixture models
• Demystifying Orthogonal Monte Carlo and Beyond
• Optimal Iterative Sketching with the Subsampled Randomized Hadamard Transform
• Complex-to-Real Sketches for Tensor Products with Applications to the Polynomial Kernel
• Sublinear Maximum Inner Product Search using Concomitants of Extreme Order Statistics