# Proof/Example of finding co-variance matrix of normalized data matrix

This might be a very trivial question but I'm asking because I couldn't found any proper explanation. I'm currently studying Principle Component Analysis (PCA) and came across this post. Here it's written that if $X$ is normalized data matrix, then co variance of $X$ can be given by:

$$\Sigma = X^TX/(N-1)$$

I've found one example here, but the answer is not what I'm looking for. Here is another example, but I don't understand why the equation are given as data matrix and what is the value of $N$ and $Y$? If $N$ is number of data points, the why it's changing in the table?

Also I don't understand how projection of $X$ on axis $w$ is given by $Xw$. Can anyone give geometrical explanation of this formula? As per this notes (on page number 5), the projection is taken as dot product ($X^Tw$), which makes complete sense to me. So what is the difference between this two formula of projection?

Ok, so there seems to be several questions in one here. Let's talk about the covariance estimation stuff first. Firstly, by definition, the covariance of a random variable (a theoretical property of an abstract variable) is given by: $$\text{Cov}(U,V) = \mathbb{E}[(U-\mathbb{E}[U])(V-\mathbb{E}[V])^T]$$ In the ML case, $U$ and $V$ can be thought of as the features.

In general, $\text{Cov}(U,V)$ cannot be computed because we don't know the distributions of $U$ and $V$. However, given some data, we can estimate the covariance in the form of the empirical (or sample) covariance matrix $\Sigma$. However, there are two ways to estimate the sample covariance: $$\Sigma = \frac{1}{f(n)}\sum_i (x_i - \mu_x)(x_i - \mu_x)^T$$ where $\mu_x=\frac{1}{n} \sum_k x_k$ is the empirical mean and $f$ can either be $f(n)=n-1$ or $f(n)=n$. Both will converge to the right answer i.e. are consistent, but using $n-1$ guarantees the estimator is unbiased. Nonetheless, people freely use either, especially preferring the latter when they assume the mean is known. See also this article and this question. See Bessel's correction for more discussion on this too. (Note that $f(n)=n$ is what you should use if you have access to a complete population or have access to the true population mean though!).

As for this question:

I don't understand why the equation are given as data matrix and what is the value of $N$ and $Y$?

In general, the covariance is useful for quantifying how much two variables covary i.e. how they change together. (e.g. in ML how similar two features are). In your link, $X$ and $Y$ are simply different variables, between which they are computing the covariance. The example is somewhat confusing in that they appear to use $N$ for two things: (1) for their original variables they are looking at two sets of sets of data, where $N$ is the size of each subset and hence variable, and (2) the number of data points after combining the subsets. But I'm not sure honestly and don't have the motivation time to decipher it.

Next let me clear up some issues that come up because of conventions. In general, when people write a vector $x_k$, it is assumed that it is a column vector, i.e. $x_k\in\mathbb{R}^{m\times 1}$. Thus, given a dataset $\{x_i\}_{i=1}^n$, the expression $x_ix_i^T \in\mathbb{R}^{m\times m}$ is an outer product.

However, in statistics and ML, people usually work with a data matrix $X\in\mathbb{R}^{n\times m}$, where the rows are the data points. In this formulation, each data point is a row vector when part of $X$. Hence there are transposes in unexpected places sometimes.

Another convention is to always work with centered data, via $x_i\leftarrow x_i - \mu_x\;\forall\; i$. Let's go with unbiased estimator. Then we can just use $f(n)=n-1$. Thus the sample covariance matrix becomes $$\Sigma = \frac{1}{n-1}\sum_i x_i x_i^T$$

Let's derive the matrix form (as in here). Let $X\in\mathbb{R}^{n\times m}$. Notice that $X^TX\in\mathbb{R}^{m\times m}$, which makes sense. Then: \begin{align} [X^TX]_{ij} &= \sum_k [X^T]_{ik} [X]_{kj} \\ &= \sum_k [X]_{ki} [X]_{kj} \\ &= \sum_k x_{ki} x_{kj} \\[2mm] &= \sum_k \begin{bmatrix} x_{k1}^2 & \cdots & x_{k1}x_{km} \\ \vdots & \ddots & \vdots \\ x_{k1}x_{km} & \cdots & x_{km}^2 \end{bmatrix}_{ij} \\ &= \sum_k [x_kx_k^T]_{ij} \\ &= \left[ \sum_k x_k x_k^T \right]_{ij} \end{align} remembering that the $x_k$'s are column vectors. This shows $X^TX/(n-1)=\sum_kx_kx_k^T/(n-1)$.

Now for the projection stuff. Recall that in PCA we are looking for a new space for our $m$-dimensional points to live. Thus, each axis $u_j$ of our new space is an $m$ dimensional vector. (When we dimensionally reduce with PCA, we choose fewer axes in the new space, but each new axis itself is still fundamentally $m$-dimensional)

We want to project a vector $x_k\in\mathbb{R}^{m\times 1}$ onto $u_j\in\mathbb{R}^{m\times 1}$. The dot product giving the projection is simply $x_k^T u_j$. For $u=(u_1,\ldots,u_\ell)\in\mathbb{R}^{m\times \ell}$ as the new axes, the complete projection is simply $(x_k^Tu)^T=u^Tx_k\in\mathbb{R}^{\ell\times 1}$ written as a column vector.

On the other hand, in $X\in\mathbb{R}^{n\times m}$, the data are written in rows. So given an axis $u_\alpha\in \mathbb{R}^{m\times 1}$, we get the projection of the entire dataset on the principal component defined by $u_\alpha$ is $Xu_\alpha \in \mathbb{R}^{n\times 1}$ (i.e. a list of scalars, one for each datum). The geometrical explanation is that we simply project every row $x_i$ onto the axis vector $u_\alpha$, and measure the length its projection assumes (i.e. to what extent the axis "explains" each data point).

In other words, both ways of writing things are fine!

Hopefully this (excessively long) clarification helps a bit (and sorry if I told you a bunch of things you already knew).

Edit (071718): in response to the comment, let's make clear the relation between our covariance formulas. Let $\{U_i\}$ be a set of random variables, which we have centered, and $\Sigma$ be the sample covariance matrix between them. Then we can estimate it via: $$\text{Cov}(U_i, U_j) \approx \Sigma_{ij} = \frac{1}{n-1} \sum_k (U_{ki} - \mu_i)(U_{kj} - \mu_j) = \frac{1}{n-1} \sum_k U_{ki} U_{kj}$$ which is component $i,j$ of $\Sigma$. The means disappear because they are centered.
On the other hand, consider a centered dataset $X\in\mathbb{R}^{n\times m}$ with $m$ features. Then the empirical covariance matrix is written: $$\Sigma = \frac{1}{n-1} \sum_i x_i x_i^T = \frac{1}{n-1} \sum_i \begin{bmatrix} x_{i1}^2 & \cdots & x_{i1} x_{im} \\ \vdots & \ddots & \vdots \\ x_{i1} x_{im} & \cdots & x_{im}^2 \end{bmatrix}$$ $$\therefore\;\; \Sigma_{ij} = \frac{1}{n-1}\sum_k x_{ki} x_{kj}$$ Thus the formula shown in places like this are simply the components of the same matrix.
• Thanks. Nice answer, +1 for that. The co variance matrix part makes complete sense to me, but in projection part, what do you mean by "the complete projection"? You said complete projection is transpose of the dot product, but isn't the dot product ($x_k^Tu$) scalar? What is the meaning of applying transpose of the scalar? Jul 14, 2018 at 11:08
• @Kaushal28 Notice that $u$ is a matrix, whose columns are the axes $u_j$. So the dot product is actually a matrix multiplication. So the transpose has an effect; I was just transposing it to convert the lone vector into a column vector rather than a row vector. As for "complete projection", I just meant that we are computing all the components of $x_k$ in the new space defined by the basis $u$ (whereas $x^T_k u_\alpha$ is the projection onto only one component of the basis). Jul 14, 2018 at 18:20
• Hello I got confused again. Can you please relate this formula $\Sigma = \frac{1}{n-1}\sum_i x_i x_i^T$ with the example in this link: math.stackexchange.com/questions/710214/…? Jul 17, 2018 at 15:48
• And how you derived $[X^TX]_{ij} = \Sigma [X^T]_{ik}[X]_{kj}$? Specifically how you came up with that $\Sigma$ here? Thanks. Jul 17, 2018 at 15:53
• @Kaushal28 Edited to answer the covariance question. As for your second question, it follows from the definition of matrix multiplication, i.e. if $C=AB$, then $C_{ij} = \sum_k \; A_{ik} B_{kj}$. Jul 17, 2018 at 17:07