  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.
