# Random Fourier Features for Asymmetric Kernels

arXiv: https://arxiv.org/abs/2209.08461 · HTML: https://mlsanity.com/paper/2209.08461/

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 13 of its 50 references that are in the map.
- First posted on arXiv 18 Sep 2022.

## Builds on (most cited first, 13 of 13)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Reconciling modern machine learning practice and the bias-variance trade-off](https://mlsanity.com/paper/1812.11118/) (2018)
- [LINE: Large-scale Information Network Embedding](https://mlsanity.com/paper/1503.03578/) (2015)
- [Proving the Lottery Ticket Hypothesis: Pruning is All You Need](https://mlsanity.com/paper/2002.00585/) (2020)
- [Random Features for Kernel Approximation: A Survey on Algorithms, Theory, and Beyond](https://mlsanity.com/paper/2004.11154/) (2020)
- [PTE: Predictive Text Embedding through Large-scale Heterogeneous Text Networks](https://mlsanity.com/paper/1508.00200/) (2015)
- [On the Error of Random Fourier Features](https://mlsanity.com/paper/1506.02785/) (2015)
- [Understanding neural networks with reproducing kernel Banach spaces](https://mlsanity.com/paper/2109.09710/) (2021)
- [On Reproducing Kernel Banach Spaces: Generic Definitions and Unified Framework of Constructions](https://mlsanity.com/paper/1901.01002/) (2019)
- [Transformers are Deep Infinite-Dimensional Non-Mercer Binary Kernel Machines](https://mlsanity.com/paper/2106.01506/) (2021)
- [Node Representation Learning for Directed Graphs](https://mlsanity.com/paper/1810.09176/) (2018)
- [Adversarial Directed Graph Embedding](https://mlsanity.com/paper/2008.03667/) (2020)
- [Learning with Asymmetric Kernels: Least Squares and Feature Interpretation](https://mlsanity.com/paper/2202.01397/) (2022)

## Built on by (most cited first, 7 of 7)

- [Unveiling Differences in Generative Models: A Scalable Differential Clustering Approach](https://mlsanity.com/paper/2405.02700/) (2024)
- [Spectraformer: A Unified Random Feature Framework for Transformer](https://mlsanity.com/paper/2405.15310/) (2024)
- [MUSO: Achieving Exact Machine Unlearning in Over-Parameterized Regimes](https://mlsanity.com/paper/2410.08557/) (2024)
- [Mirror Descent on Reproducing Kernel Banach Spaces](https://mlsanity.com/paper/2411.11242/) (2024)
- [A Kernelizable Primal-Dual Formulation of the Multilinear Singular Value Decomposition](https://mlsanity.com/paper/2410.10504/) (2024)
- [Escaping Spectral Bias without Backpropagation: Fast Implicit Neural Representations with Extreme Learning Machines](https://mlsanity.com/paper/2602.07603/) (2026)
- [Signed random Fourier features for fast density estimation with indefinite kernels](https://mlsanity.com/paper/2608.29265/) (2026)

## Abstract (arXiv)

The random Fourier features (RFFs) method is a powerful and popular technique in kernel approximation for scalability of kernel methods. The theoretical foundation of RFFs is based on the Bochner theorem that relates symmetric, positive definite (PD) functions to probability measures. This condition naturally excludes asymmetric functions with a wide range applications in practice, e.g., directed graphs, conditional probability, and asymmetric kernels. Nevertheless, understanding asymmetric functions (kernels) and its scalability via RFFs is unclear both theoretically and empirically. In this paper, we introduce a complex measure with the real and imaginary parts corresponding to four finite positive measures, which expands the application scope of the Bochner theorem. By doing so, this framework allows for handling classical symmetric, PD kernels via one positive measure; symmetric, non-positive definite kernels via signed measures; and asymmetric kernels via complex measures, thereby unifying them into a general framework by RFFs, named AsK-RFFs. Such approximation scheme via complex measures enjoys theoretical guarantees in the perspective of the uniform convergence. In algorithmic implementation, to speed up the kernel approximation process, which is expensive due to the calculation of total mass, we employ a subset-based fast estimation method that optimizes total masses on a sub-training set, which enjoys computational efficiency in high dimensions. Our AsK-RFFs method is empirically validated on several typical large-scale datasets and achieves promising kernel approximation performance, which demonstrate the effectiveness of AsK-RFFs.