Orthogonal Random Features

By Felix X. Yu, Ananda Theertha Suresh, Krzysztof Marcin Choromanski, Daniel Niels Holtmann-Rice, Sanjiv Kumar. 2016

247 citations recorded by the source corpus.

We present an intriguing discovery related to Random Fourier Features: replacing multiplication by a random Gaussian matrix with multiplication by a properly scaled random orthogonal matrix significantly decreases kernel approximation error. We call this technique Orthogonal Random Features (ORF), and provide theoretical and empirical justification for its effectiveness. Motivated by the discovery, we further propose Structured Orthogonal Random Features (SORF), which uses a class of structured discrete orthogonal matrices to speed up the computation. The method reduces the time cost from $\mathcal{O}(d^2)$ to $\mathcal{O}(d \log d)$, where $d$ is the data dimensionality, with almost no compromise in kernel approximation quality compared to ORF. Experiments on several datasets verify the effectiveness of ORF and SORF over the existing methods. We also provide discussions on using the same type of discrete orthogonal structure for a broader range of kernels and applications.

Subfields: Computer Vision and Pattern Recognition, Representation & Self-Supervised Learning, Statistical Learning Theory

How researchers see this paper

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

In Computer Vision and Pattern Recognition

In Representation & Self-Supervised Learning

In Statistical Learning Theory

Citations in the corpus

Federated Learning: Strategies for Improving Communication Efficiency (2016, methodology): “In this work, we use a type of structured rotation matrix which is the product of a Walsh-Hadamard matrix and a binary diagonal matrix, motivated by the recent advance in this topic [21].”
Rethinking Attention with Performers (2020, methodology): “If we need m > d , ORFs still can be used locally within each d × d block of W (Yu et al., 2016).”
Randomized Distributed Mean Estimation: Accuracy vs. Communication (2016, neutral): “, a structured random rotation, see [16]).”
Distributed Mean Estimation with Limited Communication (2016, methodology): “Motivated by recent works of structured matrices (Ailon & Chazelle, 2006; Yu et al., 2016), we propose to use a special type of orthogonal matrixR = HD, whereD is a random diagonal matrix with i.”
Calibrating Deep Convolutional Gaussian Processes (2018, methodology): “Structured random feature approximations: One of the advantages of the proposed model, compared to other GP approximations, is that it can exploit structured random feature expansions to accelerate computations and reduce the size of the approximate GP [20, 29].”
Random Feature Attention (2021, methodology): “(2) When d -dimensional random vectors w i are independently sampled from N ( 0 , σ 2 I d ) , Variance of the estimation is inversely proportional to D (Appendix A.2; Yu et al., 2016).”
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 ) .”
Stochastic, Distributed and Federated Optimization for Machine Learning (2017, methodology): “In this work, we use a type of structured rotation matrix which is the product of a Walsh-Hadamard matrix and a binary diagonal matrix, motivated by the recent advance in this topic [190].”
Learning Fast Algorithms for Linear Transforms Using Butterfly Factorizations (2019, background): “, convolution) [47] and the DFT and Hadamard transform [23, 48] for fast projection.”
Monarch: Expressive Structured Matrices for Efficient and Accurate Training (2022, methodology): “The matrix class (MM∗)2 can represent the Fourier transform, discrete sine and cosine transforms (DST/DCT), the (HD)(3) (Yu et al., 2016) class, Fastfood (Le et al.”
Kaleidoscope: An Efficient, Learnable Representation For All Structured Linear Maps (2020, methodology): “Fast random projection and kernel approximation methods rely on the fast Hadamard transform (Le et al., 2013; Yu et al., 2016) and convolution (Yu et al., 2015), and convolution is a critical component of modern image processing architectures (Krizhevsky et al., 2012) as well as being useful in…”
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).”
The Geometry of Random Features (2018, methodology): “These triple win methods have been used so far only in very special scenarios such as Gaussian kernel approximation in the regime of high data dimensionality (Yu et al., 2016), dimensionality reduction with modified JohnsonLindenstrauss transform, angular kernel approximation (Choromanski et al.”
Demystifying Orthogonal Monte Carlo and Beyond (2020, methodology): “This motivates future work on incorporating modern algebraic techniques into Monte Carlo algorithms for machine learning.”
Learning to Learn Kernels with Variational Random Features (2020, unknown): “…± 0.3 99.4 ± 0.2 GNN (Garcia & Bruna, 2018) 99.2 99.7 97.4 99.0 VERSA (Gordon et al., 2019) 99.7 0.2 ± ± ± ± R2-D2 (Bertinetto et al., 2019) 98.6 99.7 94.7 98.9 IMP (Allen et al., 2019) 98 usually set to be 5 to 10 times the dimension of the input features (Yu et al., 2016; Rahimi & Recht, 2007).”
Manifold Regularization for Kernelized LSTD (2017, methodology): “ency and Q-function approximation,and demonstrate superior performance on two standard RL benchmarks. Future work directions include 1) accelerating by structured random matrices for kernel machinery [23, 24], and graph sketching for graphregularizerconstructiontoscaleuptolargedatasetsandrichobserva”
Unifying Orthogonal Monte Carlo Methods (2019, methodology): “…reduction (Choromanski et al., 2017), locality-sensitive hashing (Andoni et al., 2015), random feature approximations to kernel methods such as Gaussian processes (Choromanski et al., 2018a) and support vector machines (Yu et al., 2016), and black-box optimization (Choromanski et al., 2018b).”
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).”
The Unreasonable Effectiveness of Structured Random Orthogonal Embeddings (2017, background): “This class includes as particular cases several recently introduced random matrices (e.g. Andoni et al., 2015; Yu et al., 2016), where good empirical performance was observed.”
Sampled Softmax with Random Fourier Features (2019, methodology): “On the other hand, the variance of the kernel approximation of Random Fourier feature grows with ⌫ [26].”