Quantization Algorithms for Random Fourier Features

  • 2021-02-25 18:51:39
  • Xiaoyun Li, Ping Li
  • 0

Abstract

The method of random projection (RP) is the standard technique in machinelearning and many other areas, for dimensionality reduction, approximate nearneighbor search, compressed sensing, etc. Basically, RP provides a simple andeffective scheme for approximating pairwise inner products and Euclideandistances in massive data. Closely related to RP, the method of random Fourierfeatures (RFF) has also become popular, for approximating the Gaussian kernel.RFF applies a specific nonlinear transformation on the projected data fromrandom projections. In practice, using the (nonlinear) Gaussian kernel oftenleads to better performance than the linear kernel (inner product), partly dueto the tuning parameter $(\gamma)$ introduced in the Gaussian kernel. Recently,there has been a surge of interest in studying properties of RFF. After random projections, quantization is an important step for efficientdata storage, computation, and transmission. Quantization for RP has also beenextensive studied in the literature. In this paper, we focus on developingquantization algorithms for RFF. The task is in a sense challenging due to thetuning parameter $\gamma$ in the Gaussian kernel. For example, the quantizerand the quantized data might be tied to each specific tuning parameter$\gamma$. Our contribution begins with an interesting discovery, that themarginal distribution of RFF is actually free of the Gaussian kernel parameter$\gamma$. This small finding significantly simplifies the design of theLloyd-Max (LM) quantization scheme for RFF in that there would be only one LMquantizer for RFF (regardless of $\gamma$). We also develop a variant namedLM$^2$-RFF quantizer, which in certain cases is more accurate. Experimentsconfirm that the proposed quantization schemes perform well.

 

Quick Read (beta)

loading the full paper ...