Exercise 9.10

If all the singular values of $X$ are distinct, then the eigenvalues of $\mathrm{\Sigma }$ are all distinct and positive or zero.

(a)

Let $X$ has a dimension of $N\times d$, and with SVD, let $X=\mathit{U\Gamma }{V}^T$ where $U$ has a dimension of $N\times d$ and $V$ has a dimension of $d\times d$, so we have $U^{T}U=I_d$ and $V^{T}V=V{V}^T=I_d$. Also let $V=\left[\begin{array}{ccc}\hfill v_1\hfill & \hfill \dots \hfill & \hfill v_d\hfill \end{array}\right]$, where $v_i$ are the $d\times 1$ column vector and they are orthonormal (basis). $\Gamma$ is the diagonal matrix of the singular values of $X$, and by construction it’s ordered, i.e. ${\lambda }_1\ge {\lambda }_2\ge \cdots \ge {\lambda }_d\ge 0$.

Consider any direction $v={\sum <!--\; FUNCTION\; APPLICATION\; -->}_{i=1}^d{q}_i{v}_i$, it should have $\parallel v{\text{∥}}^2={\sum <!--\; FUNCTION\; APPLICATION\; -->}_{i=1}^d{q}_i^2=1$.

$$\begin{array}{llll}\hfill \text{var}(z_1,\dots ,z_N)& =v^T\mathrm{\Sigma }v& \hfill & \\ \hfill & =v^T\frac{1}{N}{X}^T\mathit{Xv}& \hfill & \\ \hfill & =\frac{1}{N}{v}^T{(\mathit{U\Gamma }{V}^T)}^T(\mathit{U\Gamma }{V}^T)v& \hfill & \\ \hfill & =\frac{1}{N}{v}^{T}V\Gamma U^T\mathit{U\Gamma }{V}^{T}v& \hfill & \\ \hfill & =\frac{1}{N}{v}^{T}V{\Gamma }^2{V}^{T}v& \hfill & \\ \hfill & =\frac{1}{N}{v}^{T}V{\Gamma }^2\left[\begin{array}{c}\hfill v_1^T\hfill \\ \hfill \dots \hfill \\ \hfill v_d^T\hfill \end{array}\right]v& \hfill & \\ \hfill & =\frac{1}{N}{v}^{T}V\left[\begin{array}{ccc}\hfill {\lambda }_1^2\hfill & \hfill \dots \hfill & \hfill 0\hfill \\ \hfill 0\hfill & \hfill {\lambda }_2^2\hfill & \hfill \dots \hfill \\ \hfill \dots \hfill & \hfill \dots \hfill & \hfill \dots \hfill \\ \hfill \dots \hfill & \hfill 0\hfill & \hfill {\lambda }_d^2\hfill \end{array}\right]\left[\begin{array}{c}\hfill v_1^{T}v\hfill \\ \hfill \dots \hfill \\ \hfill v_d^{T}v\hfill \end{array}\right]& \hfill & \\ \hfill & =\frac{1}{N}{v}^T\left[\begin{array}{ccc}\hfill v_1\hfill & \hfill \dots \hfill & \hfill v_d\hfill \end{array}\right]\left[\begin{array}{c}\hfill {\lambda }_1^2{v}_1^{T}v\hfill \\ \hfill {\lambda }_2^2{v}_2^{T}v\hfill \\ \hfill \dots \hfill \\ \hfill {\lambda }_d^2{v}_d^{T}v\hfill \end{array}\right]& \hfill & \\ \hfill & =\frac{1}{N}\left[\begin{array}{ccc}\hfill v^T{v}_1\hfill & \hfill \dots \hfill & \hfill v^T{v}_d\hfill \end{array}\right]\left[\begin{array}{c}\hfill {\lambda }_1^2{v}_1^{T}v\hfill \\ \hfill {\lambda }_2^2{v}_2^{T}v\hfill \\ \hfill \dots \hfill \\ \hfill {\lambda }_d^2{v}_d^{T}v\hfill \end{array}\right]& \hfill & \\ \hfill & =\frac{1}{N}\sum _{i=1}^d{v}^T{v}_i{\lambda }_i^2{v}_i^{T}v& \hfill & \\ \hfill & =\frac{1}{N}\sum _{i=1}^d{\lambda }_i^2{v}^T{v}_i{v}_i^{T}v& \hfill & \\ \hfill & =\frac{1}{N}\sum _{i=1}^d{\lambda }_i^2\parallel v^T{v}_i{\text{∥}}^2& \hfill & \\ \hfill & \le \frac{1}{N}\sum _{i=1}^d{\lambda }_1^2\parallel v^T{v}_i{\text{∥}}^2& \hfill & \\ \hfill & =\frac{{\lambda }_1^2}{N}\sum _{i=1}^d\parallel v^T{v}_i{\text{∥}}^2& \hfill & \\ \hfill & =\frac{{\lambda }_1^2}{N}\sum _{i=1}^d{q}_i^2& \hfill & \\ \hfill & =\frac{{\lambda }_1^2}{N}& \hfill & \\ \hfill & =\frac{1}{N}{v}_1^T{v}_1{\lambda }_1^2{v}_1^T{v}_1& \hfill & \\ \hfill & =\frac{1}{N}\sum _{i=1}^d{v}_1^T{v}_i{\lambda }_1^2{v}_1^T{v}_i& \hfill & \\ \hfill & =v_1^T\mathrm{\Sigma }{v}_1& \hfill & \\ \hfill & & \hfill \end{array}$$

So the variance is highest when the principal direction is $v_1$ , the top right singular vector of $X$.

(b)

Follow the proof in problem (a), we see that the top-1 principal direction is $v_1$, next, if we select the next direction $v$ that is orthogonal to $v_1$, it’s clear that $\text{var}(z_1,\dots ,z_N)=v^T\mathrm{\Sigma }v=\frac{1}{N}{\sum <!--\; FUNCTION\; APPLICATION\; -->}_{i=2}^d{\lambda }_i^2\parallel v^T{v}_i{\text{∥}}^2$. It’s easy to see that the principal direction with the highest variance is $v_2$. Continue this, we see that the top-k principal directions are $v_1,\dots ,v_k$.

(c)

If we don’t have the data matrix $X$, but knows $\mathrm{\Sigma }$, since $$\mathrm{\Sigma }=\frac{1}{N}{X}^{T}X=\frac{1}{N}V{\Gamma }^2{V}^T$$

$\mathrm{\Sigma }$ is symmetric, we can do eigen-decomposition, the principal directions are the top-k eigenvectors of $\mathrm{\Sigma }$.