The Unreasonable Effectiveness of Structured Random Orthogonal Embeddings

2017/03/02 by Choromanski, Krzysztof, Rowland, Mark, Weller, Adrian · 3 citations
#Computation (stat.CO) #FOS: Computer and information sciences #Machine Learning (stat.ML)

paper · doi:10.48550/arxiv.1703.00864

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.

Cited by

• Sketch-Augmented Features Improve Learning Long-Range Dependencies in Graph Neural Networks
• RACE Attention: A Strictly Linear-Time Attention Layer for Training on Outrageously Large Contexts
• Random Projection Flows for Efficient Manifold Density Estimation

Related

• Fast nonlinear embeddings via structured matrices
• Orthogonal Random Features
• Random Embeddings with Optimal Accuracy
• Faster Linear Algebra Algorithms with Structured Random Matrices
• Binary embeddings with structured hashed projections