3
$\begingroup$

We have matrix data $X$ which is $n\times d$. We use the covariance matrix/ design matrix/ gram matrix $X^T X$ to perform least-squares/ PCA. I compute the eigen basis representation of said matrix

$$X^TX = \sum_{i=1}^d \lambda_i u_i u_i^T.$$

I notice that $\lambda_d \geq \sqrt{n}$. Can I infer that there must have been at least $\sqrt{n}$ data $\{x_t\}_{t=1}^n$ (which forms the rows of the big matrix $X$) from the direction prependicular to $u_1$

PS : assume data $\{x_t\}$ to come from the $d$-dimensional sphere so that $\|x\|_2 = 1$

PS: I would be very tempted to say the number of data $x_t$ close to some region of $u_d$ is more than $\sqrt{n}$, but I guess thats asking for too much

$\endgroup$
0

1 Answer 1

1
$\begingroup$

Counter-Example:

Suppose $d=2$ and define $$a_1 := e^{i\frac{\pi}{8}}, \ a_2 := e^{-i\frac{\pi}{8}}, \ a_3 := e^{i\frac{7\pi}{8}}, \ a_4 := e^{-i\frac{7\pi}{8}} \in \mathbb{C} \simeq \mathbb{R}^2$$ Let $x_1,x_2,...$ be iid. random variables such that $\mathbb{P}(x_j = a_i) = \frac{1}{4}$ for all $j \in \mathbb{N}$ and $i \in \{1,2,3,4\}$.

Let $X_n$ be the random $(n\times d)$-matrix given by $\big((X_n)_{j,1},(X_n)_{j,2}\big) = x_j$, then the strong law of large numbers gives the convergence $$ \big( \frac{1}{n} X_n^T X_n \big)_{i,k} = \frac{1}{n} \sum\limits_{j=1}^n X_{j,i} X_{j,k} \xrightarrow{n \rightarrow \infty}_{a.s.} \mathbb{E}[X_{1,i} X_{1,k}] $$ and thus $$ \frac{1}{n} X_n^T X_n \xrightarrow{n \rightarrow \infty}_{a.s.} \left( \begin{array}{cc} \mathbb{E}[\rm{Re}(x_1)^2] & \mathbb{E}[\rm{Re}(x_1) \, \rm{Im}(x_1)] \\ \mathbb{E}[\rm{Re}(x_1) \, \rm{Im}(x_1)] & \mathbb{E}[\rm{Im}(x_1)^2] \end{array} \right) = \left( \begin{array}{cc} \rm{Re}(a_1)^2 & 0 \\ 0 & \rm{Im}(a_1)^2 \end{array} \right) $$ Since the convergence of the matrix implies convergence of the Eigenvalues, we have \begin{align*} & \lambda_1(\frac{1}{n} X_n^T X_n) \xrightarrow{n \rightarrow \infty}_{a.s.} \rm{Re}(a_1)^2\\ & \lambda_2(\frac{1}{n} X_n^T X_n) \xrightarrow{n \rightarrow \infty}_{a.s.} \rm{Im}(a_1)^2 \end{align*} By multiplicativity of the eigenvalues we have shown, that $\frac{1}{\sqrt{n}}\lambda_2(X_n^T X_n) \xrightarrow{n \rightarrow \infty}_{a.s.} \infty$, which means for large $n$ the condition $\lambda_d(X_n^T X_n) \geq \sqrt{n}$ will hold with high probability. However by construction the data-points are never close to either $u_1 = (1,0)$ or $u_2 = (0,1)$.

For larger, constant $d$ one can find similar counter examples.

The problem becomes more interesting when $d$ and $n$ are assumed to be about the same size, i.e. let $d\rightarrow \infty$ and $n \rightarrow \infty$ such that $\frac{d}{n} \rightarrow y \in (0,\infty)$. However here too there exists a limit theorem (see 'Spectral Analysis of Large Dimensional Random Matrices' by Bai and Silverstein, Theorem 3.10) which shows, that the eigenvalues $\lambda_j(X_n^T X_n)$ will either grow with $\mathcal{O}(n)$ or be zero. This already indicates, that the condition $\lambda_d \geq \sqrt{n}$ is too weak for the wanted conclusion.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .