Inner-product Kernels are Asymptotically Equivalent to Binary Discrete Kernels

This article investigates the eigenspectrum of the inner product-type kernel matrix √p K=f( xisf T xj/√p)i,j=1n 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.