1 6 4 Principal Component Analysis

1. Remark: We assume for the exercise that $\dim V \leq d$.

We first recall that, as a orthogonal projection matrix, ${\rm Proj}_V$ is symmetrical, i.e. ${{\rm Proj}_V}^T = {\rm Proj}_V$.

We then have:

(1)

\begin{align} \sum_{i=1}^n{\Vert X^{(i)} - {\rm Proj}_V X^{(i)} \Vert}^2 = \sum_{i=1}^n{\sum_{j=1}^p{ (X^{(i)}_j - ({\rm Proj}_V X^{(i)})_j)^2 }} \end{align}

where

(2)

\begin{align} ({\rm Proj}_V X^{(i)})_j = \sum_{k=1}^p{({\rm Proj}_V)_{j, k} \, X^{(i)}_k} = \sum_{k=1}^p{X^{(i)}_k \, ({\rm Proj}_V)_{k, j}} = ({\bf X} \, {\rm Proj}_V)_{i,j} \end{align}

Hence,

(3)

\begin{align} \sum_{i=1}^n{\Vert X^{(i)} - {\rm Proj}_V X^{(i)} \Vert}^2 = \sum_{i=1}^n{\sum_{j=1}^p{ (X^{(i)}_j - ({\bf X} \, {\rm Proj}_V)_{i,j})^2 }} = \sum_{i=1}^n{\sum_{j=1}^p{ ({\bf X}_{i,j} - ({\bf X} \, {\rm Proj}_V)_{i,j})^2 }} \end{align}

and

(4)

\begin{align} \sum_{i=1}^n{\Vert X^{(i)} - {\rm Proj}_V X^{(i)} \Vert}^2 = {\Vert {\bf X} - {\bf X} \, {\rm Proj}_V \Vert}^2_F \end{align}

We will now apply theorem C.5 on ${\bf X} = \sum_{k=1}^{r}{\sigma_k \, u_k \, v_k^T}$. For any $d \lt r$, we have:

(5)

\begin{align} \min_{B:{\rm rank}(B) \le d}{\Vert {\bf X} - B \Vert}^2_F = \sum_{k=d+1}^r{\sigma_k^2} \end{align}

As a consequence,

(6)

\begin{align} {\Vert {\bf X} - {\bf X} \, {\rm Proj}_V \Vert}^2_F \ge \sum_{k=d+1}^r{\sigma_k^2} \end{align}

since ${\rm rank}({\bf X} \, {\rm Proj}_V) \le \dim{V} \le d$.

The case $d = r$ is trivial since the sum is empty and equals to 0.

2. Let $V_d$ the linear space spanned by $\{v_1, \dots, v_d\}$ for $d \leq r$. What is ${\rm Proj}_{V_d}$?

We define $Q = \sum_{k=1}^d{v_k \, v_k^T}$. Let $X \in {\bf R}^p$, we have ${\bf R}^p = V_d \oplus V_d^{\perp}$. Hence, $X = Y + Z$ with $Y = a_1 v_1 + \dots + a_d v_d = {\rm Proj}_{V_d} X \in V_d$ and $Z \in V_d^{\perp}$.

(7)

\begin{align} QZ = (\sum_{k=1}^d{v_k \, v_k^T}) Z = \sum_{k=1}^d{v_k \, (v_k^T Z)} = 0 \end{align}

since $Z \in V_d^{\perp}$ and $v_k^T Z = 0$.

So $QX = QY + QZ = QY$.

(8)

\begin{align} QX = (\sum_{k=1}^d{v_k \, v_k^T}) (\sum_{i=1}^d{a_i \, v_i}) = \sum_{k=1}^d{\sum_{i=1}^d{ a_i \, v_k \, (v_k^T \, v_i) }} \end{align}

with $v_k^T \, v_i = \langle v_k^T , v_i \rangle = \delta_{k, i}$.
Hence,

(9)

\begin{align} QX = \sum_{k=1}^d{a_k \, v_k} = Y = {\rm Proj}_{V_d} X \end{align}

and therefore $Q = {\rm Proj}_{V_d} = \sum_{k=1}^d{v_k \, v_k^T}$.

Let $d \lt r$, with ${\bf X} = \sum_{k=1}^r{\sigma_k \, u_k \, v_k^T}$, we have:

(10)

\begin{align} {\bf X} {\rm Proj}_{V_d} = (\sum_{k=1}^r{\sigma_k \, u_k \, v_k^T})(\sum_{i=1}^d{v_i \, v_i^T}) = \sum_{k=1}^r{\sum_{i=1}^d{ \sigma_k \, u_k \, (v_k^T \, v_i) v_i^T }} \end{align}

with $v_k^T \, v_i = \delta_{k, i}$, so

(11)

\begin{align} {\bf X} {\rm Proj}_{V_d} = \sum_{k=1}^d{\sigma_k \, u_k \, v_k^T} \end{align}

Hence, we can apply theorem C.5 (we achieved the minimum) and

(12)

\begin{align} \Vert {\bf X} - {\bf X} {\rm Proj}_{V_d} \Vert^2_F = \sum_{k=d+1}^r{\sigma_k^2} \end{align}

If $d = r$, ${\bf X} {\rm Proj}_{V_d} = \sum_{k=1}^r{\sigma_k \, u_k \, v_k^T} = {\bf X}$ and $\Vert {\bf X} - {\bf X} {\rm Proj}_{V_d} \Vert^2_F = 0 = \sum_{k=r+1}^r{\sigma_k^2}$.

3. This is the conclusion of questions 1 and 2.2 is the case of equality in 1.

4. Let us denote by $(a_1^{(i)}, \dots, a_d^{(i)})$ the coordinates of ${\rm Proj}_{V_d} X^{(i)}$ in the orthonormal basis $(v_1, \dots, v_d)$.

We have $a_j^{(i)} = \langle {\rm Proj}_{V_d} X^{(i)}, v_j \rangle=\langle X^{(i)}, v_j \rangle$ .

since ${\rm Proj}_{V_d} = {{\rm Proj}_{V_d}}^T$ and ${\rm Proj}_{V_d} v_j = v_j$.

Recall that $(X^{(i)})^T$ is the i-th line of ${\bf X}$. This means that

(13)

\begin{align} (X^{(i)})^T = e_i^T \, {\bf X} = e_i^T \, (\sum_{k=1}^r{\sigma_k \, u_k \, v_k^T}) = \sum_{k=1}^r{\sigma_k \, (e_i^T \, u_k) \, v_k^T} \end{align}

with $e_i^T \, u_k = \langle e_i, u_k \rangle$.

Hence,

(14)

\begin{align} X^{(i)} = \sum_{k=1}^r{\sigma_k \, \langle e_i, u_k \rangle \, v_k} \end{align}

and

(15)

\begin{align} a_j^{(i)} = \langle X^{(i)}, v_j \rangle = \langle \sum_{k=1}^r{\sigma_k \, \langle e_i, u_k \rangle \, v_k}, v_j \rangle = \sum_{k=1}^r{\sigma_k \, \langle e_i, u_k \rangle \, \langle v_k, v_j \rangle} \end{align}

Since $\langle v_k, v_j \rangle = \delta_{k,j}$, we have:

(16)

\begin{align} a_j^{(i)} = \sigma_j \, \langle e_i, u_j \rangle \end{align}

Please share your solution! find instructions on the Help page