Inner-product Kernels are Asymptotically Equivalent to Binary Discrete Kernels
This provides theoretical insight into nonlinearity in large-scale machine learning, with practical benefits for efficiency, though it is incremental in nature.
The paper shows that inner-product kernels in high-dimensional data behave asymptotically like simple cubic functions, and proposes a binary-valued function prototype that matches the classification performance of arbitrary kernels while reducing storage and runtime.
This article investigates the eigenspectrum of the inner product-type kernel matrix $\sqrt{p} \mathbf{K}=\{f( \mathbf{x}_i^{\sf T} \mathbf{x}_j/\sqrt{p})\}_{i,j=1}^n $ under a binary mixture model in the high dimensional regime where the number of data $n$ and their dimension $p$ are both large and comparable. Based on recent advances in random matrix theory, we show that, for a wide range of nonlinear functions $f$, the eigenspectrum behavior is asymptotically equivalent to that of an (at most) cubic function. This sheds new light on the understanding of nonlinearity in large dimensional problems. As a byproduct, we propose a simple function prototype valued in $ (-1,0,1) $ that, while reducing both storage memory and running time, achieves the same (asymptotic) classification performance as any arbitrary function $f$.