Random features have been introduced to scale up kernel methods via
randomization techniques. In particular, random Fourier features and orthogonal
random features were used to approximate the popular Gaussian kernel. The
former is performed by a random Gaussian matrix and leads exactly to the
Gaussian kernel after averaging. In this work, we analyze the bias and the
variance of the kernel approximation based on orthogonal random features which
makes use of Haar orthogonal matrices. We provide explicit expressions for
these quantities using normalized Bessel functions and derive sharp exponential
bounds supporting the view that orthogonal random features are more informative
than random Fourier features.

通过正交随机特征来近似普遍的高斯核，本研究分析了基于正交随机特征的核逼近的偏差和方差，并通过使用归一化贝塞尔函数推导出了明确的表达式，并提供了支持正交随机特征比随机傅里叶特征更具信息性的尖锐指数界限。

正交随机特征：显式形式和尖锐不等式

Orthogonal Random Features: Explicit Forms and Sharp Inequalities

We present an intriguing discovery related to Random Fourier Features: in
Gaussian kernel approximation, replacing the random Gaussian matrix 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 this behavior.
Motivated by this 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
applications.

本文通过使用正交矩阵代替高斯随机矩阵来减小核近似误差提出了正交随机特征和结构化正交随机特征，并为此行为提供理论和实证证据。实验结果证明了与现有方法相比 ORF 和 SORF 的有效性。