Kernel spectral clustering of large dimensional data

Introduction

Kernel spectral clustering encompasses a variety of algorithms meant to group data in an unsupervised manner based on the eigenvectors of certain data-driven matrices. These methods are so widely spread that they have become an essential ingredient of contemporary machine learning (see [V07] and references therein). This being said, the theoretical foundations of kernel spectral clustering are not unified as it can be obtained from several independent ideas, hence the multiplicity of algorithms to meet the same objective.

where, with $D\triangleq\operatorname{\mathcal{D}}(K1_{n})$ (with $\operatorname{\mathcal{D}}(\cdot)$ the diagonal operator), $D-K$ is the so-called (unnormalized) Laplacian matrix of $K$ and $M$ contains the information about the $\mathcal{C}_{i}$ classes. Observing that $M^{\sf T}M=I_{k}$, one may relax the above problem to

which then reduces to an eigenvector problem. From the original form of $M\in\mathcal{M}$, the data clusters can then readily be retrieved from the entries of $M$.

Our focus, for reasons discussed below, is precisely on the following version of the normalized Laplacian matrix

which we shall from now on refer to, with a slight language abuse, as the Laplacian matrix of $K$. The kernel function $\kappa$ will be such that $\kappa(x,y)=f(\|x-y\|^{2}/p)$ for some sufficiently smooth $f$ independent of $n,p$, that isThis choice is merely motivated by the wide spread of these (so-called radial) kernels in statistics. The alternative choice $\kappa(x,y)=f(x^{\sf T}y/p)$ could be treated similarly and in fact turns out (based on a parallel study) to be much simpler to handle and less rich in clustering capabilities.

For $x_{i}$ in class $\mathcal{C}_{a}$, we assume that $x_{i}\sim\mathcal{N}(\mu_{a},C_{a})$ with $(\mu_{a},C_{a})\in\{(\mu_{1},C_{1}),\ldots,(\mu_{k},C_{k})\}$ ($k$ shall remain fixed while $p,n\to\infty$) such that, for each $(a,b)$, $\|\mu_{a}-\mu_{b}\|=O(1)$ while $\|C_{a}\|=O(1)$ (here, and throughout the article, $\|\cdot\|$ stands for the operator norm) and $\operatorname{tr}(C_{a}-C_{b})=O(\sqrt{p})$. This setting can be considered as a critical growth rate regime in the sense that, supposing $\operatorname{tr}C_{a}$ and $\operatorname{tr}C_{a}^{2}$ to be of order $O(p)$ (which is natural if $\|C_{a}\|=O(1)$) and $\|\mu_{a}-\mu_{b}\|=O(1)$, the norms of the observations in each class $\mathcal{C}_{a}$ fluctuate at rate $\sqrt{p}$ around $\operatorname{tr}C_{a}$, so that clustering ought to be possible so long as $\operatorname{tr}(C_{a}-C_{b})=O(\sqrt{p})$.

The technical contribution of this work is to provide a thorough analysis of the eigenvalues and eigenvectors of the matrix $L$ in the aforementioned regime. In a nutshell, we shall demonstrate that there exist critical values for the (inter-cluster differences between) means $\mu_{i}$ and covariances $C_{i}$ beyond which some (relevant) eigenvalues of $L$ tend to isolate from the majority of the eigenvalues, thus inducing a so-called spiked model for $L$. When this occurs, the eigenvectors associated to these isolated eigenvalues will contain information about class clustering. Our objective is to precisely describe the structure of the individual eigenvectors as well as to evaluate correlation coefficients among these, keeping in mind that the ultimate interest is on harnessing spectral clustering methods. The outcomes of our study shall provide new practical insights and methods to appropriately select the kernel function $f$.

Before delving concretely into our main results, some of which may seem quite cryptic on the onset, we introduce below a motivation example and some visual results of our work.

The proofs of some of the technical mathematical results are deferred to our companion paper [BC16].

We shall often denote $\{v_{a}\}_{a=1}^{k}$ a column vector with $a$-th entry (or block entry) $v_{a}$ (which may be a vector itself), while $\{V_{ab}\}_{a,b=1}^{k}$ denotes a square matrix with entry (or block-entry) $(a,b)$ given by $V_{ab}$ (which may be a matrix itself).

Motivation and statement of main results

Let us start by illustratively motivate our work. In Figure 2 are displayed in red the eigenvectors associated with the four largest eigenvalues of $L$ (as defined in (2)) for $x_{1},\ldots,x_{n}$ a set of (preprocessedThe full MNIST database is preprocessed by discarding from all images the empirical mean and by then scaling the resulting vector images by $p$ over the average squared norm of all vector images. This preprocessing ensures an appropriate match to the base Assumption 1 below.) vectorized images sampled from the popular MNIST database (handwritten digits) [LCB98]. The vector images are of size $p=784$ (for images are of size $28\times 28$) and we take $n=192$ samples, with the first $64$ $x_{i}$’s being images of zeros, next $64$ images of ones, and last $64$ images of twos. An example of these is displayed in Figure 1 (the vector values follow a grayscale from zero for black to one for white). The kernel function $f$ (defining the kernel matrix $K$ through (3)) is taken to be the standard $f(x)=\exp(-x/2)$ Gaussian kernel.

In order to anticipate the performance of clustering methods, and to be capable of improving the latter, it is a fundamental first step to understand the behavior of the eigenvectors of Figure 2 along with their joint correlation, as exemplified in Figure 3. The present work intends to lay the theoretical grounds for such clustering performance understanding and improvement. Namely, we shall investigate the existence and position of isolated eigenvalues of $L$ and shall show that some of them (not always all of them) carry information about the class structure of the problem. Then, since, by a clear invariance property of the model under consideration, each of the dominant eigenvectors of $L$ can be divided class-wise into $k$ chunks, each of which being essentially composed of independent realizations of a random variable with given mean and variance, we shall identify these means and variances. Finally, since eigenvectors are correlated, we shall evaluate the class-wise correlation coefficients.

As a first glimpse on the practical interest of our results, in Figure 2 are displayed in blue lines the theoretical means and standard deviations for each class-wise chunk of eigenvectors, obtained from the results of this article. That is, the means and standard deviations that one would obtain if the data were genuinely Gaussian (which here for the MNIST images they are obviously not). Also, Figure 3 proposes in blue ellipses the theoretical one- and two-standard deviations of the joint eigenvector entries, again if the data were to be Gaussian. It is quite interesting to see that, in spite of their evident non-Gaussianity, the theoretical findings visually conform to the data behavior. We are thus optimistic that the findings of this work, although restricted to Gaussian assumptions, can be applied to a large set of problems beyond strongly structured ones.

We summarize below our main theoretical contributions and their practical aftermaths, all detailed more thoroughly in the subsequent sections. From a technical standpoint, our main results may be summarized as follows:

as $n,p\to\infty$ while $n/p=O(1)$, $\|L^{\prime}-\hat{L}^{\prime}\|\to 0$ (in operator norm) almost surely, where $L^{\prime}$ is a slight modification of $L$ and $\hat{L}^{\prime}$ is a matrix which is an instance of the so-called spiked random matrix models, as introduced in [BBP05, BN12] (but closer to the model studied independently in [CH13]); that is, the spectrum of $\hat{L}^{\prime}$ is essentially composed of (one or several) clusters of eigenvalues and finitely many isolated ones. This result is the mandatory ground step that allows for the theoretical understanding of the eigenstructure of $L$;

as is standard in spiked models, there exists a phase transition phenomenon by which, the more distinct the classes, the more eigenvalues tend to isolate from the main eigenvalue bulk of $\hat{L}^{\prime}$ and the more information is contained within the eigenvectors associated with those eigenvalues. This statement is precisely accounted for by exhibiting conditions for the separability of the isolated eigenvalues from the main bulk, by exactly locating these eigenvalues, and by retrieving the asymptotic values of the class-wise means and variances of the isolated eigenvectors;

the eigenvectors associated to the isolated eigenvalues are correlated to one another and we precisely exhibit the asymptotic correlation coefficients.

Aside from these main expected results are some more subtle and somewhat unexpected outcomes:

the eigenvectors associated with some of the non extreme isolated eigenvalues of $L^{\prime}$ may contain information about the classes, and thus clustering may be performed not only based on extreme eigenvectors;

on the contrary, some of the eigenvectors associated to isolated eigenvalues, even the largest, may be purely noisy;

in some specific scenarios, the theoretical number of informative isolated eigenvalues cannot exceed two altogether, while in others as many as $k-1$ can be found in-between each pair of eigenvalue bulks of $L^{\prime}$;

in some other scenarios, two eigenvectors may be essentially the same, so that some eigenvectors may not always provide much information diversity.

From a practical standpoint, the aforementioned technical results, along with the observed adequacy between theory and practice, have the following key entailments:

as opposed to classical kernel spectral clustering insights in small dimensional datasets, high dimensional data tend to be “always far from one another” to the point that $\|x_{i}-x_{j}\|$ for intra-class data $x_{i}$ and $x_{j}$ may systematically be larger than for inter-class data. This disrupts many aspects of kernel spectral clustering, starting with the interest for non-decreasing kernel functions $f$;

the interplay between the triplet $(f(\tau),f^{\prime}(\tau),f^{\prime\prime}(\tau))$ and the class-wise means and covariances opens up a new road for kernel investigations; in particular, although counter-intuitive, choosing $f$ non-monotonous may be beneficial for some datasets. In a work subsequent to the present article [CK16], we show that choosing $f^{\prime}(\tau)=0$ allows for very efficient subspace clustering of zero mean data, where the traditional Gaussian kernel $f(x)=\exp(-x/2)$ completely fails (the motivation for [CK16] was spurred by the important Remark 12 below);

more specifically, in problems where clustering ought to group data upon specific statistical properties (e.g., upon the data covariance, irrespective of the statistical means), then appropriate choices of kernels $f$ can be made that purposely discard specific statistical information;

the result of the study of the eigenvectors content, along with point (B) above, allow for a theoretical evaluation of the optimally expectable performance of kernel spectral clustering for large dimensional Gaussian mixtures (and then likely for any practical large dimensional dataset). As such, upon the existence of a parallel set of labelled data, one may prefigure the optimum quality of kernel clustering on similar datasets (e.g., datasets anticipated to share similar statistical structures).

We now turn to the detailed introduction of our model and to some necessary preliminary notions of random matrix theory.

Preliminaries

We shall consider the large dimensional regime where both $n$ and $p$ are simultaneously large with the following growth rate assumption.

As $n\to\infty$, the following conditions hold.

Data scaling: defining $c_{0}\triangleq\frac{p}{n}$

Class scaling: for each $a\in\{1,\ldots,k\}$, defining $c_{a}\triangleq\frac{n_{a}}{n}$,

We shall denote $c\triangleq\left\{c_{a}\right\}_{a=1}^{k}$.

Mean scaling: let $\mu^{\circ}\triangleq\sum_{i=1}^{k}\frac{n_{i}}{n}\mu_{i}$ and for each $a\in\{1,\ldots,k\}$, $\mu_{a}^{\circ}\triangleq\mu_{a}-\mu^{\circ}$, then

Covariance scaling: let $C^{\circ}\triangleq\sum_{i=1}^{k}\frac{n_{i}}{n}C_{i}$ and for each $a\in\{1,\ldots,k\}$, $C_{a}^{\circ}\triangleq C_{a}-C^{\circ}$, then

As discussed in the introduction, the growth rates above were chosen in such a way that the achieved clustering performance be non-trivial in the sense that: (i) the proportion of misclassification remains non-vanishing as $n\to\infty$, and (ii) there exist smallest values of $\|\mu_{a}^{\circ}\|$, $\frac{1}{\sqrt{p}}\operatorname{tr}C_{a}^{\circ}$ and $\frac{1}{p}\operatorname{tr}C_{a}^{\circ}C_{b}^{\circ}$ below which no isolated eigenvector can be used to perform efficient spectral clustering.

This quantity is central to our analysis as it is easily shown that, under Assumption 1,

almost surely. The value $\tau$, which depends implicitly on $n$, is bounded but needs not converge as $p\to\infty$.

The function $f$ is three-times continuously differentiable in a neighborhood of the values taken by $\tau$. Moreover, $\liminf_{n}f(\tau)>0$.

From (5), it appears that, while the diagonal elements of $K$ are all equal to $f(0)$, the off-diagonal entries jointly converge toward $f(\tau)$. This means that, up to $(f(\tau)-f(0))I_{n}$, $K$ is essentially a rank-one matrix.

The observation above has important consequences to the traditional vision of kernel spectral clustering. Indeed, while in the low-dimensional regime (small $p$) it is classically assumed that intra-class data can be linked through a chain of short distances $\|x_{i}-x_{j}\|$, for large $p$, all $x_{i}$ tend to be far apart. The statistical differences between data, that shall then allow for clustering, only appear in the second order terms in the expansion of $K_{ij}$ which need not be ordered in a decreasing manner as $x_{i}$ and $x_{j}$ belong to “more distant classes”. This immediately annihilates the need for $f$ to be a decreasing function, thereby disrupting from elementary considerations in traditional spectral clustering.

As spectral clustering is based on Laplacian matrices rather than on $K$ itself, we shall focus here on the Laplacian matrix

where $D=\operatorname{\mathcal{D}}(K1_{n})$ is often referred to as the matrix of degrees of $K$. Aside from the arguments laid out in the introduction, the choice of studying the matrix $L$ also follows from a better stability of clustering algorithms based on $L$ versus $K$ and $D-K$ that we observed in various simulations.

Under our growth rate assumptions, the matrix $L$ shall be seen to essentially be a rank-one matrix which is rather simple to deal with since, unlike $K$, its dominant eigenvector is known precisely to be $D^{\frac{1}{2}}1_{n}$ and it shall be shown that the projected matrix

has bounded operator norm almost surely as $n\to\infty$. Indeed, note here that $L^{\prime}$ and $L$ have the same eigenvalues and eigenvectors but for the eigenvalue-eigenvector pair $(n,D^{\frac{1}{2}}1_{n})$ of $L$ turned into $(0,D^{\frac{1}{2}}1_{n})$ for $L^{\prime}$. Under the aforementioned assumptions, the matrix $L^{\prime}$ will be subsequently shown to have its eigenvalues all of order $O(1)$.

Our first intermediary result shows that there exists a matrix $\hat{L}^{\prime}$ such that $\|L^{\prime}-\hat{L}^{\prime}\|\to 0$ almost surely, where $\hat{L}^{\prime}$ follows an analytically tractable random matrix model. Before going into the result, a few notations need be introduced. In the remainder of the article, we shall use the following deterministic element notationsAs a mental reminder, capital $M$ stands here for means while $t$, $T$ account for vector and matrix of traces, $P$ for a projection matrix (onto the orthogonal of the vector $1_{n}$).

Let Assumptions 1 and 2 hold. Let $L^{\prime}$ be defined as in (6). Then, as $n\to\infty$,

almost surely, where $\hat{L}^{\prime}$ is given by

with $F(\tau)=\frac{f(0)-f(\tau)+\tau f^{\prime}(\tau)}{2f^{\prime}(\tau)}$ and

and the case $f^{\prime}(\tau)=0$ is obtained through extension by continuity ($f^{\prime}(\tau)B$ being well defined as $f^{\prime}(\tau)\to 0$).

From Theorem 1 it entails that the eigenvalues of $L^{\prime}$ and $\hat{L}^{\prime}$ converge to one another (as we have as an immediate corollary that $\max_{i}|\lambda_{i}(L^{\prime})-\lambda_{i}(\hat{L}^{\prime})|\overset{\rm a.s.}{\longrightarrow}0$; see e.g., [HJ85, Theorem 4.3.7]), so that the determination of isolated eigenvalues in the spectrum of $L^{\prime}$ (or $L$) can be studied from the equivalent problem for $\hat{L}^{\prime}$. More importantly, from Theorem 1, it unfolds that, for every isolated eigenvector $u$ of $L^{\prime}$ and its associated $\hat{u}$ of $\hat{L}^{\prime}$, $\|u-\hat{u}\|\overset{\rm a.s.}{\longrightarrow}0$. Thus, the spectral clustering performance based on the observable $L^{\prime}$ (or $L$) may be asymptotically analyzed through that of $\hat{L}^{\prime}$.

A few important remarks concerning Theorem 1 are in order before proceeding. From a mathematical standpoint, observe that, up to a scaled identity matrix and a constant scale factor, if $f^{\prime}(\tau)\neq 0$, $\hat{L}^{\prime}$ is a random matrix of the so-called spiked model family [BBP05] in that it equals the sum of a somewhat standard random matrix model $PW^{\sf T}WP$ and of a small rank (here up to $2k+1$) matrix $UBU^{\sf T}$. Nonetheless, it differs from classically studied spiked models in several aspects: (i) $U$ is not independent of $W$, which is a technical issue that can fairly easily be handled, and (ii) $PW^{\sf T}WP$ itself constitutes a spiked model as $P$ is a low rank perturbation of the identity matrix.Our choice of not breaking $PW^{\sf T}WP$ into $W^{\sf T}W$ plus small rank perturbation integrated to the perturbation $UBU^{\sf T}$ stands from the fact that the hypothetical isolated eigenvectors $P$ engenders do not provide any clustering information, unlike $UBU^{\sf T}$. Besides, by Remark 3 below or by interlacing inequalities, $PW^{\sf T}WP$ does not induce isolated eigenvalues on the right side of the support, where clustering algorithms look for eigenvalues.

As such, as $n\to\infty$, the eigenvalues of $\hat{L}^{\prime}$ are expected to be asymptotically the same as those of $PW^{\sf T}WP$ (which mainly gather in bulks) but possibly for finitely many of them which are allowed to wander away from the main eigenvalue bulks. As per classical spiked model results from random matrix theory, it is then naturally expected that, if some of the (finitely many) eigenvalues of $UBU^{\sf T}$ are sufficiently large, those shall induce isolated eigenvalues in the spectrum of $\hat{L}^{\prime}$, the eigenvectors of which align to some extent to the eigenvectors of $UBU^{\sf T}$. If instead $f^{\prime}(\tau)=0$, then $\hat{L}^{\prime}-\frac{f(0)-f(\tau)}{f(\tau)}I_{n}$ is of maximum rank $k+1$ and is fully deterministic, hence has eigenvalue-eigenvector pairs immediately related to $UBU^{\sf T}$.

From a spectral clustering aspect, observe that $U$ is importantly constituted by the vectors $j_{a}$, $1\leq a\leq k$, while $B$ contains the information about the inter-class mean deviations through $M$, and about the inter-class covariance deviations through $t$ and $T$. As such, some of the aforementioned isolated eigenvectors are expected to align to the canonical class basis $J$ and we already intuit that this will be true all the more that the matrices $M$, $t$, $T$ have sufficient “energy” (i.e., are sufficiently away from zero matrices). Theorem 1 thus already prefigures the behavior of spectral clustering methods thoroughly detailed in Section 4.

A more detailed application-oriented analysis now sheds light on the behavior of the kernel function $f$. Note that, if $f^{\prime}(\tau)\to 0$, $L^{\prime}$ becomes essentially deterministic as $f^{\prime}(\tau)PW^{\sf T}WP\to 0$, this having a positive effect of the alignment between $L^{\prime}$ and $J$. However, when $f^{\prime}(\tau)\to 0$, $M$ vanishes from the expression of $\hat{L}^{\prime}$, thus not allowing spectral clustering to rely on differences in means. Similarly, if $f^{\prime\prime}(\tau)\to 0$, then $T$ vanishes, and thus differences in “shape” between the covariance matrices cannot be discriminated upon. Finally, if $\frac{5f^{\prime}(\tau)}{8f(\tau)}-\frac{f^{\prime\prime}(\tau)}{2f^{\prime}(\tau)}\to 0$, then differences in covariance traces are seemingly not exploitable.

This observation leads to the following key remark on the optimal choice of a kernel.

An illustrative application of Theorem 1 is proposed in Figure 4, where a three-class example with Gaussian kernel function is considered. Note the extremely accurate spectrum approximation of $L^{\prime}$ by $\hat{L}^{\prime}$ in this example. Anticipating slightly our coming results, note here that, aside from the eigenvalue zero, two isolated (spiked) eigenvalues are observed, which shall presently be related to the eigenvalues of the small rank matrix $UBU^{\sf T}$.

Before introducing our technical approach, a few further random matrix notions are needed.

where the $(g_{1},\ldots,g_{k})$ is the unique vector of Stieltjes transforms solutions, for all such $z$, to the implicit equations

and the notation $A_{n}\leftrightarrow B_{n}$ stands for the fact that, as $n\to\infty$, $\frac{1}{n}\operatorname{tr}D_{n}A_{n}-\frac{1}{n}\operatorname{tr}D_{n}B_{n}\overset{\rm a.s.}{\longrightarrow}0$ and $d_{1,n}^{\sf T}(A_{n}-B_{n})d_{2,n}\overset{\rm a.s.}{\longrightarrow}0$ for all deterministic Hermitian matrix $D_{n}$ and deterministic vectors $d_{i,n}$ of bounded norms.

With those notations and remarks at hand, we are now ready to introduce our main results.

Main Results

Before delving into the investigation of the eigenvalues and eigenvectors of $L$, recall from Theorem 1 that the behavior of $L$ is strikingly different if $f^{\prime}(\tau)$ is away from zero or if instead $f^{\prime}(\tau)\to 0$. We shall then systematically study both cases independently. In practice, if $f^{\prime}(\tau)$ only has limit points at zero (so is neither away nor converges to zero), then the following study will be valid up to extracting subsequences of $p$.

Assume first that $f^{\prime}(\tau)$ is away from zero, i.e., $\liminf_{p}|f^{\prime}(\tau)|>0$. In order to study the isolated eigenvalues and associated eigenvectors of the model, we follow standard random matrix approaches as developed in e.g., [BN12, HLMNV13]. That is, to determine the isolated eigenvalues, we shall solve

for $\rho$ away from $\mathcal{S}_{p}\cup\mathcal{G}_{p}$ defined in Lemma 1. Such $\rho$ ensure the correct behavior of the resolvent $Q_{\rho}=(PW^{\sf T}WP-\rho I_{n})^{-1}$. Factoring out $PW^{\sf T}WP-\rho I_{n}$ and using Sylverster’s identity, the above equation is then equivalent to

By Lemma 1 (and some arguments to handle the dependence between $U$ and $Q_{\rho}$), $U^{\sf T}Q_{\rho}U$ tends to be deterministic in the large $n$ limit, and thus, using a perturbation approach along with the argument principle, we find that the isolated eigenvalues of $PW^{\sf T}WP+UBU^{\sf T}$ tend to be the values of $\rho$ for which $BU^{\sf T}Q_{\rho}U+I_{2k+1}$ has a zero eigenvalue, the multiplicity of $\rho$ being asymptotically the same as that of the aforementioned zero eigenvalue.

All calculus made, we have the following first main results.

Let Assumptions 1 and 2 hold and define the $k\times k$ matrix

As it shall turn out, the isolated eigenvalues identified in Theorem 2 are the only ones of practical interest for spectral clustering as they are strongly related to $J$. However, some other isolated eigenvalues may be found which we discuss here for completion (and thoroughly in the proof section).

Under the conditions of Theorem 2, if there exists a $\rho_{+}$ in a neighborhood of $\mathcal{H}_{p}$ such that $\det H_{\rho_{+}}=0$ with $H_{z}$ defined in (25), then there exist $\lambda_{j}^{p}\geq\ldots\geq\lambda^{p}_{j+m_{\rho_{+}}-1}$ eigenvalues of $L$ satisfying

where $m_{\rho}\geq 1$ is the multiplicity of zero as an eigenvalue of $H_{\rho}$. Note in particular that, if $t=0$ and $\mathcal{H}_{p}\cap\mathcal{S}_{p}^{c}\neq\emptyset$, then such $\rho_{+}$ exists. Figure 7, commented later, provides an example where a $\rho_{+}$ is found amongst the other isolated eigenvalues of $L$ (emphasized here in blue). Note that $\rho_{+}$ only depends on a weighted sum of the $\operatorname{tr}C_{i}^{2}$ and may even exist when $M=0$, $t=0$, and $T=0$. Intuitively, this already suggests that $\rho_{+}$ is only marginally related to the spectral clustering problem.

Operating the variable change $z\mapsto-f^{\prime}(\tau)z/f(\tau)$ in the expression of $G_{z}$, we may form the matrix $G_{-f(\tau)z/(2f^{\prime}(\tau))}$ the null eigenvalues of which are achieved for the values $-2f^{\prime}(\tau)\rho/f(\tau)$ where $\rho$ is defined in Theorem 2. While $G_{z}$ is ill-defined as $f^{\prime}(\tau)\to 0$, $G_{-f(\tau)z/(2f^{\prime}(\tau))}$ has a non trivial limit, which we denote $G^{0}_{z}$ and that allows for an extension of Theorem 2 to the case $f^{\prime}(\tau)\to 0$. In particular, $g_{a}(-f(\tau)z/(2f^{\prime}(\tau)))$ behaves similar to $2f^{\prime}(\tau)/(c_{0}f(\tau)z)$ for all $a\in\{1,\ldots,k\}$ and we have the following simpler expression.

Let Assumptions 1–2 hold and define the $k\times k$ matrixThere, $h^{0}(\tau,z)=\lim_{f^{\prime}(\tau)\to 0}h(\tau,z)$, $\Gamma^{0}_{z}=\lim_{f^{\prime}(\tau)\to 0}-f(\tau)/(2f^{\prime}(\tau))\Gamma_{-f(\tau)z/(2f^{\prime}(\tau))}$, and $D^{0}_{\tau,z}=\lim_{f^{\prime}(\tau)\to 0}-\frac{2f^{\prime}(\tau)}{f(\tau)}D_{\tau,-f(\tau)z/(2f^{\prime}(\tau))}$.

Define also $\mathcal{H}_{p}^{0}=\{x~{}|~{}h^{0}(\tau,x)=0\}$. Then, for $\rho^{0}$ at macroscopic distance from $\mathcal{H}_{p}^{0}\cup\{(f(0)-f(\tau))/f(\tau)\}$ such that $G^{0}_{\rho^{0}}$ has a zero eigenvalue of multiplicity $m^{0}_{\rho}$, there exist $\lambda_{j}^{p}\geq\cdots\geq\lambda_{j+m_{\rho}-1}^{p}$ ($j$ may depend on $p$) eigenvalues of $L$ satisfying

Similar to Remark 4, under the conditions of Theorem 3, if there exists $\rho_{+}^{0}$ in a small neighborhood of $\mathcal{H}_{p}^{\circ}$ such that $\det H^{0}_{\rho_{+}^{0}}=0$ with $H_{z}^{0}$ defined in (27), then there exist $\lambda_{j}^{p}\geq\ldots\geq\lambda_{j+m_{\rho_{+}^{0}}-1}$, eigenvalues of $L$ satisfying

with $m_{\rho_{+}^{0}}$ the multiplicity of the zero eigenvalue of $H^{0}_{\rho_{+}^{0}}$. Along with the eigenvalue $n$ and the eigenvalues identified in Theorem 3, this enumerates all the (asymptotic) isolated eigenvalues of $L$.

The two theorems above exhibit quite involved expressions that do not easily allow for intuitive interpretations. We shall see in Section 5 that these results greatly simplify in some specific scenarios of practical interest. We may nonetheless already extrapolate some elementary properties.

If an eigenvalue of $D_{\tau,\rho}$ diverges to infinity as $n,p\to\infty$, by the boundedness property of Stieltjes transforms, we find that $h(\tau,\rho)$ and $\Gamma_{\rho}$ remain bounded and, thus, the value $\rho$ cancelling the determinant of $G_{\rho}$ must go to infinity as well. This is the expected behavior of spiked models. This implies in particular that, if, for some $i,j$, $\|\mu_{i}^{\circ}\|\to\infty$, or $t_{i}\to\infty$, or $T_{ij}\to\infty$, as $n,p\to\infty$ slowly (thus disrupting from our assumptions), there will exist an asymptotically unbounded eigenvalue in the spectrum of $L$ (aside from the eigenvalue $n$). On the opposite, if for all $i,j$ those quantities vanish as $n,p\to\infty$, then $D_{\tau,z}$ is essentially zero in the limit, and thus, aside from the $\rho$’s solution to $h(\tau,\rho)=0$ (and from the eigenvalue $n$), no isolated eigenvalue can be found in the spectrum of $L$.

As a confirmation of the intuition captured in Remark 2, it now clearly appears from Theorem 3 that, as $f^{\prime}(\tau)=0$, the matrix $M$ does not contribute to the isolated eigenvectors of $L$ and thus the $\mu_{i}$’s can be anticipated not to play any role in the resulting spectral clustering methods. Similarly, from Theorem 2, if $f^{\prime\prime}(\tau)=0$, the cross-variances $\frac{1}{p}\operatorname{tr}C_{i}^{\circ}C_{j}^{\circ}$ will not intervene and thus cannot be discriminated over. Finally, letting $\frac{5f^{\prime}(\tau)}{8f(\tau)}=\frac{f^{\prime\prime}(\tau)}{2f^{\prime}(\tau)}$ discards the impact of the traces $\frac{1}{\sqrt{p}}\operatorname{tr}C_{i}^{\circ}$. This has interesting consequences in practice if one aims at discriminating data upon some specific properties.

2. Eigenvectors

Let us now turn to the central aspect of the article: the eigenvectors of $L$ (being the same as those of $L^{\prime}$, up to reordering).

To start with, note that, in both theorems, the eigenvalue $n$ is associated with the eigenvector $D^{\frac{1}{2}}1_{n}$. Since the eigenvector is completely explicit (which shall not be the case of the next eigenvectors), it is fairly easy to study independently without resorting to any random matrix analysis. Precisely, we have the following result for it.

with $\varphi\sim\mathcal{N}(0,I_{n})$ and $o(n^{-1})$ is meant entry-wise.

We can make the value of $\varphi$ explicit as follows. Recalling the definition (7) of $\psi$,

Note that the eigenvector $D^{\frac{1}{2}}1_{n}$ may then be used directly for clustering, with increased efficiency when the entries $t_{a}=\frac{1}{\sqrt{p}}\operatorname{tr}C_{a}^{\circ}$ of $t$ grow large for fixed $\frac{1}{p}\operatorname{tr}C_{a}^{2}$. But the eigenvector (asymptotically) carries no information concerning $M$ or $T$ and is in particular of no use if all covariances $C_{i}$ have the same trace.

For the other isolated eigenvectors, the study is much more delicate as we do not have an explicit expression as in Proposition 1. Instead, by statistical interchangeability of the class-$\mathcal{C}_{a}$ entries of, say, the $i$-th isolated eigenvector $\hat{u}_{i}$ of $L$, we may write

Assuming when needed unit multiplicity for the eigenvalue associated with $\hat{u}_{i}$, our objective is now twofold:

Class-wise Eigenvector Means. We first wish to retrieve the values of the $\alpha_{a}^{i}$’s. For this, note that

We shall evaluate these quantities by obtaining an estimator for the $k\times k$ matrix $\frac{1}{p}J^{\sf T}\hat{u}_{i}^{\sf T}\hat{u}_{i}^{\sf T}J$. The diagonal entries of the latter will allow us to retrieve $|\alpha_{a}^{i}|$ and the off-diagonal entries will be used to decide on the signs of $\alpha_{1}^{i},\ldots,\alpha_{k}^{i}$ (up to a convention in the sign of $\hat{u}_{i}$).

Class-wise Eigenvector Inner and Cross Fluctuations. Our second objective is to evaluate the quantities

between the fluctuations of two eigenvectors indexed by $i$ and $j$ on the subblock indexing $\mathcal{C}_{a}$. In particular, letting $i=j$, $\sigma_{a}^{i,i}=(\sigma_{a}^{i})^{2}$ from the previous definition (8). For this, it is sufficient to exploit the previous estimates and to evaluate the quantities $\hat{u}_{i}^{\sf T}\mathcal{D}(j_{a})\hat{u}_{j}$. But, to this end, for lack of a better approach, we shall resort to estimating the more involved object $\frac{1}{p}J^{\sf T}\hat{u}_{i}\hat{u}_{i}^{\sf T}\mathcal{D}(j_{a})\hat{u}_{j}\hat{u}_{j}^{\sf T}J$, from which $\hat{u}_{i}^{\sf T}\mathcal{D}(j_{a})\hat{u}_{j}$ can be extracted by division of any entry $m,l$ by $\alpha_{m}^{i}\alpha_{l}^{i}$. The specific fluctuations of the eigenvector $D^{\frac{1}{2}}1_{n}$ as well as the cross-correlations between any eigenvector and $D^{\frac{1}{2}}1_{n}$ will be treated independently.

The two aforementioned steps are successively derived in the next sections, starting with the evaluation of the coefficients $\alpha_{a}^{i}$.

Consider the case where $f^{\prime}(\tau)$ is away from zero. First observe that, for $\lambda^{p}_{j},\ldots,\lambda^{p}_{j+m_{\rho}-1}$ a group of the identified isolated eigenvalues of $L$ all converging to the same limit (as per Theorem 2 or Remark 4), the corresponding eigenspace is (asymptotically) the same as the eigenspace associated with the corresponding deterministic eigenvalue $\rho$ in the spectrum of $PW^{\sf T}WP+UBU^{\sf T}$. Denoting $\hat{\Pi}_{\rho}$ a projector on the former eigenspace, we then have, by Cauchy’s formula and our approximation of Theorem 1,

for a small (positively oriented) closed path $\gamma_{\rho}$ circling around $\rho$, this being valid for all large $n$, almost surely.

Using matrix inversion lemmas, the right-hand side of (9) can be worked out and reduced to an expression involving the matrix $G_{z}$ of Theorem 2. It then remains to perform a residue calculus on the final formulation which then leads to the following result.

Let Assumptions 1 and 2 hold and assume $f^{\prime}(\tau)$ away from zero. Let also $\lambda^{p}_{j},\ldots,\lambda^{p}_{j+m_{\rho}-1}$ be a group of isolated eigenvalues of $L$ and $\rho$ the associated deterministic approximate (of multiplicity $m_{\rho}$) as per Theorem 2, and assume that $\rho$ is uniformly away from any other eigenvalue retrieved in Theorem 2. Further denote $\hat{\Pi}_{\rho}$ the projector on the eigenspace of $L$ associated to these eigenvalues. Then,

Similarly, when $f^{\prime}(\tau)\to 0$, we obtain, with the same limiting approach as for Theorem 3, the following estimate.

Let Assumptions 1 and 2 hold and assume $f^{\prime}(\tau)\to 0$. Let $\lambda^{p}_{j},\ldots,\lambda^{p}_{j+m_{\rho}-1}$ be a group of isolated eigenvalues of $L$ and $\rho^{0}$ the corresponding approximate (of multiplicity $m_{\rho^{0}}$) defined in Theorem 3, and assume that $\rho^{0}$ is uniformly away from any other eigenvalue retrieved in Theorem 3. Further denote $\hat{\Pi}_{\rho^{0}}$ the projector on the eigenspace associated to these eigenvalues. Then,

almost surely, whereThere, $\Xi_{\rho}^{\circ}=\lim_{f^{\prime}(\tau)\to 0}-\frac{2f^{\prime}(\tau)}{f(\tau)}\Xi_{-f(\tau)\rho/(2f^{\prime}(\tau))}$.

Correspondingly to Remarks 4 and 5, we have the following complementary result for the isolated eigenvalues satisfying $h(\tau,\rho)\to 0$.

In addition to Theorem 4, it can be shown (see the proof section) that, if $\rho_{+}$ is an isolated eigenvalue as per Remark 4 having multiplicity one, then with similar notations as above

almost surely. The same holds for $\rho_{+}^{0}$ from Remark 5. As such, as far as spectral clustering is concerned, the eigenvectors forming the (dimension one) eigenspace $\hat{\Pi}_{\rho_{+}}$ cannot be used for unsupervised classification.

From this remark, we shall from now on adopt the following convention. The finitely many isolated eigenvalue-eigenvector pairs $(\rho_{i},\hat{u}_{i})$ of $L$, excluding those for which (at least on a subsequence) $h(\tau,\rho)\to 0$, will be denoted in the order $\rho_{1}\geq\rho_{2}\geq\ldots$, with possibly equal values of $\rho_{i}$’s to account for multiplicity. In particular, $\hat{u}_{1}=\frac{D^{\frac{1}{2}}1_{n}}{\sqrt{1_{n}^{\sf T}D1_{n}}}$. The eigenvalue-eigenvector pairs $(\rho,\hat{u})$ for which $h(\tau,\rho)\to 0$ will no longer be listed.

Let us consider the case where $\rho$ is an isolated eigenvalue of unit multiplicity with associated eigenvector $\hat{u}_{i}$ (thus $\hat{\Pi}_{\rho}=\hat{u}_{i}\hat{u}_{i}^{\sf T}$). According to (8), we may now obtain the expression of $\alpha_{1}^{i},\ldots,\alpha_{k}^{i}$ as follows:

$\sqrt{\frac{1}{n_{1}}[J^{\sf T}\hat{u}_{i}\hat{u}_{i}^{\sf T}J]_{11}}=|\alpha_{1}^{i}|$ allows the retrieval of $\alpha_{1}^{i}$ up to a sign shift. We may conventionally call this nonnegative value $\alpha_{1}^{i}$ (if this turns out to be zero, we may proceed similarly with entry $(2,2)$ instead).

for all $1<a\leq k$, $\sqrt{\frac{1}{n_{a}}[J^{\sf T}\hat{u}_{i}\hat{u}_{i}^{\sf T}J]_{aa}}\times{\rm sign}([J^{\sf T}\hat{u}_{i}\hat{u}_{i}^{\sf T}J]_{1a})$ provides $\alpha_{a}^{i}$ up to a sign shift which is consistent with the aforementioned convention, and thus we may redefine $\alpha_{a}^{i}=\sqrt{\frac{1}{n_{a}}[J^{\sf T}\hat{u}_{i}\hat{u}_{i}^{\sf T}J]_{aa}}\times{\rm sign}([J^{\sf T}\hat{u}_{i}\hat{u}_{i}^{\sf T}J]_{1a})$.

An alignment metric between the span of $\hat{\Pi}_{\rho}$ and the sought-for subspace ${\rm span}(j_{1},\ldots,j_{k})$ may be given by

with $(c^{-1})_{i}=1/c_{i}$ and corresponds in practice to the extent to which the eigenvectors of $L$ are close to linear combinations of the base vectors $\frac{j_{1}}{\sqrt{n_{1}}},\ldots,\frac{j_{k}}{\sqrt{n_{k}}}$.

Remark 11 may be straightforwardly applied to observe a peculiar (and of fundamental application reach) phenomenon, when $M=0$, $t=0$ and the kernel is such that $f^{\prime}(\tau)\to 0$.

If $M=0$, $t=0$, and $f^{\prime}(\tau)\to 0$, note that $G^{0}_{x}=h^{0}(\tau,x)I_{k}+D^{0}_{\tau,x}\Gamma^{0}_{x}$ satisfies $G^{0\prime}_{x}=\frac{h^{0}(\tau,x)^{\prime}}{h^{0}(\tau,x)}G^{0}_{x}\Gamma^{0}_{x}-\frac{1}{x}(h^{0}(\tau,x)I_{k}-G^{0}_{x})$ (the rightmost term arising from $D^{0}_{\tau,x}\Gamma_{x}=G^{0}_{x}-h^{0}(\tau,x)I_{k}$), so that, for $x=\rho^{0}$, since $(V_{l,\rho^{0}}^{0})^{\sf T}G_{\rho^{0}}^{0\prime}=0$, we find that

almost surely. It shall also be seen through an example in Section 5 that this is no longer true in general if $f^{\prime}(\tau)$ is away from zero. As such, there is an asymptotic perfect alignment in the regime under consideration if only $T$ is non vanishing, provided one takes $f^{\prime}(\tau)\to 0$. In this case, it is theoretically possible, as $n,p\to\infty$, to correctly cluster all but a vanishing proportion of the $x_{i}$.

Remark 12 is somewhat unsettling at first look as it suggests the possibility to obtain trivial clustering by setting $f^{\prime}(\tau)=0$, under some specific statistical conditions. This is in stark contradiction with Assumption 1 which was precisely laid out so to avoid trivial behaviors. As a matter of fact, a thorough investigation of the conditions of Remark 12 was recently performed in our follow-up work [CK16], where it is shown that clustering becomes non-trivial if now $\frac{1}{p}\operatorname{tr}C_{a}^{\circ}C_{b}^{\circ}$ is of order $O(p^{-\frac{1}{4}})$ rather than $O(1)$. This conclusion, supported by conclusive simulations, explicitly says that classical clustering methods (based on the Gaussian kernel for instance) necessarily fail in the regime where $\|T\|=O(p^{-\frac{1}{4}})$ while by taking $f^{\prime}(\tau)=0$ non-trivial clustering is achievable. This observation is used to provide a novel subspace clustering algorithm with applications in particular to wireless communications. See [CK16] for more details.

Let us now turn to the evaluation of the fluctuations and cross-fluctuations of the isolated eigenvectors of $L$ around their projections onto ${\rm span}(j_{1},\ldots,j_{k})$. As far as inner fluctuations are concerned, first remark that, from Proposition 1, we already know the class-wise fluctuations of the eigenvector $D^{\frac{1}{2}}1_{n}$ (these are proportional to $\frac{1}{p}\operatorname{tr}C_{a}^{2}$ for class $\mathcal{C}_{a}$), and thus we may simply work on the remaining eigenvectors. We are then left to evaluating (i) the inner and cross fluctuations involving eigenvectors $\hat{u}_{i}$, $\hat{u}_{j}$, for $i,j>1$ ($i$ may equal $j$), and (ii) the cross fluctuations between $\hat{u}_{1}$ (that is $(1_{n}^{\sf T}D_{n})^{-\frac{1}{2}}D^{\frac{1}{2}}1_{n}$) and eigenvectors $\hat{u}_{i}$, $i>1$.

For readability, from now on, we shall use the shortcut notation $\mathcal{D}_{a}\triangleq\mathcal{D}(j_{a})$. For case (i), to estimate

we need to evaluate $\hat{u}_{i}^{\sf T}\mathcal{D}_{a}\hat{u}_{j}$. However, $\hat{u}_{i}^{\sf T}\mathcal{D}_{a}\hat{u}_{j}$ may not be directly estimated using a mere Cauchy integral approach as previously (unless $i=j$ for which alternative approaches exist). To work this around, we propose instead to estimate

Indeed, if $\hat{u}_{i}$ has a non-trivial projection onto ${\rm span}(j_{1},\ldots,j_{k})$ (in the other case, $\hat{u}_{i}$ is of no interest to clustering), then there exists at least one index $a\in\{1,\ldots,k\}$ for which $\frac{1}{p}j_{a}^{\sf T}\hat{u}_{i}=\frac{c_{a}}{c_{0}}\alpha_{a}^{i}$ is non zero. The same holds for $\hat{u}_{j}$, and thus $\hat{u}_{i}^{\sf T}\mathcal{D}_{a}\hat{u}_{j}$ can be retrieved by dividing a specific entry $(m,l)$ of (10) by the appropriate $\alpha_{m}^{i}$ and $\alpha_{l}^{j}$.

with obvious notations and with $\mathcal{Q}_{z}=\left(PW^{\sf T}WP+UBU^{\sf T}-zI_{n}\right)^{-1}$.

For case (ii), note from Proposition 1 that, in the first order, $\hat{u}_{1}$ is essentially the vector $\frac{1_{n}}{\sqrt{n}}$ of norm $1$ plus fluctuations of norm $O(n^{-\frac{1}{2}})$. If one were to evaluate $\hat{u}_{1}^{\sf T}\mathcal{D}_{a}\hat{u}_{i}$, $i>1$, as previously done, this would thus provide an inaccurate estimate to capture the cross-fluctuations. However, since the fluctuating part of $\hat{u}_{1}$ is well understood by Remark 8, and is in particular directly related to $\psi$, defined in (7), we shall here estimate instead $\psi^{\sf T}\mathcal{D}_{a}\hat{u}_{i}$, which can be obtained from $\psi^{\sf T}\mathcal{D}_{a}\hat{u}_{i}\hat{u}_{i}^{\sf T}\frac{J}{\sqrt{p}}$, the latter being in turn obtained, in case of unit multiplicity, from

Before presenting our results, we need an additional technical result, mostly borrowed from our companion article [BC16].

Under the conditions and notations of Lemma 1, for $z_{1},z_{2}$ (sequences of) complex numbers at macroscopic distance from the eigenvalues of $PW^{\sf T}WP$, as $n\to\infty$,

In particular, as a consequence of Lemma 2, we have the following identities

The matrix $R^{z_{1}z_{2}}$ is strongly related to the derivative of the $g_{a}(z)$’s. In particular, we have that

With this lemma at hand, we are in position to introduce the following class-wise fluctuation results.

Under the setting and notations of Theorem 4, as $n\to\infty$,

Under the setting and notations of Theorem 5, as $n\to\infty$,

with $[E_{a;z_{1}z_{2}}^{0;J}]_{ij}\triangleq\frac{c_{a}}{c_{0}}\frac{1}{z_{1}z_{2}}{\bm{\delta}}_{ia}{\bm{\delta}}_{ja}$ and $E_{a;z_{1}z_{2}}^{0;\psi}\triangleq\frac{c_{a}}{c_{0}}\frac{2}{p}\operatorname{tr}C_{a}^{2}\frac{1}{z_{1}z_{2}}$.

These results are much more involved than those previously obtained and do not lead themselves to much insight. Nonetheless, we shall see in Section 5 that this greatly simplifies when considering special application cases.

For $i,j>1$, from the convention on the signs of $\hat{u}_{i}$ and $\hat{u}_{j}$ given by Remark 10, we get immediately that

for any index $b,d\in\{1,\ldots,k\}$ for which $\alpha_{b}^{i},\alpha_{d}^{j}\neq 0$, with in particular $(\sigma_{a}^{i})^{2}=\sigma_{a}^{ii}$. As for the case $i=1$, $j>1$, corresponding to $\hat{u}_{1}=(1_{n}^{\sf T}D1_{n})^{-\frac{1}{2}}D^{\frac{1}{2}}1_{n}$, we may similarly impose the convention that $1_{n}^{\sf T}\hat{u}_{1}>0$ (for all large $n$), which is easily ensured as $\hat{u}_{1}=\frac{1_{n}}{\sqrt{n}}+o(1)$ almost surely. Then we find that

again for all $d\in\{1,\ldots,k\}$ for which $\alpha_{d}^{j}\neq 0$.

An illustration of the application of the results of Sections 4.2.1 and 4.2.2 to determine the class-wise means, fluctuations, and cross-fluctuations of the eigenvectors, as discussed in the early stage of Section 4.2, is depicted in Figure 5. There, under the same setting as in Figure 4 (that is, three classes with various means and covariances under Gaussian kernel), we display in class-wise colored crosses the $n$ couples $([\hat{u}_{i}]_{a},[\hat{u}_{j}]_{a})$, $a=1,\ldots,n$, for the $i$-th and $j$-th dominant eigenvectors $\hat{u}_{i}$ and $\hat{u}_{j}$ of $L$. The left figure is for $(\hat{u}_{1},\hat{u}_{2})$ and the right figure for $(\hat{u}_{2},\hat{u}_{3})$. On top of these values are drawn the ellipses corresponding to the one- and two-dimensional standard deviations of the fluctuations, obtained from the covariance matrix $\left[\begin{smallmatrix}(\sigma_{i})_{a}^{2}&(\sigma_{ij})_{a}\\ (\sigma_{ij})_{a}&(\sigma_{j})_{a}^{2}\end{smallmatrix}\right]$.

In order to get a precise understanding of the behavior of the spectral clustering based on $L$, we shall successively constrain the conditions of Assumption 1 so to obtain meaningful results.

Special cases

The results obtained in Section 4 above are particularly difficult to analyze for lack of tractability of the functions $g_{1}(z),\ldots,g_{k}(z)$ (even though from a numerical point of view, these can be accurately estimated as the output of a provably converging fixed point algorithm; see [BC16]). In this section, we shall consider three scenarios for which all $g_{a}(z)$ assume a constant value:

We first assume $C_{1}=\cdots=C_{k}$. In this setting, only $M$ can be discriminated over for spectral clustering. We shall show that, in this case, up to $k-1$ isolated eigenvalues can be found in-between each pair of connected components in the limiting support of the empirical spectrum of $PW^{\sf T}WP$, in addition to the isolated eigenvalue $n$. But more importantly, we shall show that, as long as $f^{\prime}(\tau)$ is away from zero, the kernel choice is asymptotically irrelevant (so one may take $f(x)=x$ with the same asymptotic performance for instance).

Next, we shall consider $\mu_{1}=\cdots=\mu_{k}$ and take $C_{a}=(1+p^{-1/2}\gamma_{a})C$ for some fixed $\gamma_{1},\ldots,\gamma_{k}$. This ensures that $T$ vanishes and thus only $t$ can be used for clustering. There we shall surprisingly observe that a maximum of two isolated eigenvalues altogether can be found in the limiting spectrum and that $\hat{u}_{1}$ (associated with eigenvalue $n$) and the hypothetical $\hat{u}_{2}$ are extremely correlated. This indicates here that clustering can be asymptotically performed based solely on $\hat{u}_{1}$.

Finally, to underline the effect of $T$ alone, we shall enforce a model in which $\mu_{1}=\cdots=\mu_{k}$, $n_{1}=\cdots=n_{k}=n/k$, and $C_{a}$ is of the form $\operatorname{\mathcal{D}}(D_{1},\ldots,D_{1},D_{2},D_{1},\ldots,D_{1})$ with $D_{2}$ in the $a$-th position. There we shall observe that the hypothetical eigenvalues have multiplicity $k-1$, thus precluding a detailed eigenvector analysis.

Assume that for all $a$, $C_{a}=C$ (which we may further relax by merely requiring that $t\to 0$ and $T\to 0$ in the large $p$ limit). For simplicity of exposition, we shall require in that case the following.

As $p\to\infty$, the empirical spectral measure $\frac{1}{p}\sum_{i=1}^{p}{\bm{\delta}}_{\lambda_{i}(C)}$ converges weakly to $\nu$. Besides,

This assumption ensures, along with the results from [SC95] and [BS98], that $g_{1}(z),\ldots,g_{k}(z)$ all converge towards a unique $g(z)$, solution to the implicit equation

In this setting, only the matrix $M$ can be discriminated upon to perform clustering and thus we need to take here $f^{\prime}(\tau)$ away from zero to obtain meaningful results which, since $\tau\to 2\int u\nu(du)$, merely requires that $f^{\prime}(2\int u\nu(du))\neq 0$. Starting then from Theorem 2 and using the fact that $Mc=0$, we get

withThe $o(1)$ term accounts for $g(z)$ being here a limiting quantity rather than a finite $p$ deterministic equivalent.

The values of $\rho\in\mathcal{S}^{\prime}=\mathcal{S}\cup\{\rho;h(\tau,\rho)=0\}$ for which $G_{\rho}$ (asymptotically) has zero eigenvalues are such that $I_{k}+M^{\sf T}\left[I_{p}+g(\rho)C\right]^{-1}M\operatorname{\mathcal{D}}(c)$ is singular. By Sylverster’s identity, this is equivalent to looking for such $\rho$ satisfying

A visual representation of $x({\bf g})$ is provided in Figure 6. Now, since $Mc=0$, $M$ has maximum rank $k-1$ and thus, by Weyl’s interlacing inequalities and Assumption 3, there asymptotically exist up to $k-1$ isolated eigenvalues in-between each connected component of ${\rm supp}(\nu)$.

Additionally, since $t=0$, as per Remark 4, if there exists $\rho_{+}$ away from $\mathcal{S}$ such that $h(\tau,\rho_{+})=0$, that is for which $-g(\rho_{+})^{-1}=\left(\frac{5f^{\prime}(\tau)}{4f(\tau)}-\frac{f^{\prime\prime}(\tau)}{f^{\prime}(\tau)}\right)\int u^{2}\nu(du)$, then an additional isolated eigenvalue of $L$ may be found.

Gathering the above, we thus have the following corollary of Theorem 2.

then there exists an isolated eigenvalue of $L$, which is asymptotically well approximated by $-\frac{2f^{\prime}(\tau)}{f(\tau)}\rho_{j}^{i}+\frac{f(0)-f(\tau)+\tau f^{\prime}(\tau)}{f(\tau)}$, where

there is an additional corresponding isolated eigenvalue in the spectrum of $L$ given by $-\frac{2f^{\prime}(\tau)}{f(\tau)}\rho_{+}+\frac{f(0)-f(\tau)+\tau f^{\prime}(\tau)}{f(\tau)}$ with