The Unreasonable Effectiveness of Structured Random Orthogonal Embeddings

By Krzysztof Marcin Choromanski, Mark Rowland, Adrian Weller. 2017

92 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition, Representation & Self-Supervised Learning

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Vision and Pattern Recognition

In Representation & Self-Supervised Learning

Citations in the corpus

Rethinking Attention with Performers (2020, methodology): “…applications, including regular attention), instead of sampling ω i independently, we can use orthogonal random features (ORF) (Yu et al., 2016; Choromanski et al., 2017; 2018b): these maintain the marginal distributions of samples ω i while enforcing that different samples are orthogonal.”
Masked Language Modeling for Proteins via Linearly Scalable Long-Context Transformers (2020, methodology): “2.4, we know that if instead we use G-ORFs, then space complexity is reduced to O ( M log( d ) + Ld + ML ) and if the H-ORFs mechanism is used, then space is further reduced to O ( M + Ld + ML ) = O ( Ld + ML ) .”
Optimizing Simulations with Noise-Tolerant Structured Exploration (2018, background): “We conjecture that the fact that the above structured estimators are particularly good follows from their low variance and might be related to the recent discovery that certain kernel estimators based on structured orthogonal matrices strictly outperform accuracy-wise their baseline counterparts bui”
Orthogonal Estimation of Wasserstein Distances (2019, methodology): “These random matrices have been used as computationally cheap alternatives to exact sampling from UnifOrt( S d − 1 ; d ) in a variety of applications recently; see e.g. (Choromanski et al., 2017; Andoni et al., 2015).”
Initialization matters: Orthogonal Predictive State Recurrent Neural Networks (2018, methodology): “This “downstream” application of RFs goes beyond the results proven in Yu et al. (2016) and Choromanski et al. (2017).”
Demystifying Orthogonal Monte Carlo and Beyond (2020, methodology): “OMC relies on ensembles of mutually orthogonal random samples for variance reduction and turns out to be very effective in virtually all applications of MC in machine learning involving isotropic distributions [36, 11, 18, 14, 35].”
Hybrid Random Features (2021, methodology): “…Carlo (QMC) methods, where directions and/or lengths of Gaussian vectors used to produce features are correlated, often through geometric conditions such as orthogonality (Choromanski et al., 2017; Rowland et al., 2018; Yu et al., 2016; Choromanski et al., 2019; Choromanski & Sindhwani, 2016).”
Unifying Orthogonal Monte Carlo Methods (2019, methodology): “The comparison between the MSE associated with the base and Kac’s random walk estimators follows straightforwardly from the MSE expression for the base estimator in Choromanski et al. (2017).”
Compressing RNNs for IoT devices by 15-38x using Kronecker Products (2019, methodology): “KPs have also been used for orthogonal projections for dimensionality reduction of input matrices (Zhang et al., 2015; Choromanski et al., 2017), which is orthogonal to the present work.”
The Geometry of Random Features (2018, methodology): “These techniques also often lead to faster routines for the RFM computation if they can be discretized (Choromanski et al., 2017), yielding triple win improvements in accuracy, speed and space complexity.”