Random matrices in service of ML footprint: ternary random features with no performance loss

In this article, we investigate the spectral behavior of random features\nkernel matrices of the type ${\\bf K} = \\mathbb{E}_{{\\bf w}}\n\\left[\\sigma\\left({\\bf w}^{\\sf T}{\\bf x}_i\\right)\\sigma\\left({\\bf w}^{\\sf\nT}{\\bf x}_j\\right)\\right]_{i,j=1}^n$, with nonlinear function $\\sigma(\\cdot)$,\ndata ${\\bf x}_1, \\ldots, {\\bf x}_n \\in \\mathbb{R}^p$, and random projection\nvector ${\\bf w} \\in \\mathbb{R}^p$ having i.i.d. entries. In a high-dimensional\nsetting where the number of data $n$ and their dimension $p$ are both large and\ncomparable, we show, under a Gaussian mixture model for the data, that the\neigenspectrum of ${\\bf K}$ is independent of the distribution of the\ni.i.d.(zero-mean and unit-variance) entries of ${\\bf w}$, and only depends on\n$\\sigma(\\cdot)$ via its (generalized) Gaussian moments $\\mathbb{E}_{z\\sim\n\\mathcal N(0,1)}[\\sigma'(z)]$ and $\\mathbb{E}_{z\\sim \\mathcal\nN(0,1)}[\\sigma''(z)]$. As a result, for any kernel matrix ${\\bf K}$ of the form\nabove, we propose a novel random features technique, called Ternary Random\nFeature (TRF), that (i) asymptotically yields the same limiting kernel as the\noriginal ${\\bf K}$ in a spectral sense and (ii) can be computed and stored much\nmore efficiently, by wisely tuning (in a data-dependent manner) the function\n$\\sigma$ and the random vector ${\\bf w}$, both taking values in $\\{-1,0,1\\}$.\nThe computation of the proposed random features requires no multiplication, and\na factor of $b$ times less bits for storage compared to classical random\nfeatures such as random Fourier features, with $b$ the number of bits to store\nfull precision values. Besides, it appears in our experiments on real data that\nthe substantial gains in computation and storage are accompanied with somewhat\nimproved performances compared to state-of-the-art random features\ncompression/quantization methods.\n