  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.
