  The method of "random Fourier features (RFF)" has become a popular tool for
approximating the "radial basis function (RBF)" kernel. The variance of RFF is
actually large. Interestingly, the variance can be substantially reduced by a
simple normalization step as we theoretically demonstrate. We name the improved
scheme as the "normalized RFF (NRFF)".
  We also propose the "generalized min-max (GMM)" kernel as a measure of data
similarity. GMM is positive definite as there is an associated hashing method
named "generalized consistent weighted sampling (GCWS)" which linearizes this
nonlinear kernel. We provide an extensive empirical evaluation of the RBF
kernel and the GMM kernel on more than 50 publicly available datasets. For a
majority of the datasets, the (tuning-free) GMM kernel outperforms the
best-tuned RBF kernel.
  We conduct extensive experiments for comparing the linearized RBF kernel
using NRFF with the linearized GMM kernel using GCWS. We observe that, to reach
a comparable classification accuracy, GCWS typically requires substantially
fewer samples than NRFF, even on datasets where the original RBF kernel
outperforms the original GMM kernel. The empirical success of GCWS (compared to
NRFF) can also be explained from a theoretical perspective. Firstly, the
relative variance (normalized by the squared expectation) of GCWS is
substantially smaller than that of NRFF, except for the very high similarity
region (where the variances of both methods are close to zero). Secondly, if we
make a model assumption on the data, we can show analytically that GCWS
exhibits much smaller variance than NRFF for estimating the same object (e.g.,
the RBF kernel), except for the very high similarity region.
