Principal Component Analysis

Definition:

• Find principle components, i.e. orthogonal directions that are computed via the SVD of a centered data matrix
• Think of a cloud of data and if we can project all of the points on only 2 lines, then we would want the line to be in the direction of the largest variances in order to capture the most information

Rank-one affine approximation:

Basic idea:

• We can use SVD to to find the line passing through 0 that best approximates data points (i.e., the projection of the points on the line gives the lowest approximation error)
• Rank-one approximation but we want it to be affine

Main result:

• Just center the data
• Let $X:=[x_1,...,x_m]$ be a $n\times m$ data matrix, with each column $x_i\in {\mathbb{R}}^n$ a data point
• We seek to find a line $L:=\{x_0+\alpha p:\alpha \in \mathbb{R}\}$ with $x_0,p\in {\mathbb{R}}^n$ to be determined, so that the projected points on the line are closest to the original ones.
• If all the points are approximately on such a line then $x_i\approx x_0+q_{i}p$ for some $q_i\in \mathbb{R},i=1,...,m$ so that $X\approx x_0{1}^{⊺}+p{q}^{⊺}$
  • where 1 is the m-vector of ones
• This leads to the problem ${\min }_{x_0,p,q}||X-x_0{1}^{⊺}-p{q}^{⊺}|{|}_F^2$ where $x_0$ and $p,q\in {\mathbb{R}}^m$ are both variables
  • and the optimal $x_0$ is $\hat{x}=\frac{1}{m}{\sum }_{i=1}^m{x}_i$
• So the problem can be reduce to a standard rank-one problem ${\min }_{p,q_c}||X_c-p{q}_c^{⊺}|{|}_F^2$
  • where $q_c=q-\hat{q}1$ and $\hat{q}=\frac{1}{m}{\sum }_{i=1}^m{q}_i$ and $X_c$ is the centered data matrix $X_c=[x_1-\bar{x},...,x_m-\bar{x}]$

PCA

Deflation:

• Once we’ve found a line close to the cloud of points, can we repeat the process and find another one that is closest again
• Deflation method:
  • Project data points on the hyperplane orthogonal to the direction we found
  • Find a new direction of for the projected data.
  • Iterate
  • Stop until when got $k$ dimensions
• Geomtric of deflation: project the data on a hyperplane orthogonal to the line with direction 1, then a line that is on the plane, orthogonal to the first direction, is found
  • 
• Setup:
  • After SVD, we have centered data matrix $n\times m$, $X_c=X-\hat{x}{1}^{⊺}=U\tilde{S}{V}^{⊺}={\sum }_{i=1}^r{\sigma }_i{u}_i{v}_i^{⊺}$ where:
    • $\tilde{S}$ is a $n\times m$ diagonal matrix $\tilde{S}=\text{diag}({\sigma }_1,...,{\sigma }_r,0,...,0)$
    • $U:=[u_1,...,u_n]$ and $V:=[v_1,..,v_m]$ are orthogonal
• Euclidean Projection on a line, projection of $z$ on a point $x$ on the line $\mathcal{L}:=\{x_0+\alpha u:\alpha \in \mathbb{R}\}$ is given by $z=x_0+(u{u}^{⊺})(x-x_0)$
  • we have $x=z+z_{\perp }$ where $z\perp z_{\perp }$; therefore, $z_{\perp }-x_0=(I-u{u}^{⊺})(x-x_0)$
• After projecting the points on the closest line, the (centered) matrix of projected points is $Z^{(1)}=u_1{u}_1^{⊺}{X}_c$ while the points projected on the orthogonal to the line are $X_c^{(1)}=P_1{X}_c$ where $P_1:=I-u_1{u}_1^{⊺}$
• Since $U$ is orthonormal, the projected points $X_c^{(1)}$ can be written as $X_c^{(1)}=P_1{\sum }_{i=1}^r{\sigma }_i{u}_i{v}_i^{⊺}={\sum }_{i=2}^r{\sigma }_i{u}_i{v}_i^{⊺}=U{\tilde{S}}^{(2)}{V}^{⊺}$
  • where ${\tilde{S}}^{(2)}:=diag(0,{\sigma }_2,....,{\sigma }_r,0,...,0)$
• In effect we have removed the component (dyad) associated with ${\sigma }_1$
• Note that the new data matrix is centered, and has largest singular value ${\sigma }_2$, with the corresponding direction $u_2$.
  • Together, $u_1,u_2$ span the closest plane approximating data
• After $k$ steps of the deflation process, the directions returned are $u_1,...,u_k$; spanning the closest k-dimensional subspace.
  • Thus we can compute all the principal components with one SVD of the original centered data matrix

Approximation error:

• The sum of the squared lengths of the distances of points project to the line measures the error between points and their projections.
• Explained variance:
  • At the first step, the average squared error between the (centered) original points and the points projected on the closest line is $||X_c-Z^{(1)}|{|}_F^2=||P_1{X}_c|{|}_F^2={\sigma }_2^2+...+{\sigma }_n^2$
• After the k-th step, the error is thus $||X_c-Z^{(k)}|{|}_F^2=||(P_k...P_1)X_c|{|}_F^2={\sigma }_{k+1}^2+...+{\sigma }_n^2$
• The explained variance is the ratio $0\le {\rho }^2:=\frac{{\sigma }_{k+1}^2+...+{\sigma }_n^2}{{\sigma }_1^2+...+{\sigma }_n^2}\le 1$

Data projection:

• Once we computed the SVD of the centered data matrix, we can project the data on the plane spanned by the two vectors u1, u2.
• This plane is the plane closest to data. The (centered) projected points are the 2D vectors in $Z:Z=[z_1,...,z_m]=\left(\begin{array}{c}{u}_1^{⊺}\\ u_2^{⊺}\end{array}\right)X_c$
• More generally, the span of $\{u_1,...,u_k\}$ is the subspace of dimension $k$ closest to the data set (this comes directly from the low-rank approximation theorem). The projected points are given by $Z=[z_1,...,z_m]=\left(\begin{array}{c}{u}_1^{⊺}\\ ...\\ u_k^{⊺}\end{array}\right)X_c$

Link between SVD and eigenvalue decomposition of covariance:

• Consider a centered matrix of data points $X_c$
• The covariance matrix can be written as $C=\frac{1}{m}\sum _{i=1}^m\left(x_i-\hat{x}\right){\left(x_i-\hat{x}\right)}^T=\frac{1}{m}{X}_c{X}_c^T,\hat{x}:=\frac{1}{m}\sum _{i=1}^m{x}_i$
• If $X_c$ has SVD $X_c=U\tilde{S}{V}^T$, then $C=U\wedge U^T$, where $\Lambda :=\frac{1}{m}\mathrm{diag}\left({\sigma }_1^2,\dots ,{\sigma }_r^2,0,\dots ,0\right)$
• Thus, the left singular vectors of $X_c$ are the eigenvectors of $C$.

Variance Maximization problem:

• Let $C$ be the sample $n\times n$ Covariance Matrix for a data set of $m$ points $x_1,...,x_m\in {\mathbb{R}}^n$ with mean $\hat{x}=(1/m)(x_1+...+x_m)$
• For a given $n$-vector $u$, the line $\mathcal{L}(\bar{x},u)$ of points of the form $\hat{x}+\alpha u$
  • for $\alpha \in \mathbb{R}$
  • knowing that the projected data points are of the form $z_i=\hat{x}+{\alpha }_i{u}_i$ for ${\alpha }_i=u^{⊺}(x_i-\bar{x})$
• We seek a direction $u$ such that the variance of the projected points on the line $\mathcal{L}(\hat{x},u)$ is maximal. Without loss of generality, we can assume $||u|{|}_2=1$
• The variance of scores (m-vectors $\alpha$) is $\frac{1}{m}{\sum }_{i=1}^m[u^{⊺}(x_i-\hat{x}){]}^2=y^{T}Cu$
• We wish to maximize ${\max }_u{u}^{T}Cu:||u|{|}_2=1$
• Solution: an optimal vector $u^{\ast }=u_1$ with $u_1$ an eigenvector of $C$ that corresponds to its largest eigenvalue ${\lambda }_1$
• Projection on maximum variance line:
  • The line with maximum variance is set of points of the form $\hat{x}+\alpha u_1$
  • The projection of a generic point $x\in {\mathbb{R}}^n$ on the line is $z=\hat{x}+(u_1^{⊺}(x-\hat{x}))u_1=\hat{x}+u_1{u}_1^T(x-\hat{x})$
  • We can project all the data points at once: the (centered) matrix of projected points is the dyad: $Z^{(1)}=[z_1^{(1)}-\hat{x},...,z_m^{(1)}-\hat{x}]=u_1{u}_1^T{X}_c$
  • The line of maximum variance minimizes the sum of squared Euclidean norm distance between the data points and the line.
  • In fact, PCA can be interpreted two ways:
    • as a variance maximization process, relying on the eigenvalue decomposition of the covariance matrix;
    • as a low-rank approximation of the centered data matrix, relying on the SVD of that matrix

Minimum distance line:

• The projection $z$ of $x$ along line $\hat{x}+\alpha u$ is $z=\hat{x}+u{u}^T(x-\hat{x})$
• So the sum of squared distances between $x^{(i)}$ and its projection $z^{(i)}$ is
  • $\begin{array}{rl}& \\ \sum _i& {\Vert x^{(i)}-z^{(i)}\Vert }_2^2=\sum _i{\Vert \left(x^{(i)}-\hat{x}\right)-u{u}^T\left(x^{(i)}-\hat{x}\right)\Vert }_2^2=\sum _i{\Vert x_c^{(i)}\Vert }_2^2-2{\left(u^T{x}_c^{(i)}\right)}^2+{\left(u^T{x}_c^{(i)}\right)}^2\end{array}$
  • $=\sum _i{\Vert x_c^{(i)}\Vert }_2^2-{\left(u^T{x}_c^{(i)}\right)}^2={\Vert X_c\Vert }_F^2-m\left(u^{T}Cu\right)$
• Hence, minimizing the sum of squared distances is the same as maximizing $(1/m){\sum }_i{\left(u^T{x}_c^{(i)}\right)}^2$, that is, the variance of the projected points.

Rank-one approximation:

• Consider the centered data matrix $X_c=\left[x_c^{(1)}\cdots x_c^{(m)}\right]$ and assume we want to find the rank-one matrix matrix $\sigma u{v}^T$ that best approximates $X_c$ in the Frobenius norm sense: ${\min }_{\sigma ,u,v}{\Vert X_c-\sigma u{v}^T\Vert }_F^2,\sigma \ge 0,\Vert u{\Vert }_2=\Vert v{\Vert }_2=1$
• Since $\Vert Y{\Vert }_F^2=\mathrm{trace}\left(Y{Y}^T\right)$, we have:
  • $\begin{array}{rl}\Vert X_c& -\sigma u{v}^T{\Vert }_F^2=\mathrm{trace}\left(X_c^T-\sigma v{u}^T\right)\left(X_c-\sigma u{v}^T\right)\\ & =\mathrm{trace}\left(X_c^T{X}_c\right)-2\sigma \mathrm{trace}\left(X_c^{T}u{v}^T\right)+{\sigma }^2\mathrm{trace}\left(v{u}^{T}u{v}^T\right)\\ & =\mathrm{trace}\left(X_c^T{X}_c\right)-2\sigma u^T{X}_{c}v+{\sigma }^2\Vert u{\Vert }_2^2\Vert v{\Vert }_2^2\\ & =\mathrm{trace}\left(X_c^T{X}_c\right)-2\sigma u^T{X}_{c}v+{\sigma }^2\end{array}$
• Given the SVD of $X_c={\sigma }_1{u}_1{v}_1^T+\cdots$ the best choice is to take $u=u_1$ and $v=v_1$, whence $u^T{X}_{c}v={\sigma }_1$, etc…

The left singular vector $u_1$:

• The three problems:
  • Find the line of maximal projected data variance;
  • Find the line that minimizes the residual distance from the original points to their projections;
  • Find a rank one approximation of the centered data matrix;
• All have solutions that involve the left principal singular vector $u_1$ of the centered data matrix $X_c$.
• N.B.: this is also the principal eigenvector of the covariance matrix $C$. Indeed, if $X_c=U\Sigma V^T$, then
  • $C=\frac{1}{m}{X}_c{X}_c^T=\frac{1}{m}U\Sigma V^{T}V\Sigma U^T=U\left(\frac{1}{m}{\Sigma }^2\right)U^T$ is an eigenvalue factorization for $C$

---