One-Sketch-for-All: Non-linear Random Features from Compressed Linear Measurements

The commonly used Gaussian kernel has a tuning parameter $\gamma$. This makes the design of quantization schemes for random Fourier features (RFF) challenging, which is a popular technique to approximate the Gaussian kernel. Intuitively one would expect that a different quantizer is needed for a different $\gamma$ value (and we need to store a different set of quantized data for each $\gamma$). Fortunately, the recent work~\citep{Report:Li_2021_RFF} showed that only one Lloyd-Max (LM) quantizer is needed as the marginal distribution of RFF is free of the tuning parameter $\gamma$. On the other hand, \citet{Report:Li_2021_RFF} still required to store a different set of quantized data for each $\gamma$ value. In this paper, we adopt the ``one-sketch-for-all'' strategy for quantizing RFFs. Basically, we only store one set of quantized data after applying random projections on the original data. From the same set of quantized data, we can construct approximate RFFs to approximate Gaussian kernels for any tuning parameter $\gamma$. Compared with \citet{Report:Li_2021_RFF}, our proposed scheme would lose some accuracy as one would expect. Nevertheless, the proposed method still perform noticeably better than the quantization scheme based on random rounding. We provide statistical analysis on the properties of the proposed method and experiments are conducted to empirically illustrate its effectiveness.