Components of a Gram matrix and its eigenvalues

Question

The Gram Matrix is defined as $$\sum_{i=1}^n X_iX_i^T,$$ where $X_i$ is drawn from the unit sphere based according to some continuous distribution (Relation between eigenvalues and the gram matrix for a discrete case counter example).

Consider a $3$-D case:

I know that $\lambda_1 \sim n$, $\lambda_2 \sim \sqrt{n}$, $\lambda_3 \sim 1$ (these represent growth rates) and $\lambda_1 \ge \lambda_2 \ge \lambda_3$. These growth rates of the eigenvalues tell me that there must be regions in $\mathcal{S}^2$ which have been sampled more and regions which have been sampled less. (What's the physical meaning of the eigenvectors of the Gram/Kernel matrix?)

My question is :

Can I say anything formally about which regions have been sampled more and which have been sampled less. (For example intuitively one can perhaps say any region in the direction of $U_1$ (eigenvector) has been sampled more and $U_3$ has been sampled less, but does this say anything about how $X_t$s were sampled?)

Answer 1

Let's assume $\mathbb{E}[X_i]=0_{\mathbb{R}^d}$, since PCA makes little sense otherwise. (Always normalize your data points by subtracting the empirical mean.)

I'm afraid your assumption, that $\lambda_1 \sim n$, $\lambda_2 \sim \sqrt{n}$ and $\lambda_3 \sim 1$ is false.

When the data ponits are iid, there will always be some cut-off point $m \leq d$ (indepentent of $n$) such that $\lambda_i \sim n$ when $i \leq m$ and $\lambda_i = 0$ for $i>m$ almost surely. This can be seen with the strong law of large numbers similarly to the counter expamle, you have already linked. The condition, that $X_i$ needs to have a continuous distribution on $\mathbb{S}^{d-1}$ only ensures, that this cut-off point is $m=d$, which means all eigenvalues grow with speed $\mathcal{O}(n)$.

There are still very weak probabilistic statements one can make about the distances of data points to $u_i$.

If we mulitply the Gram-Matrix by $\frac{1}{n}$ we get the empirical covariance matrix $S_n := \frac{1}{n} Z_n^T Z_n$, where $Z_n$ is the random matrix given by $(Z_n)_{i,\cdot} = X_i^T$. It is easily seen, that $$ \mathbb{E}[S_n] := (\mathbb{E}[(S_n)_{i,j}])_{i, j \leq d} = \left(\mathbb{E}\left[\frac{1}{n} \sum\limits_{k=1}^n Z_{k,i} Z_{k,j}\right]\right)_{i, j \leq d} = \left(\rm{Cov}\left[(X_{1})_i ,(X_{1})_j\right]\right)_{i, j \leq d} =: S \ . $$ Now if $\eta_i$ are the ordered eigenvalues and $v_i$ the eigenvectors of $S$, then the strong law of large numbers will again ensure, that $u_i \xrightarrow{n \rightarrow \infty}_{a.s.} v_i$ for each $i \leq d$.

Also for any measurable set $A \subset \mathbb{S}^{d-1}$ the strong law of large numbers gives $$ \frac{1}{n} \sum\limits_{j=1}^n 1_A(X_j) \xrightarrow{n \rightarrow \infty}_{a.s.} \mathbb{P}(X_1 \in A) \ . $$ Now for fixed $i \leq d$, we can use both almost sure convergences to get $$ \frac{1}{n} \sum\limits_{j=1}^n 1_{B_\varepsilon(u_i)}(X_j) \xrightarrow{n \rightarrow \infty}_{a.s.} \mathbb{P}(X_1 \in B_\varepsilon(v_i)) \ . $$ Since $S_n$, $v_i$ and $\mathbb{P}(X_1 \in B_\varepsilon(v_i))$ can be calculated with only knowledge about the distribution of $X_1$ and we can thus calculate to which value the percentage of data points within an $\varepsilon$-ball of $u_i$ will converge for large $n$.

While this result may be improved by using tail bounds to find out just how fast the empirical probability will converge to the limiting probability, it says nothing about the data points having to be close to $u_1$ but only, that they have to be (on average) closer to $u_1$ than $u_2,...,u_d$.