Inner-product Kernels are Asymptotically Equivalent to Binary Discrete Kernels

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$.