Covariance discriminative power of kernel clustering methods

Let x1,⋯,xn be independent observations of size p, each of them belonging to one of c distinct classes. We assume that observations within the class a are characterized by their distribution N(0,1 pCa) where here C1,⋯,Cc are some non-negative definite p×p matrices. This paper studies the asymptotic behavior of the symmetric matrix Φ˜kl=p(x kTx l)2δ k≠l when p and n grow to infinity with n p→c0. Particularly, we prove that, if the class covariance matrices are sufficiently close in a certain sense, the matrix Φ˜ behaves like a low-rank perturbation of a Wigner matrix, presenting possibly some isolated eigenvalues outside the bulk of the semi-circular law. We carry out a careful analysis of some of the isolated eigenvalues of Φ˜ and their associated eigenvectors and illustrate how these results can help understand spectral clustering methods that use Φ˜ as a kernel matrix.