10-DimensionReductionWithPrincipalComponentAnalysis.Rmd

# Dimensionality Reduction with Principal Component Analysis (PCA)

High-dimensional data, such as images, often pose challenges for analysis, visualization, and storage. For instance, a 640×480 color image represents a point in a million-dimensional space (three dimensions per pixel). Despite this complexity, high-dimensional data usually contains redundancy and correlation, allowing it to be represented in a lower-dimensional space with minimal loss of information.

**Dimensionality reduction** leverages these redundancies to produce a more compact representation of the data—similar to compression techniques like JPEG (for images) or MP3 (for audio).



## Principal Component Analysis (PCA)

**Principal Component Analysis (PCA)** is a method for **linear dimensionality reduction**.  
The idea was originally proposed by Pearson (1901) and Hotelling (1933).  In signal processing, PCA is also known as the **Karhunen–Loève Transform**.  
PCA is used for **data compression**, **visualization**, and **identifying patterns or latent factors** in high-dimensional data.

To begin, PCA assumes that high-dimensional data lies approximately on a **low-dimensional subspace**.  
By projecting data onto this subspace, PCA reduces dimensionality while preserving as much variance (information) as possible.

Let:

- \( \mathcal{X} = \{\mathbf{x}_1, \dots, \mathbf{x}_N\} \), with \( \mathbf{x}_n \in \mathbb{R}^D \) (mean-centered data)  
- The covariance matrix be defined as:  
  \[
  \mathbf{S} = \frac{1}{N} \sum_{n=1}^{N} \mathbf{x}_n \mathbf{x}_n^\top
  \]
- A **low-dimensional representation (code)**:  
  \[
  \mathbf{z}_n = \mathbf{B}^\top \mathbf{x}_n \in \mathbb{R}^M, \quad M < D
  \]
- The **projection matrix**:  
  \[
  \mathbf{B} = [\mathbf{b}_1, \dots, \mathbf{b}_M] \in \mathbb{R}^{D \times M}
  \]
  where the columns \( \mathbf{b}_i \) are **orthonormal**:  \( \mathbf{b}_i^\top \mathbf{b}_j = 0 \) if \( i \neq j \), and \( \mathbf{b}_i^\top \mathbf{b}_i = 1 \).

The **projected data** is given by:
\[
\tilde{\mathbf{x}}_n = \mathbf{B}\mathbf{B}^\top \mathbf{x}_n \in \mathbb{R}^D
\]

The goal of PCA is to find \( \mathbf{B} \) and \( \mathbf{z}_n \) that minimize information loss between \( \mathbf{x}_n \) and \( \tilde{\mathbf{x}}_n \).



<div class="example">

In \( \mathbb{R}^2 \), the canonical basis is:
\[
\mathbf{e}_1 = [1, 0]^\top, \quad \mathbf{e}_2 = [0, 1]^\top
\]

A point \( \mathbf{x} = [5, 3]^\top = 5\mathbf{e}_1 + 3\mathbf{e}_2 \) can be represented in this basis.  
If we project onto the subspace spanned by \( \mathbf{e}_2 \):
\[
\tilde{\mathbf{x}} = [0, z]^\top = z\mathbf{e}_2
\]
then only the coordinate \( z \) needs to be stored—representing a 1D subspace of \( \mathbb{R}^2 \).

</div>

This illustrates dimensionality reduction: the original 2D vector is represented by a single coordinate in a 1D subspace.

---

### Compression Interpretation

PCA can be viewed as a data compression system:

- **Encoder:** \( \mathbf{z} = \mathbf{B}^\top \mathbf{x} \)  
  (projects data to lower-dimensional space)  
- **Decoder:** \( \tilde{\mathbf{x}} = \mathbf{B}\mathbf{z} \)  
  (reconstructs data from its low-dimensional code)

The matrix \( \mathbf{B} \) defines both the encoding and decoding transformations.

---

<div class="example">

**MNIST Digits**

PCA is often demonstrated using the **MNIST dataset**, which contains 60,000 grayscale images of handwritten digits (0–9).  

- Each image has **28×28 pixels = 784 dimensions**.  
- Thus, each image can be represented as a vector \( \mathbf{x} \in \mathbb{R}^{784} \).

By applying PCA, we can compress and visualize the intrinsic lower-dimensional structure of this dataset.

</div>
---



### Exercises {.unnumbered .unlisted}


Put some exercises here.






## Maximum Variance Perspective

Principal Component Analysis (PCA) can be derived from the idea that the most informative directions in data are those with the highest variance. When reducing dimensionality, we aim to retain as much of this variance (and hence information) as possible. In essence, PCA finds a low-dimensional subspace that **maximizes the variance** of the projected data.

For simplicity, we assume that the dataset is centered (mean = 0). This assumption can be made *without loss of generality* because shifting the data by its mean does not affect its variance:

\[
V_z[\mathbf{z}] = V_x[\mathbf{B}^\top(\mathbf{x} - \boldsymbol{\mu})] = V_x[\mathbf{B}^\top \mathbf{x}].
\]

Therefore, we can safely assume that both the data \( \mathbf{x} \) and the low-dimensional code \( \mathbf{z} = \mathbf{B}^\top \mathbf{x} \) have zero mean.

---

### Direction with Maximal Variance

We start by finding a single direction \( \mathbf{b}_1 \in \mathbb{R}^D \) along which the variance of the projected data is maximized.

For centered data:
\[
z_{1n} = \mathbf{b}_1^\top \mathbf{x}_n
\]
and the variance of the projection is:
\[
V_1 = \frac{1}{N} \sum_{n=1}^{N} (\mathbf{b}_1^\top \mathbf{x}_n)^2 = \mathbf{b}_1^\top \mathbf{S} \mathbf{b}_1,
\]
where \( \mathbf{S} \) is the data covariance matrix.

To prevent arbitrary scaling of \( \mathbf{b}_1 \), we impose the constraint:
\[
\|\mathbf{b}_1\|^2 = 1.
\]

This leads to the constrained optimization problem:
\[
\max_{\mathbf{b}_1} \; \mathbf{b}_1^\top \mathbf{S} \mathbf{b}_1 \quad \text{subject to } \|\mathbf{b}_1\|^2 = 1.
\]

Using a **Lagrangian formulation**:
\[
L(\mathbf{b}_1, \lambda_1) = \mathbf{b}_1^\top \mathbf{S} \mathbf{b}_1 + \lambda_1(1 - \mathbf{b}_1^\top \mathbf{b}_1).
\]

Setting derivatives to zero gives:
\[
\mathbf{S} \mathbf{b}_1 = \lambda_1 \mathbf{b}_1.
\]

Thus, \( \mathbf{b}_1 \) is an eigenvector of \( \mathbf{S} \), and \( \lambda_1 \) is the corresponding eigenvalue.

The variance of the projection onto \( \mathbf{b}_1 \) is:
\[
V_1 = \lambda_1.
\]

Hence, the **first principal component** is the eigenvector corresponding to the largest eigenvalue of \( \mathbf{S}. \)

The projected data point can be reconstructed as:
\[
\tilde{\mathbf{x}}_n = \mathbf{b}_1 \mathbf{b}_1^\top \mathbf{x}_n.
\]






---

### M-Dimensional Subspace with Maximal Variance

To generalize, we seek an M-dimensional subspace spanned by orthonormal vectors:
\[
\mathbf{B} = [\mathbf{b}_1, \mathbf{b}_2, \dots, \mathbf{b}_M],
\]
where each \( \mathbf{b}_m \) is an eigenvector of \( \mathbf{S} \) associated with one of its largest eigenvalues.  After finding the first \( m-1 \) principal components, we can define the remaining (unexplained) data as:
\[
\hat{\mathbf{X}} = \mathbf{X} - \sum_{i=1}^{m-1} \mathbf{b}_i \mathbf{b}_i^\top \mathbf{X} = \mathbf{X} - \mathbf{B}_{m-1} \mathbf{X},
\]
and seek the next direction \( \mathbf{b}_m \) that maximizes the variance of the residual data.  This again leads to:
\[
\mathbf{S} \mathbf{b}_m = \lambda_m \mathbf{b}_m,
\]
where \( \lambda_m \) is the **m-th largest eigenvalue** of \( \mathbf{S} \). Thus, each principal component corresponds to an eigenvector of the covariance matrix. The variance captured by the m-th component is:
\[
V_m = \mathbf{b}_m^\top \mathbf{S} \mathbf{b}_m = \lambda_m.
\]



<div class="theorem">
The total variance captured by the first \( M \) principal components is:
\[
V_M = \sum_{m=1}^{M} \lambda_m.
\]

The variance lost (due to compression) is:
\[
J_M = \sum_{j=M+1}^{D} \lambda_j = V_D - V_M.
\]
</div>

Alternatively, the **relative variance captured** is:
\[
\frac{V_M}{V_D},
\]
and the **relative variance lost** is:
\[
1 - \frac{V_M}{V_D}.
\]



<div class="example">
If we project the point \( \mathbf{x} = [5, 3]^\top = 5\mathbf{e}_1 + 3\mathbf{e}_2 \)  onto the subspace spanned by \( \mathbf{e}_2 \):
\[
\tilde{\mathbf{x}} = [0, z]^\top = z\mathbf{e}_2 = [0, 3]^\top
\]
We can calculate the error as \[ \mathbf{x} - \tilde{\mathbf{x}} = [5, 3]^\top [0, 3]^\top = [5, 0]^\top.\]

If this projection came from the covariance matrix of a large data set with 2 eigenvalues 6 and 4, then this projection represents 60% ($6/(6+4)$) of the variance in the projection while the lost variance is 40%.  In essence, 60% of the variability of the data associated with a projection of this type would be a result of the second component.

</div>


<div class="example">
When PCA is applied to the MNIST images of the digit “8”:

- The eigenvalues of the data covariance matrix decrease rapidly.  
- Most variance is captured by only a small number of principal components.  
- This demonstrates that the dataset has an intrinsic low-dimensional structure.
</div>


---



### Exercises {.unnumbered .unlisted}




<div class="exercise">
Show that the variance of low dimensional code does not depend on the mean of the data.  This allows us to assume our data has mean 0.

<div style="text-align: right;">
[Solution]( )
</div> 
</div>






<div class="exercise">
Consider the constrained optimization problem \begin{align*} &\max_{\mathbf{b}_1} \mathbf{b}_1^T\mathbf{S}\mathbf{b}_1\\& \text{subject to} ||\mathbf{b}_1||^2 = 1. \end{align*}  Derive the necessary Lagrangian conditions for this optimization problem.

<div style="text-align: right;">
[Solution]( )
</div> 
</div>




<div class="exercise">
Explain why we maximize the variance when we select the basis vector that is associated with the largest eigenvalue. 

<div style="text-align: right;">
[Solution]( )
</div> 
</div>







## Projection Perspective


Principal Component Analysis (PCA) can also be viewed as finding the best low-dimensional linear projection of the data that minimizes the average reconstruction error between the original data and its projection.  This interpretation connects PCA with optimal linear autoencoders.


### Setting and Objective

Any data vector $\mathbf{x} \in \mathbb{R}^D$ can be expressed as a linear combination of orthonormal basis (ONB) vectors $(\mathbf{b}_1, \dots, \mathbf{b}_D)$:
$$
\mathbf{x} = \sum_{d=1}^{D} \zeta_d \mathbf{b}_d.
$$
We seek an approximation $\tilde{\mathbf{x}}$ in a lower-dimensional subspace $U \subseteq \mathbb{R}^D$ of dimension $M < D$:
$$
\tilde{\mathbf{x}} = \sum_{m=1}^{M} z_m \mathbf{b}_m.
$$
The goal is to make $\mathbf{x}$ and $\tilde{\mathbf{x}}$ as close as possible by minimizing the average squared Euclidean distance:
$$
J_M = \frac{1}{N} \sum_{n=1}^{N} \| \mathbf{x}_n - \tilde{\mathbf{x}}_n \|^2.
$$
This quantity is known as the **reconstruction error**.

---

### Finding Optimal Coordinates

For a fixed basis $(\mathbf{b}_1, \dots, \mathbf{b}_M)$, the optimal coordinates of the projection are given by the orthogonal projection:
$$
z_{in} = \mathbf{b}_i^\top \mathbf{x}_n.
$$
Hence, the optimal projection of $\mathbf{x}_n$ is:
$$
\tilde{\mathbf{x}}_n = \mathbf{B} \mathbf{B}^\top \mathbf{x}_n.
$$
where $\mathbf{B} = [\mathbf{b}_1, \dots, \mathbf{b}_M]$.

**Interpretation:**  
PCA’s projection step is an orthogonal projection of the data onto the principal subspace spanned by the top $M$ basis vectors.

---

### Finding the Basis of the Principal Subspace

Rewriting the reconstruction error using projection matrices:
$$
J_M = \frac{1}{N} \sum_{n=1}^{N} \| \mathbf{x}_n - \tilde{\mathbf{x}}_n \|^2 
= \frac{1}{N} \sum_{n=1}^{N} \| ( \mathbf{I} - \mathbf{B}\mathbf{B}^\top ) \mathbf{x}_n \|^2.
$$


- $\mathbf{B}\mathbf{B}^\top$ is a rank-$M$ symmetric matrix — the best rank-$M$ approximation of the identity matrix $\mathbf{I}$.  
- The reconstruction error can also be expressed as:
  $$
  J_M = \sum_{j=M+1}^{D} \mathbf{b}_j^\top \mathbf{S} \mathbf{b}_j = \sum_{j=M+1}^{D} \lambda_j,
  $$
where $\mathbf{S}$ is the data covariance matrix and $\lambda_j$ are its eigenvalues.




<div class="example">
Applying PCA to the MNIST digits “0” and “1”:

- Data embedded in 2D (using top two principal components) shows clear **class separation**.  
- Digits “0” show **greater internal variation** than digits “1”.
</div>




---



### Exercises {.unnumbered .unlisted}


Put some exercises here.















## Eigenvector Computation and Low-Rank Approximations

### Computing Eigenvectors via Covariance and SVD

The **principal subspace basis** of PCA is obtained from the eigenvectors corresponding to the largest eigenvalues of the data covariance matrix:
$$
\mathbf{S} = \frac{1}{N} \sum_{n=1}^N \mathbf{x}_n \mathbf{x}_n^\top 
= \frac{1}{N} \mathbf{X} \mathbf{X}^\top, \quad \mathbf{X} \in \mathbb{R}^{D \times N}.
$$
Two equivalent approaches exist:

1. Eigen-decomposition of $\mathbf{S}$ - Compute eigenvalues and eigenvectors directly from $\mathbf{S}$.

2. Singular Value Decomposition (SVD) of $\mathbf{X}$  
   $$
   \mathbf{X} = \mathbf{U} \boldsymbol{\Sigma} \mathbf{V}^\top.
   $$
   - $\mathbf{U} \in \mathbb{R}^{D \times D}$ and $\mathbf{V} \in \mathbb{R}^{N \times N}$ are orthogonal.  
   - $\boldsymbol{\Sigma} \in \mathbb{R}^{D \times N}$ holds the singular values $\sigma_i \ge 0$.

From this decomposition:
$$
\mathbf{S} = \frac{1}{N} \mathbf{U} \boldsymbol{\Sigma} \boldsymbol{\Sigma}^\top \mathbf{U}^\top.
$$
Hence:

- Columns of $\mathbf{U}$ are eigenvectors of $\mathbf{S}$.  
- Eigenvalues of $\mathbf{S}$ are related to singular values by:
  $$
  \lambda_d = \frac{\sigma_d^2}{N}.
  $$
This connects the maximum variance view of PCA with the SVD perspective.

---

###  PCA via Low-Rank Matrix Approximations

PCA can be viewed as finding the best rank-$M$ approximation to $\mathbf{X}$ that minimizes reconstruction error.  




<div class="theorem">
**Eckart–Young theorem**:
$$
\tilde{\mathbf{X}}_M = \arg\min_{\text{rank}(A) \le M} \| \mathbf{X} - A \|_2.
$$
</div>

The optimal low-rank approximation is obtained by truncating the SVD:
$$
\tilde{\mathbf{X}}_M = \mathbf{U}_M \boldsymbol{\Sigma}_M \mathbf{V}_M^\top,
$$
where:

- $\mathbf{U}_M = [\mathbf{u}_1, \dots, \mathbf{u}_M] \in \mathbb{R}^{D \times M}$   
- $\mathbf{V}_M = [\mathbf{v}_1, \dots, \mathbf{v}_M] \in \mathbb{R}^{N \times M}$  
- $\boldsymbol{\Sigma}_M \in \mathbb{R}^{M \times M}$ contains the top $M$ singular values.  

This provides the optimal projection matrix for PCA and directly yields the principal components.

---

###  Practical Aspects of Eigenvalue Computation

While eigenvalues can theoretically be found by solving the characteristic polynomial, the Abel–Ruffini theorem states that general algebraic solutions for polynomials of degree ≥ 5 do not exist.

In practice:

- Numerical methods (e.g., `np.linalg.eigh`, `np.linalg.svd`) compute eigenvalues iteratively.  
- When only a few leading eigenvectors are needed, **iterative methods** are more efficient than full decompositions.


A simple iterative algorithm to compute the dominant eigenvector:
$$
\mathbf{x}_{k+1} = \frac{\mathbf{S} \mathbf{x}_k}{\| \mathbf{S} \mathbf{x}_k \|}.
$$
This converges to the eigenvector corresponding to the largest eigenvalue.  The original **Google PageRank** algorithm used a similar approach.






---



### Exercises {.unnumbered .unlisted}


Put some exercises here.



## PCA in High Dimensions



For high-dimensional data, computing the $D \times D$ covariance matrix and its eigen-decomposition is computationally expensive, scaling cubically with $D$. When the number of samples is much smaller than the number of features ($N \ll D$), most eigenvalues are zero, and the covariance matrix $\mathbf{S}$ has rank $N$.

---

### Dimensionality Reduction Trick for $N \ll D$

Given centered data $\mathbf{X} = [\mathbf{x}_1, \dots, \mathbf{x}_N] \in \mathbb{R}^{D \times N}$, the covariance matrix is:
$$
\mathbf{S} = \frac{1}{N} \mathbf{X} \mathbf{X}^\top.
$$
The eigenvector equation is:
$$
\mathbf{S} \mathbf{b}_m = \lambda_m \mathbf{b}_m.
$$
Multiplying by $\mathbf{X}^\top$ gives:
$$
\frac{1}{N} \mathbf{X}^\top \mathbf{X} \mathbf{c}_m = \lambda_m \mathbf{c}_m,
\quad \text{where } \mathbf{c}_m = \mathbf{X}^\top \mathbf{b}_m.
$$
Thus:

- $\mathbf{X}^\top \mathbf{X} / N$ (size $N \times N$) shares the **same nonzero eigenvalues** as $\mathbf{S}$.  
- We can compute eigenvectors more efficiently using this smaller matrix.

To recover the original eigenvectors of $\mathbf{S}$:
$$
\mathbf{b}_m = \mathbf{X} \mathbf{c}_m.
$$
Finally, normalize $\mathbf{b}_m$ to have unit norm for use in PCA.








---



### Exercises {.unnumbered .unlisted}


Put some exercises here.




##  Key Steps of PCA in Practice

PCA consists of several main computational steps to identify and project data onto a lower-dimensional subspace.

**1. Mean Subtraction**

Center the data by subtracting the mean vector:
$$
\boldsymbol{\mu} = \frac{1}{N} \sum_{n=1}^N \mathbf{x}_n, \quad 
\mathbf{x}_n \leftarrow \mathbf{x}_n - \boldsymbol{\mu}.
$$
This ensures the dataset has zero mean, which improves numerical stability.

**2. Standardization**

Divide each dimension by its standard deviation $\sigma_d$:
$$
x_{n}^{(d)} \leftarrow \frac{x_{n}^{(d)} - \mu_d}{\sigma_d}, \quad d = 1, \dots, D.
$$
This step removes scale dependence and gives each feature unit variance.


**3. Eigendecomposition of the Covariance Matrix**

Compute the covariance matrix:
$$
\mathbf{S} = \frac{1}{N} \mathbf{X} \mathbf{X}^\top.
$$
Then find its eigenvalues and eigenvectors:
$$
\mathbf{S} \mathbf{u}_i = \lambda_i \mathbf{u}_i.
$$
The eigenvectors form an orthonormal basis (ONB), and the one with the largest eigenvalue defines the principal subspace.

**4. Projection**

To project a new data point $\mathbf{x}_\ast$ onto the principal subspace:

1. Standardize using the training mean and standard deviation:
   $$
   x_\ast^{(d)} \leftarrow \frac{x_\ast^{(d)} - \mu_d}{\sigma_d}.
   $$  
2. Project:
   $$
   \tilde{\mathbf{x}}_\ast = \mathbf{B}\mathbf{B}^\top \mathbf{x}_\ast.
   $$
where $\mathbf{B}$ contains the top eigenvectors as columns.  
3. Obtain low-dimensional coordinates:
   $$
   \mathbf{z}_\ast = \mathbf{B}^\top \mathbf{x}_\ast.
   $$
4. To recover the projection in the original data space:
   $$
   \tilde{x}_\ast^{(d)} \leftarrow \tilde{x}_\ast^{(d)} \sigma_d + \mu_d.
   $$



<div class="example">
PCA applied to MNIST digits (e.g., digit “8”) shows that:

- With few components (e.g., 1–10 PCs), reconstructions are blurry.   
- Increasing PCs (up to ~500) yields near-perfect reconstructions.  
- The reconstruction error:
$$
\frac{1}{N}\sum_{n=1}^N \| \mathbf{x}_n - \tilde{\mathbf{x}}_n \|^2 = \sum_{i=M+1}^{D} \lambda_i
$$
decreases sharply with $M$ until most variance is captured by a small number of components.
</div>







<div class="example">
A Simple Centered Dataset

Consider five observations in \( \mathbb{R}^2 \):
\[
\mathbf{x}_1 =
\begin{pmatrix}
2 \\ 0
\end{pmatrix}, \quad
\mathbf{x}_2 =
\begin{pmatrix}
0 \\ 1
\end{pmatrix}, \quad
\mathbf{x}_3 =
\begin{pmatrix}
-2 \\ 0
\end{pmatrix}, \quad
\mathbf{x}_4 =
\begin{pmatrix}
0 \\ -1
\end{pmatrix}, \quad
\mathbf{x}_5 =
\begin{pmatrix}
0 \\ 0
\end{pmatrix}.
\]

The sample mean is
\[
\frac{1}{5}\sum_{n=1}^5 \mathbf{x}_n = \mathbf{0},
\]

so the data are already mean-centered.  Geometrically, the data exhibit greater spread along the horizontal axis than the vertical axis.

**Compute the Covariance Matrix**

For centered data, the empirical covariance matrix is
\[
\mathbf{S} = \frac{1}{N} \sum_{n=1}^N \mathbf{x}_n \mathbf{x}_n^\top.
\]
Summing the outer products gives
\[
\sum_{n=1}^5 \mathbf{x}_n \mathbf{x}_n^\top
=
\begin{pmatrix}
8 & 0 \\
0 & 2
\end{pmatrix}.
\]
Therefore,
\[
\mathbf{S}
= \frac{1}{5}
\begin{pmatrix}
8 & 0 \\
0 & 2
\end{pmatrix}
=
\begin{pmatrix}
1.6 & 0 \\
0 & 0.4
\end{pmatrix}.
\]


**Variance Along a Direction**

Let
\[
\mathbf{b} =
\begin{pmatrix}
b_1 \\ b_2
\end{pmatrix},
\quad \text{with } \|\mathbf{b}\|^2 = b_1^2 + b_2^2 = 1.
\]
The variance of the projection of the data onto \( \mathbf{b} \) is
\[
V(\mathbf{b}) = \mathbf{b}^\top \mathbf{S} \mathbf{b}
= 1.6 b_1^2 + 0.4 b_2^2.
\]
The PCA optimization problem is
\[
\max_{\mathbf{b}} \; \mathbf{b}^\top \mathbf{S} \mathbf{b}
\quad \text{subject to } \|\mathbf{b}\|^2 = 1.
\]


**Lagrangian Formulation**

Introduce a Lagrange multiplier \( \lambda \):
\[
L(\mathbf{b}, \lambda)
= \mathbf{b}^\top \mathbf{S} \mathbf{b}
+ \lambda (1 - \mathbf{b}^\top \mathbf{b}).
\]
Taking derivatives with respect to \( \mathbf{b} \) and setting them to zero yields
\[
\mathbf{S} \mathbf{b} = \lambda \mathbf{b}.
\]
Thus, the optimal direction \( \mathbf{b} \) must be an eigenvector of the covariance matrix \( \mathbf{S} \).


**Eigenvalues and Eigenvectors**

Since \( \mathbf{S} \) is diagonal,
\[
\mathbf{S}
=
\begin{pmatrix}
1.6 & 0 \\
0 & 0.4
\end{pmatrix},
\]
its eigenvalues and eigenvectors are:

| Eigenvalue | Eigenvector |
|-----------|-------------|
| \( \lambda_1 = 1.6 \) | \( \begin{pmatrix} 1 \\ 0 \end{pmatrix} \) |
| \( \lambda_2 = 0.4 \) | \( \begin{pmatrix} 0 \\ 1 \end{pmatrix} \) |


**First Principal Component**

The largest eigenvalue is \( \lambda_1 = 1.6 \), with eigenvector
\[
\mathbf{b}_1 =
\begin{pmatrix}
1 \\ 0
\end{pmatrix}.
\]
This vector defines the first principal component.  The variance of the data projected onto this direction is
\[
V_1 = \lambda_1 = 1.6.
\]

**Projection and Reconstruction**

For any data point \( \mathbf{x}_n \), the one-dimensional projection is
\[
z_{1n} = \mathbf{b}_1^\top \mathbf{x}_n.
\]
The rank-1 reconstruction using the first principal component is
\[
\tilde{\mathbf{x}}_n
= \mathbf{b}_1 \mathbf{b}_1^\top \mathbf{x}_n
=
\begin{pmatrix}
x_{n1} \\ 0
\end{pmatrix}.
\]
Thus, PCA retains the horizontal coordinate and discards the vertical one.

</div>





---



### Exercises {.unnumbered .unlisted}






<div class="exercise">
What are the steps of PCA?

<div style="text-align: right;">
[Solution]( )
</div> 
</div>



<div class="exercise">
Consider the following data. What is the first principal component?

| x | y |
|---|---|
| 1 | -1 |
| 0 |  1 |
| -1 | 0 |

<div style="text-align: right;">
[Solution]( )
</div> 
</div>



<div class="exercise">

<div style="text-align: right;">
[Solution]( )
</div> 
</div>



<div class="exercise">
Consider the following data. What is the first principal component?

| x   | y   |
|-----|-----|
| 126 | 78  |
| 130 | 82  |
| 128 | 82  |
| 128 | 78  |

<div style="text-align: right;">
[Solution]( )
</div> 
</div>



<div class="exercise">
Consider the following data. What is the first principal component?

| x  | y  |
|----|----|
| 4  | 11 |
| 8  | 4  |
| 13 | 5  |
| 7  | 14 |

<div style="text-align: right;">
[Solution]( )
</div> 
</div>



<div class="exercise">
Consider the following data. What are the first two principal components?

| Math | Science | Arts |
|------|---------|------|
| 90   | 90      | 80   |
| 90   | 80      | 90   |
| 70   | 70      | 60   |
| 70   | 60      | 70   |
| 50   | 50      | 50   |
| 50   | 40      | 50   |

<div style="text-align: right;">
[Solution]( )
</div> 
</div>





<div class="exercise">
Consider the following data. What is the first principal component?

| Large Apples | Rotten Apples | Damaged Apples | Small Apples |
|--------------|---------------|----------------|--------------|
| 1            | 5             | 3              | 1            |
| 4            | 2             | 6              | 3            |
| 1            | 4             | 3              | 2            |
| 4            | 4             | 1              | 1            |
| 5            | 5             | 2              | 3            |



<div style="text-align: right;">
[Solution]( )
</div> 
</div>



<div class="exercise">
Consider the following data. What is the first principal component?

| f1 | f2 | f3 | f4 |
|----|----|----|----|
| 1  | 2  | 3  | 4  |
| 5  | 5  | 6  | 7  |
| 1  | 4  | 2  | 3  |
| 5  | 3  | 2  | 1  |
| 8  | 1  | 2  | 2  |


<div style="text-align: right;">
[Solution]( )
</div> 
</div>





## Latent Variable Perspective

While PCA can be derived geometrically or algebraically, it can also be viewed probabilistically using a latent variable model.

---

### Probabilistic PCA (PPCA)

PPCA (Tipping & Bishop, 1999) introduces a latent variable $\mathbf{z} \in \mathbb{R}^M$ with:
$$
p(\mathbf{z}) = \mathcal{N}(\mathbf{z} | 0, \mathbf{I}),
$$
and a linear mapping to the observed data:
$$
\mathbf{x} = \mathbf{Bz} + \boldsymbol{\mu} + \boldsymbol{\epsilon}, \quad 
\boldsymbol{\epsilon} \sim \mathcal{N}(0, \sigma^2 \mathbf{I}).
$$
Thus:
$$
p(\mathbf{x} | \mathbf{z}, \mathbf{B}, \boldsymbol{\mu}, \sigma^2) 
= \mathcal{N}(\mathbf{x} | \mathbf{Bz} + \boldsymbol{\mu}, \sigma^2 \mathbf{I}).
$$
The **joint distribution** is:
$$
p(\mathbf{x}, \mathbf{z} | \mathbf{B}, \boldsymbol{\mu}, \sigma^2)
= p(\mathbf{x} | \mathbf{z}, \mathbf{B}, \boldsymbol{\mu}, \sigma^2)p(\mathbf{z}).
$$
This defines the **generative process**:

1. Sample $\mathbf{z} \sim \mathcal{N}(0, \mathbf{I})$  
2. Sample $\mathbf{x} \sim \mathcal{N}(\mathbf{Bz} + \boldsymbol{\mu}, \sigma^2 \mathbf{I})$  

---

###  Likelihood and Covariance Structure

By integrating out $\mathbf{z}$:
$$
p(\mathbf{x} | \mathbf{B}, \boldsymbol{\mu}, \sigma^2)
= \int p(\mathbf{x} | \mathbf{z}, \mathbf{B}, \boldsymbol{\mu}, \sigma^2)p(\mathbf{z})\, d\mathbf{z}
= \mathcal{N}(\mathbf{x} | \boldsymbol{\mu}, \mathbf{B}\mathbf{B}^\top + \sigma^2 \mathbf{I}).
$$

- Mean: $\mathbb{E}[\mathbf{x}] = \boldsymbol{\mu}$  
- Covariance: $\text{Var}[\mathbf{x}] = \mathbf{B}\mathbf{B}^\top + \sigma^2 \mathbf{I}$

Hence, the observed data has covariance derived from both the latent structure and the noise.

---

### Posterior Distribution

Given an observation $\mathbf{x}$, the posterior over latent variables is:
$$
p(\mathbf{z} | \mathbf{x}) = \mathcal{N}(\mathbf{z} | \mathbf{m}, \mathbf{C}),
$$
with:
$$
\mathbf{m} = \mathbf{B}^\top (\mathbf{B}\mathbf{B}^\top + \sigma^2 \mathbf{I})^{-1}(\mathbf{x} - \boldsymbol{\mu}),
$$
$$
\mathbf{C} = \mathbf{I} - \mathbf{B}^\top (\mathbf{B}\mathbf{B}^\top + \sigma^2 \mathbf{I})^{-1} \mathbf{B}.
$$

The covariance $\mathbf{C}$ represents the uncertainty of the latent embedding:

- Small determinant → confident embedding  
- Large determinant → uncertain or outlier point  

To visualize or reconstruct data:

1. Sample $\mathbf{z}_\ast \sim p(\mathbf{z} | \mathbf{x}_\ast)$  
2. Generate $\tilde{\mathbf{x}}_\ast \sim p(\mathbf{x} | \mathbf{z}_\ast, \mathbf{B}, \boldsymbol{\mu}, \sigma^2)$.  

This process allows **data generation** and exploration of latent structure, forming a bridge between classical PCA and modern **generative models**.


---






### Exercises {.unnumbered .unlisted}


Put some exercises here.