PCA Algorithm

Let’s say this is our data matrix (e.g. our houses), where each data point is a $d$-dimensional row vector.

$$X=\left(\begin{array}{ccc}-& x_1^T& -\\ -& x_2^T& -\\ & ⋮& \\ -& x_n^T& -\end{array}\right)$$

1. Compute the mean row vector $\bar{x}=\frac{1}{n}{\sum }_{i=1}^n{x}_i$
2. Compute the mean row matrix:

\bar X = \begin{pmatrix} 1 \ 1 \ \vdots \ 1 \end{pmatrix} \cdot \bar x^T = \begin{pmatrix} - & \bar x^T & - \ - & \bar x^T & - \ & \vdots \ - & \bar x^T & - \ \end{pmatrix} $$

The dimensions are $n\times d$. 3. Subtract mean (obtain mean centred data)

$$B=X-\bar{X}$$

The dimensions are $n\times d$. 4. Compute the covariance matrix of rows of $B$

$$C=\frac{1}{n}{B}^{T}B$$

The dimensions are $(n\times d{)}^T\times (n\times d)=(d\times n)\times (n\times d)=d\times d$. (more notes on why we do this below) 5. Compute the $k$ largest eigenvectors $v_1,v_2,\dots ,v_k$ of C (not covered in module, use Python or WolframAlpha). Each eigenvector has dimensions $1\times d$.

Note

Depending on implementation, may not be sorted (e.g. certain Python libraries). Hence, sort eigenvectors by decreasing order of eigenvalues.

6. Compute matrix $W$ of $k$-largest eigenvectors. $$W=\left(\begin{array}{cccc}|& |& & |\\ v_1& v_2& \dots & v_k\\ |& |& & |\end{array}\right)$$ Dimensions of $W$ are $(d\times k)$.
7. Multiply each datapoint $x_i$ for $i\in \{1,2,\dots ,n\}$ with $W^T$. Dimensions of $y_i$ are $(k\times d)\times (d\times 1)=k\times 1$

We’ve now reduced the number of dimensions from $d$ to $k$.