11 - Principal Component Analysis and Autoencoders

Class: CSCE-421

Notes:

We will use linear algebra only!

Linear Algebra - Matrix multiplication

Matrix times Vector - 2 Ways

At first, you learn (Mv1). But when you get used to viewing it as (Mv2), you can understand $A\mathit{x}$ as a linear combination of the columns of $A$. Those products fill the column space of $A$ denoted as $\mathbf{C}(A)$. The solution space of $A\mathit{x}=\mathbf{0}$ is the nullspace of $A$ denoted as $\mathbf{N}(A)$.

Notes:

• If you need to know anything about linear algebra, this is the most important thing to know, matrix and vector multiplication!

Vector times matrix - 2 Ways

A row vector $\mathit{y}$ is multiplied by the two column vectors of $A$ and become the two dot product elements of $\mathit{y}A$.

The product $\mathit{y}A$ is a linear combination of the row vectors of $A$.

Notes:

• Vector matrix multiplication is the linear combination of the rows
• vM2 is basically a scaled version of the rows in B added together
  • Linear combination coefficients come from each element in A

Matrix times Matrix - 4 ways

Notes:

• MM1 is a natural way, but turns out it is not the most used
  • It is typycal row by column approach
• The most important view is MM4
  • You take a column vector and multiply it by a row vector, what do you get? a matrix
  • You do this for every column and every row and then add the matrices together (they will be of the same size)
  • This is kind of like an outer product.
  • What can you learn from this approach?
    • You take the first column on matrix A, then you take the first row B, you multiply them together to get a matrix
    • The only thing that matters is the cross balance
    • This doesn't tell you that if you permute the columns, the matrix will be the same
    • But if you permute both the columns and row, then your matrices will be the same
  • Note this gives rank 1 columns because they are not linearly independent since they are scaled by the same column vector.
• What about MM2?
  • You take each column and multiply it with a matrix, a linear combination of columns with the matrix (Matrix - vector multiplication).
• MM3 is just the row way of doing MM2?

Practical Patterns

Burn this into your memories and you can see ...

Notes:

• P1: Linear combination of the columns on A.
  • Matrix A * Diagonal Matrix D
  • Individual elements in the diagonal of the diagonal matrix scale each of the columns of A
• P2: Is the same thing but the diagonal matrix is on the left.
  • Only the elements on the diagonal are non-zero so this makes sense
  • Note this one is not a linear combination, you are just multiplying the numbers from the diagonal matrix * the rows in matrix B

Notes:

• How to interpret P4 (it is the most important one)?
  • We can do step by step
    • First we use P1' (columns * diagonal) And then you multiply that column matrix to the row matrix
    • In practice what is the result? How do I interpret this?
      • You still look at the matrix from P1' as a column matrix but with each column multiplied with a number, then we need to multiply each column with each row of the row matrix.
  • The diagonal matrix is represented by a sigma sign
    • Each of the diagonal elements of these matrix basically scales the outer product of the ith column with the ith row
• Why are we talking about this?
  • Later on, what we will do is to have a matrix, but we will decompose this matrix into products of matrices, with the one on the center being a diagonal matrix.
  • The reason why we view linear algebra this way, is that if you docompose in this way, you can view this decomposition as an outer product (P4)
    • The size of this matrix is the same size as the original matrix, but each column are linearly dependent so the rank of this matrix is 1.
      • Is a sequence of rank 1 matrices summed together.
• There is something that is easy but most people do not know.
  • In most of these decomposition, they require the diagonal elements to be in non-increasing order?, why is this a requirement?
  • Because the order of the matrices does not matter, you can always rearrange in sorted order.
    • If the diagonal terms are not in sorted order, you can always rearrange the terms of the sum of matrices at the end
• Other thing is that the result is nonnegative?
  • Because if they are negative, you can just flip the sign of the outside.
  • You can always split the sign by multiplying a column or a row times a -1
  • You either leave the sign in the column or in the row, but not in both
• We always assume that the diagonal terms are always non-negative and in sorted order?

Orthogonal Matrices

(1) An orthogonal matrix is a square matrix whose columns and rows are orthogonal unit vectors, i.e., orthonormal vectors. That is, if a matrix $\mathit{Q}$ is an orthogonal matrix, we have

(2) It leads to ${\mathit{Q}}^{-1}={\mathit{Q}}^T$, which is a very useful property as it provides an easy way to compute the inverse.

(3) For an orthogonal $n\times n$ matrix $\mathit{Q}=[{\mathit{q}}_1,{\mathit{q}}_2,\dots ,{\mathit{q}}_n]$, where ${\mathit{q}}_i\in {\mathbb{R}}^n$, $i=1,2,\dots ,n$, it is easy to see that ${\mathit{q}}_i^T{\mathit{q}}_j=0$ when $i\ne j$ and ${\mathit{q}}_i^T{\mathit{q}}_i=1$.

(4) Furthermore, suppose ${\mathit{Q}}_1=[{\mathit{q}}_1,{\mathit{q}}_2,\dots ,{\mathit{q}}_i]$ and ${\mathit{Q}}_2=[{\mathit{q}}_{i+1},{\mathit{q}}_{i+2},\dots ,{\mathit{q}}_n]$, we have ${\mathit{Q}}_1^T{\mathit{Q}}_1=\mathit{I},{\mathit{Q}}_2^T{\mathit{Q}}_2=\mathit{I}$, but ${\mathit{Q}}_1{\mathit{Q}}_1^T\ne \mathit{I},{\mathit{Q}}_2{\mathit{Q}}_2^T\ne \mathit{I}$.

Notes:

• Certain matrices are called orthogonal matrices, these matrices are square matrices (equal number of rows and columns)
• Note that by convention we require orthogonal matrices to have normalized rows and columns (orthonormal vectors)
• If you have a square matrix, it is orthogonal if all columns are orthogonal to each other
  • If you take any different columns and you compute the inner product, the inner product is 0.
  • Each column needs to be normalized with each row?
    • Each column is normalized to have a unit ... then the rows will automatically satisfy the orthogonal requirement
• The requirement is intuitively translated into ${\mathit{Q}}^T\mathit{Q}=\mathit{Q}{\mathit{Q}}^T=\mathit{I}$
  • Remember Identity matrix (I) is all elements 0 except by the diagonal elements which are 1.
  • $Q^{T}Q$: $Q^T$ are rows, and $Q$ are columns, its product tells you the columns are normalized
  • $Q{Q}^T$: tells you the rows are normalized
• If a matrix is orthogonal the inverse is simply the transpose of that matrix!
• There is something else that is important to talk about:
  • If I have an orthogonal matrix $Q$ (view it as columns) - it has to be a square matrix
  • Somehow we will split this into 2 matrices: $Q=[Q_1,Q_2]$, of course $Q_1$ and $Q_2$ are no longer squared matrices
    • They are not orthogonal matrices anymore, but they are vey important
    • In general when we talk about $Q_1$, it is a matrix with orthonormal columns.
      • All the columns are orthonormal to each other and each column is also normalized
  • In this case we would have:
    • $Q_1^T{Q}_1=I$
    • $Q_1{Q}_1^T=\text{we don’t know}$
      • Rows are no longer orthogonal and normalized!
    • $Q_2^T{Q}_2=I$
    • $Q_2{Q}_2^T=\text{we don’t know}$
      • Rows are no longer orthogonal and normalized!

Notes:

• We know that:
  • $Q=[Q_1,Q_2]$
  • $Q^{T}Q=Q{Q}^T=I$
• How do I write this in terms of $Q_1$ and $Q_2$?
  • $Q^{T}Q=Q{Q}^T=I=Q_1{Q}_1^T+Q_2{Q}_2^T$
  • You multiply the first part together, and then you multiply the second part together and sum them
  • There is an interesting property here (FYIO):
    • These two matrices added together equals the Identity matrix
      1. For these two matrices the sum of the diagonal elements of these matrices is also the Identity matrix
      2. What would be the rank of these two matrices?
         • Is there an upper bound? Yes, the upper-bound is 1.
         • The diagonal elements are nonnegative, each of them have to be smaller or equal to 1.
    • Note this is not required for this class.

Eigen-Decomposition

Eigen-Decomposition (1)

(1) A square $n\times n$ matrix $\mathit{S}$ with $n$ linearly independent eigenvectors can be factorized as

where $\mathit{Q}$ is the square $n\times n$ matrix whose columns are eigenvectors of $\mathit{S}$, and $\mathbf{\Lambda }$ is the diagonal matrix whose diagonal elements are the corresponding eigenvalues.

(2) Note that only diagonalizable matrices can be factorized in this way.

(3) If $\mathit{S}$ is a symmetric matrix, its eigenvectors are orthogonal. Thus $\mathit{Q}$ is an orthogonal matrix and we have

Notes:

• Definition of eigenvalues & eigenvectoes?
  • Matrix has to be a squared matrix
  • If you have squared matrix $S$ (n * n)
  • The eigen values and eigen vectors are:
    • $S{v}_i={\lambda }_i{v}_i,i=1\cdots n$
      • note eigen values and eigen vectors are paired to each other.
      • We just want it to be a matrix = a matrix
• We want to have a matrix $Q$ so that each of its columns can be paired as eigenvectors:$$Q=[q_1,q_2,\cdots q_n]$$
• Then we have another matrix, which is a diagonal matrix:$$\text{Lambda = left[begin{array}{lll}}$$& \lambda_2 & \
  & & \lambda_3
  \end{array}\right]$$
  • If you want to multiply each number times the columns, the diagonal matrix has to be on the right and the column matrix on the left: $Q\mathrm{\Lambda }$
• Note that when doing $SQ$, we are multiplying the first column of the matrix S times $q_i$, and so on.

- we can represent this a $S{q}_i$
- We then can say:

- We are just equaling each column to each other on $S{v}_i={\lambda }_i{v}_i$

• You can assume $Q$ is non-singular. and therefore you are able to do:

- This happens since $Q{Q}^{-1}=I$?
- If all columns are orthogonal to each other, they are not linear independent
- (orthogonal means they have 90 degree angle), this is a stronger condition

• S is a symmetric matrix, and in that case $Q$ will be an orthogonal matrix (non-singular). Where the inverse $Q^{-1}$ becomes the transpose.

• Definition (only works when S is symmetric):

  • $S\ge 0$ iff $x^{T}Sx\ge 0$ (for all $x$)
  • $S>0$ iff $x^{T}Sx>0$ (for all $x\ne 0$)

• Remember this only applies for a squared matrix

Question:

• Look at:$$
  \boldsymbol{S}=\boldsymbol{Q} \boldsymbol{\Lambda} \boldsymbol{Q}^T .$$$$
  • Then we know the matrix i the middle is a diagonal matrix with eigenvalues
  • Since $S$ is symmetric, we can be sure that all the eigenvalues are real numbers (but they still can be + or -)
  • The dilemma is that:
    • somehow in this decomposition, we can somehow manage to make them positive?
      • No, because then we will affect transpose
      • Why can't you make these to be non-negative?
        • Because $Q$ and $Q^T$ will be the same value, so multiplying them will become the square
      • You are kind of flipping two times
      • Therefore you cannot make the eigenvalues (the diagonal elements of the middle matrix) to always be positive.
        • Note this is different in singular value decomposition, where $Q$ and $Q^T$ are different matrices.

Eigen-Decomposition (2)

Notes:

• Why is this useful?
  • Because each outer product can be view as a projection matrix
• Why are we calling these a projection matrix?
  • Because $q_i$ are all unit vectors
  • If we take any vector $x$, the result will equal the projection lens
    • The projection of $x$ in the direction of $q_1$
      • $P_1$ will project any vector to $q_1$
      • $P_2$ will project any vector to $q_2$
      • ...
• As we project to each axis (each $q_i$), they will all be orthogonal to each other
• If we assume that the $\mathrm{\Lambda }$ is an identity matrix, we can rewrite in the second form
  • What this means is that we can recover the original vector
• The last relation means that any of two projections are perpendicular to each other
  • They will be aligned to $q_i$

Checkpoint 1 (eigen-decomposition)

To understand Principal Component Analysis (PCA), we first need to understand the mathematical engine that makes it work: Eigen-Decomposition.

Imagine a matrix as a machine that stretches, squashes, and rotates data vectors. Eigen-decomposition is a way of "taking the machine apart" to reveal its fundamental, underlying structure. It tells us the core directions in which the machine stretches the data, and by exactly how much.

1. The Basic Formula ($S=Q\mathrm{\Lambda }{Q}^{-1}$) If you have a square $n\times n$ matrix $S$, you can mathematically factorize (decompose) it into the product of three simpler matrices:

• $Q$ (The Directions): This is a square matrix where every single column is an eigenvector of $S$. Think of an eigenvector as a special, fundamental axis. When the matrix $S$ acts on its eigenvector, it doesn't knock it off its line or rotate it; it only stretches or shrinks it.
• $\mathrm{\Lambda }$ (The Scales): This is a diagonal matrix (zeros everywhere except down the main diagonal). The numbers on this diagonal are the eigenvalues. Each eigenvalue corresponds to an eigenvector in $Q$ and tells you exactly how much the data is stretched or shrunk along that specific axis.
• $Q^{-1}$: This is simply the inverse of the $Q$ matrix.

Note: This specific decomposition is only possible for "diagonalizable" square matrices with linearly independent eigenvectors.

2. The Symmetric Magic ($S=Q\mathrm{\Lambda }{Q}^T$) In machine learning (and especially PCA), we almost always deal with symmetric matrices (like the covariance matrix, where the top-right mirrors the bottom-left). When your matrix $S$ is symmetric, two beautiful mathematical properties occur:

1. Orthogonal Eigenvectors: The eigenvectors (the fundamental axes) become perfectly perpendicular (orthogonal) to each other.
2. The Inverse Becomes the Transpose: Because the columns of $Q$ are orthogonal unit vectors, $Q$ becomes an "orthogonal matrix". A magical property of orthogonal matrices is that calculating their inverse is as easy as flipping them on their side: $Q^{-1}=Q^T$.

Because of this, the decomposition formula for symmetric matrices simplifies beautifully to: $S=Q\mathrm{\Lambda }{Q}^T$.

3. Positive Semi-Definite (PSD) Matrices Your professor introduces the concept of a Positive Semi-Definite matrix. By definition, a symmetric matrix $S$ is PSD if for any vector $x$, the result of $x^{T}Sx\ge 0$.

• Why does this matter? Because if a symmetric matrix is PSD, it guarantees that all of its eigenvalues are real, non-negative numbers (they cannot be imaginary or negative). As you will see later, covariance matrices are always PSD, meaning their eigenvalues are always positive or zero.
• A warning: In pure eigen-decomposition, if the matrix is not PSD, the eigenvalues (the numbers inside $\mathrm{\Lambda }$) can be negative. You cannot arbitrarily flip their signs to make them positive, because flipping the sign inside $\mathrm{\Lambda }$ would mathematically alter the original matrix $S$.

4. Eigen-Decomposition (2): The Projection View Instead of looking at $S=Q\mathrm{\Lambda }{Q}^T$ as three giant matrices multiplying each other, we can use linear algebra (Specifically "Practical Pattern 4" from your previous slides) to rewrite it as a sum of smaller pieces: $$S = \sum_{i=1}^n \lambda_i q_i q_i^T$$

• What is $q_i{q}_i^T$? This is the "outer product" of a single eigenvector with itself, which creates a matrix.
• The Meaning: This matrix acts as a projection matrix. If you multiply any data point $x$ by this matrix, it acts like a flashlight, projecting a shadow of $x$ directly onto the axis defined by $q_i$.
• The Big Picture: This equation tells us that the entire complex matrix $S$ is actually just a combination of independent 1D projections. Each projection onto a fundamental axis ($q_i$) is scaled by its importance (${\lambda }_i$) and then added together. This is the exact mechanism PCA uses to reduce dimensions—it simply throws away the projections that have the smallest ${\lambda }_i$ scaling factors!

Singular Value Decomposition (SVD)

Singular Value Decomposition (1)

Notes:

• Using practical pattern 4
  • Correspond to first outer product and then the linear combination of them scaled with each diagonal term
• Lets say we have an $m\times n$ matrix $A$, the shape of $U$ will be $m\times m$, and the shape of $V$ will be $n\times n$
  • Sigma will also have a shape of $m\times n$, where only the diagonal elemets are non-zero
  • But note that $A$ can also be a square matrix
• This gives a very useful decomposition
• How do we interpret it? Given a matrix $A$, how do we get $U$, sigma and $V$?
• In order to prove that this decomposition exists what do we need to do?
  • We need to learn how to calculate U, how to calculate sigma, and how to calculate V
  • These can actually be obtained from eigenvalue decomposition.

Singular Value Decomposition (2)

The singular value decomposition (SVD) of an $m\times n$ real matrix (without loss of generality, we assume $m\ge n$ ) can be written as

where $\mathit{U}$ is an orthogonal $m\times m$ matrix, $\mathit{V}$ is an orthogonal $n\times n$ matrix, and $\tilde{\mathbf{\Sigma }}$ is a diagonal $m\times n$ matrix with non-negative real values on diagonal. That is,

where ${\sigma }_1\ge {\sigma }_2\ge \cdots \ge {\sigma }_n\ge 0$ are known as singular values. If $\mathrm{rank}(\mathit{R})=r(r\le n)$, we have ${\sigma }_1\ge {\sigma }_2\ge \cdots \ge {\sigma }_r>0$ and ${\sigma }_{r+1}={\sigma }_{r+2}=\cdots ={\sigma }_n=0$.

Notes:

• Note that the elements in the sigma matrix are always non-negative singular values! This is very important

  • Typically we will always prefer to order these values
  • The number of singular values directly tells you the rank of $R$

• Exists for any matrix

• A matrix R can be decomposed into further 3 matrices

  • $U$ and $V$ are orthogonal matrices
  • $\tilde{\mathrm{\Sigma }}$ may not be a squared matrix

• We assume that $M$ has more rows than columns (like a vertical rectangle shape) - $m\times n$

• The upper part of $\mathrm{\Sigma }$ is what we call the sigma, it is a diagonal matrix, and everything below is 0

  1. Remember that you can assume this is in sorted order from large to small
  2. Little sigmas are either positive or zero (they are nonnegative)
     • We can always flip the sign in either $U$ or $V$ to make it positive
       • But remember the diagonal elements have to have a negative (for eigenvalues)
  3. If the rank of the $R$ matrix is $r$, then the first ${\sigma }_1,{\sigma }_2,\cdots ,{\sigma }_r$ are greater than 0.
     • The number of positive singular values is the rank of that matrix

• So the conditions come to be: Square matrix + positive semi-definite + symmetric

  • otherwise eigenvalues may not be even real numbers
  • otherwise $\sigma$ values would be negative

• This is called Full SVD

Relation to Eigen-Deconposition

The columns of $\mathit{U}$ (left-singular vectors) are orthonormal eigenvectors of $\mathit{R}{\mathit{R}}^T$, and the columns of $\mathit{V}$ (right-singular vectors) are orthonormal eigenvectors of ${\mathit{R}}^T\mathit{R}$. In other words, we have

It is easy to verify them as we have

and ${\mathit{V}}^T={\mathit{V}}^{-1},{\mathit{U}}^T={\mathit{U}}^{-1}$.

Notes:

• Note $R$ is an $m\times n$ matrix
• If we do $R{R}^T$, this will give us a square matrix ($n\times n$),
  • then from this we can do an eigen-decomposition to get $U\mathrm{\Lambda }{U}^{-1}$
• But we can also do $R^{T}R$, which will also give us a square matrix
  • then from this we can also do an eigen-decomposition to get $V\mathrm{\Lambda }{V}^{-1}$
  • Key properties:
    • $R^{T}R$ is a symmetrical matrix
    • It will always have positive eigenvalues
  • These properties allows it to be written as $V\mathrm{\Lambda }{V}^T$
• Now to verify this, recall this:
  • $(ABC{)}^T=C^T{B}^T{A}^T$
  • Note that $\mathrm{\Lambda }$ will correspond to ${\mathrm{\Sigma }}^2$
• Why is $\lambda$ always properties?

SVD and eigen-decomposition

(1) Under what conditions are SVD and eigen-decomposition the same? First, $\mathit{R}$ is a symmetric matrix, i.e., $\mathit{R}={\mathit{R}}^T$. Second, $\mathit{R}$ is a positive semi-definite matrix, i.e., $\mathrm{\forall }\mathit{x}\in {\mathbb{R}}^n,{\mathit{x}}^T\mathit{R}\mathit{x}\ge 0$.

(2) The difference between $\mathbf{\Lambda }$ in eigen-decomposition and $\mathbf{\Sigma }$ in SVD is that, the diagonal entries of $\mathbf{\Lambda }$ can be negative, while the diagonal entries of $\mathbf{\Sigma }$ are non-negative. What are the fundamental reasons underlying this difference? Why the requirements on the singular values in SVD (non-negative and in sorted order) do not prevent the generality of SVD?

Compact SVD

By removing zero components, we obtain

where $\mathrm{rank}\left({\sigma }_i{\mathit{u}}_i{\mathit{v}}_i^T\right)=1,i=1,2,\dots ,r$.

Notes:

• $R$ is a product of 3 matrices, we can write this multiplication into some kind of process to take an element/row/column of each one and modularly multiply them
• You take $u_1$, multiply with ${\sigma }_1$, and multipy by $v_1^T$.
  • This makes a matrix
• You continue with $u_2,u_3,\cdots ,u_r$
• Then you add every matrix produced
• It is a different way to talk about matrix multiplication
• The lower method is called Compact SVD
  • Remember ${\mathrm{\Sigma }}_r$ is basically the upper part of the matrix
  • This is exactly equivalent to summing each multiplication of ${\sigma }_i{u}_i{v}_i^T$ until $i=r$
  • So basically in compact SVD we just throw away all rows and columns corresponding to the 0 elements
• Now what happens if we do $i=1$ to $k$ where $k<r$
  • You still get a matrix but it will not be exactly be equal to $r$, though it will still have the same size as $r$.

Truncated SVD and Best Low-Rank Approximation

We can also approximate the matrix $\mathit{R}$ with the $k$ largest singular values as

Apparently, $\mathit{R}\ne {\mathit{R}}_k$ unless $\mathrm{rank}(\mathit{R})=k$. This approximation is the best in following sense:

where $\parallel \cdot {\parallel }_F$ denotes the Frobenius norm and $\parallel \cdot {\parallel }_2$ denotes the spectral norm, defined as the largest singular value of the matrix. That is, ${\mathit{R}}_k$ is the best rank- $k$ approximation to $\mathit{R}$ in terms of both the Frobenius norm and spectral norm. Note the difference in terms of approximation errors when different matrix norms are used.

Notes:

• The $R_k$ matrix is the best rank-$k$ approximation to $R$
• See this is very important because for each $i$ we have a matrix, so then we will have $k$ matrices added together
  • This happens element-wise because they have the same size
  • What do we know about the rank of the resulting matrix once they are summed?
    • When you add a matrix of rank 3 and a matrix of rank 4, the resulting matrix rank cannot be larger than 7, this is guaranteed!
    • There is no lower bound though
    • In this case the $R_k$ matrix will have rank $k$
  • The most important part is that this matrix is the closest one to the original $R$
• The error is related to the size of $\mathrm{\Sigma }$ -> size of the sigma that you throw away?
• Frobenius norm is basically to take the element-wise difference of the two matrices, and ...
• Remember again that Sigma is sorted from large to small
  • You always try to throw away smaller sigmas
• When using $k$ there will always be error, since it is smaller than $r$
• In practice (i.e think about images)
  • Color images of 500x500x3
  • Each location can have 256 different values
  • The total number of possible images of this size is ${256}^{500\times 500\times 3}$
  • In reality all the existing images is a tiny fraction of the actual number of possible images
  • Intrinsic dimension is quite small even when dimension is large

Checkpoint 2 (SVD)

To understand Singular Value Decomposition (SVD), we must realize that pure eigen-decomposition has a severe limitation: it only works for square matrices. In machine learning, our raw data is almost always a rectangular matrix (e.g., $N$ samples by $D$ features).

1. Singular Value Decomposition & SVD (2) SVD is the ultimate mathematical tool because it exists for any real matrix, no matter its shape. If you have a rectangular data matrix $R$ (of size $m\times n$), SVD factorizes it into three matrices: $R=U\tilde{\mathrm{\Sigma }}{V}^T$.

• $U$ (Left-Singular Vectors): An orthogonal $m\times m$ matrix.
• $V$ (Right-Singular Vectors): An orthogonal $n\times n$ matrix.
• $\tilde{\mathrm{\Sigma }}$ (The Singular Values): A diagonal $m\times n$ matrix. Unlike eigenvalues, the numbers on this diagonal (called singular values, $\sigma$) are strictly non-negative and are always sorted from largest to smallest (${\sigma }_1\ge {\sigma }_2\ge \cdots \ge 0$).
• The Rank: The number of strictly positive singular values ($\sigma >0$) tells you the exact mathematical rank ($r$) of the matrix.

2. Relation to Eigen-Decomposition If $R$ is rectangular, how do we find $U$ and $V$? We use a clever trick to force the matrix to become square and symmetric.

• If we multiply $R{R}^T$, we get a square $m\times m$ symmetric matrix. The eigenvectors of $R{R}^T$ exactly form the columns of our $U$ matrix.
• If we multiply $R^{T}R$, we get a square $n\times n$ symmetric matrix. The eigenvectors of $R^{T}R$ exactly form the columns of our $V$ matrix.
• Because of how the math cancels out ($R^{T}R=V{\mathrm{\Sigma }}^2{V}^T$), the singular values ($\sigma$) are simply the square roots of the eigenvalues ($\lambda$) obtained from these squared matrices.

3. SVD and eigen-decomposition When are SVD and eigen-decomposition the exact same thing? Because SVD enforces that all singular values ($\sigma$) must be positive, an eigen-decomposition only matches the SVD if its eigenvalues ($\lambda$) are also guaranteed to be positive. Therefore, the original matrix must be symmetric ($R=R^T$) and Positive Semi-Definite ($x^{T}Rx\ge 0$).

4. Compact SVD If the rank ($r$) of your matrix is smaller than its dimensions, you will have singular values that are exactly $0$ at the bottom of the $\mathrm{\Sigma }$ matrix. Because anything multiplied by $0$ is $0$, storing those values and their corresponding columns in $U$ and $V$ is a waste of computer memory. Compact SVD simply throws away the zero components. By rewriting the matrix multiplication as a sum of outer products, we get $R=\sum _{i=1}^r{\sigma }_i{u}_i{v}_i^T$. We only sum up to the rank $r$, losing absolutely no information.

5. Truncated SVD and Best Low-Rank Approximation Compact SVD throws away exact zeros. But what if we throw away small (but non-zero) singular values to intentionally compress the data? If we stop the summation early at some number $k$ (where $k<r$), we get a new, compressed matrix $R_k=\sum _{i=1}^k{\sigma }_i{u}_i{v}_i^T$.

• Why is this amazing? Linear algebra guarantees that this truncated matrix $R_k$ is the absolute best rank-$k$ approximation of the original data matrix $R$.
• There is no other rank-$k$ matrix in existence that will give you a smaller reconstruction error (measured by the Frobenius or spectral norms). The error is exactly tied to the $\sigma$ values you decided to throw in the trash.

Principal Component Analysis (PCA)

What is PCA?

(1) Principal Component Analysis (PCA) is a statistical procedure that can be used to achieve feature (dimensionality) reduction.

(2) Note, feature reduction is different from feature selection. After feature reduction, we still use all the features, while feature selection selects a subset of features to use.

(3) The goal of PCA is to project the high-dimensional features to a lower-dimensional space with maximal variance and minimum reconstruction error simultaneously.

(9) We derive PCA based on maximizing variance, and then we show the solution also minimizes reconstruction error.

(6) In machine learning, PCA is an unsupervised learning technique, and therefore does not need labels.

Notes:

• The calculation of PCA is simply SVD
  • There is a very small difference but important that we need to do
• SVD is unsupervised, so we are only given $x$ (no labels)

PCA to 1D

(1) To introduce PCA, we start from the simple case where PCA projects the features to a 1 -dimensional space.

(2) Formally, suppose we have $np$-dimensional ( $p>1$ ) features ${\mathit{x}}_1,{\mathit{x}}_2,\dots ,{\mathit{x}}_n\in {\mathbb{R}}^p$.

(3) Let $\mathit{a}\in {\mathbb{R}}^p$ represent a projection that ${\mathit{a}}^T{\mathit{x}}_i=z_i,i=1,2,\dots ,n$ where $z_1,z_2,\dots ,z_n\in {\mathbb{R}}^1$.

(4) PCA aims to solve

(5) Note that the variance of the reduced data is

which means that PCA tries to find the projection with the maximum variance in reduced data.

Notes:

• We have some data points (each is P dimensional) and want to make them shorter dimensional (for example a single number)
• Each of the inputs become a $p$-dimensional vector
• We want each of the input vectors to be a shorter vector while still keeping most of the information
  • What information to keep? we will talk about it
• Lets say we want to reduce each of the long inputs ($x_i$) to 1 dimension (the simplest one)
• Come up with an $a$ (unknown for now), then what we want to do is to compute the inner product: $a^T{x}_i$
  • This is basically a reduced (low-dimensional) representation of $x_i$
  • By using this $a$, we basically reduced $x$ to a number
  • If that $a$ is applied to every $x$ you get a set of $z_i$ values, which are just 1D single values
• This is already basically PCA
• Now we need to talk about how to compute $a$
• What kind of $a$'s are intuitively good?
  • Lets say you r data is 2-dimensional (p=2), and you want to reduce to 1D
  • $a$ needs to project this data into a 1D space
    • It needs to project data in some direction
      • i.e. if you project in the x axis you lose a coordinate
      • What about a diagonal? some differences disappear, points on top of each other diagonally will become a single point
        • This is exactly what PCA tries to do!
    • You can compute the variance to check that the spread is large
    • So our job is to pick $a$ that takes advantage of a maximum variance
      • "Compute $a$ so that the reduced data has maximum variance"
• How to do it?
  • We have each of the $z$'s are computed using $a$, so that each of them have maximum awareness
  • $\overline{z}$ is the mean of $z$
  • PCA will try to arg max the variance (basically maximize the variance)
    • We want to compute variance so that it is as large as possible?
• PCA is an unsupervised dimensional thing

PCA to 1D (process)

Since

the problem can be written as

where $\mathit{C}=\frac{1}{n}\sum _{i=1}^n(x_i-\overline{x}){(x_i-\overline{x})}^T$, denotes the covariance matrix.

Notes:

• Lets start from $\overline{z}$, the mean of the $z_i$ numbers
• We know that each $z_i$ is $a^T{x}_i$
• We know that $a^T$ is actually not changing so we can move it out of the summation
• Instead, first produce the mean of the original data ($\overline{x}$) and then multiply by $a^T$
  • This basically shows that the operation is linear
• At this point we know $\overline{z}=a^T\overline{x}$
• Then we actually calculate and try to maximize the variance using arg max
• Then we substitute our $z$ and $\overline{z}$ by their representations in terms of $a$
• $a^T{x}_i-a^T\overline{x}$ is basically a number, and when we do $(a^T{x}_i-a^T\overline{x}{)}^2$ we want to write it twice
  • This is a number being squared (it multiplies by itself)
  • We can write it as $a^T(x_i-\overline{x})\cdot (x_i-\overline{x}{)}^{T}a$
• Then we can apply the summation, and at this point we realize we can actually take $a^T$ out of the summation, since it is not changing at all

- The whole point here is that we need to do something with this matrix: $(x_i-\overline{x})$
- Note the matrix in the brackets only depends on your input data, this is called the covariance matrix (completely out of your dataset)
- It basically represents the reverse of the reduced data

• At the end what we do is: $$\text{arg max }a^TCa$$
  • where C is the covariance matrix completely dependent on your data
• What is the covariance matrix?
  • How do we get rid of that summation and write it in terms of matrices?
    • Note we have a column vector $(x_i-\overline{x})$ and the same vector transposed $(x_i-\overline{x}{)}^T$
    • So basically we can write this as a multiplication of two matrices
    • Instead suppose we have the data matrix: $\tilde{X}=[x_i-\overline{x}\cdots x_i-\overline{x}\cdots ]$
      • Just subtract each column of $X$ by the mean
    • Now given this $\tilde{X}$, how do we compute the covariance matrix? This will be in the exam! $$C = \frac{1}{n}\tilde{X}\tilde{X}^T$$

PCA to k-dimensional space

(1) What if we want to project the features to a $k$-dimensional space? Then the PCA problem becomes

where $\mathit{A}=[{\mathit{a}}_1,{\mathit{a}}_2,\cdots ,{\mathit{a}}_k]\in {\mathbb{R}}^{p\times k}$. Note that when projecting onto $k$-dimensional space, PCA requires different projection vectors to be orthogonal. Also, the trace above is the sum of the variances after projecting the data to each of the $k$ directions as

Notes:

• If you want to predict at k-dimensional vector
• For each dimension you need to have an entry on the A matrix ($a^k$), each being a $p$-dimensional vector
• Note for 1D:
  • Variance of z = $a^{T}Ca$
• For k-dimension
  • For each of the $a$ you just do the same thing, this gives you a number, then sum all of them together
    • Summation of the variance along each projection
  • This summation can be written as $\text{trace}(A^{T}CA)$
    • where $\text{trace}$ is just the summation of the diagonal elements
• Concerns:
  • Each of the columns of $A$ is orthogonal to each other and is normalized
    • Orthonormal columns
• There would be a question on PCA in the final exam!
• Remember C is given
• A will be computed by taking eigen-vectors and eigen-values for this matrix

Ky Fan Theorem

(1) Solving the problem in Eqn. (2) requires the follow theorem.
(2) Theorem. (Ky Fan) Let $\mathit{H}\in {\mathbb{R}}^{n\times n}$ be a symmetric matrix with eigenvalues

and the corresponding eigenvectors $\mathit{U}=[{\mathit{u}}_1,\dots ,{\mathit{u}}_n]$. Then

And the optimal ${\mathit{A}}^{\ast }$ is given by ${\mathit{A}}^{\ast }=[{\mathit{u}}_1,\dots ,{\mathit{u}}_k]\mathit{Q}$ with $\mathit{Q}$ an arbitrary orthogonal matrix.

Notes:

• To solve k-dimensional PCA we use the Key Fan Theorem
• This theorem basically tells you that the solution:
  • Compute Eigenvalue and eigenvectors of the $H$ matrix and take the $k$ eigenvector corresponding to the $k$-largest eigenvalues.
  • Put these eigenvectors as columns on matrix $A$?

Solutions to PCA

(1) Note that in Eqn. (2), the covariance matrix $\mathit{C}$ is a symmetric matrix. Given the above theorem, we directly obtain

where ${\lambda }_1,\dots ,{\lambda }_k$ are the $k$ largest eigenvalues of the covariance matrix $\mathit{C}$, and the solution ${\mathit{A}}^{\ast }$ is the matrix whose columns are corresponding eigenvectors.
(2) It also follows from the above theorem that solutions to PCA are not unique, and they differ by an orthogonal matrix. We used the special case where $\mathit{Q}=\mathit{I}$, i.e., ${\mathit{A}}^{\ast }=[{\mathit{u}}_1,\dots ,{\mathit{u}}_k]$.

Notes:

• We need to compute C, it is the covariance matrix dependent only on your data
• We need to do eigen-decomposition of the covariance matrix

Checkpoint 3 (PCA and solutions)

To understand Principal Component Analysis (PCA), imagine you are holding a 3D cloud of data points (like a swarm of bees). If you want to draw this 3D cloud on a 2D piece of paper, you have to squash it flat. If you squash it from the wrong angle, all the bees will overlap and look like a single blob. If you squash it from the right angle, you can still see the distinct shape and spread of the swarm. PCA is the mathematical tool that finds the absolute best angle to squash (project) your data.

1. What is PCA? PCA is an unsupervised dimensionality reduction technique.

• Unsupervised means we do not care about labels or classes (like "cat" or "dog"); we only care about the raw data points ($x$).
• Dimensionality reduction means taking data with hundreds of features (like a 10,000-pixel image) and compressing it into a much smaller, manageable set of features (like 50 numbers) without losing the core structure.
• To do this successfully, PCA has two equivalent goals: Maximize the variance (keep the data as spread out as possible so points don't overlap) and Minimize the reconstruction error (ensure we can rebuild the original data from the compressed version as accurately as possible).

2. PCA to 1D Let's start with the simplest case: compressing a $p$-dimensional dataset down to a single 1D line.

• We define a vector $a$ (which has a length of 1, written as $|a|=1$). This vector represents the direction of the 1D line we want to project our data onto.
• When we project an original data point $x_i$ onto this line, it becomes a single scalar number: $z_i=a^T{x}_i$.
• The Goal: We want to choose the line $a$ that results in the new $z_i$ points being as spread out as possible. In statistics, "spread" is measured by variance. Therefore, we want to find the $a$ that maximizes the variance of $z$.

3. PCA to 1D (process) How do we mathematically maximize this variance?

• The formula for the variance of our projected points is: $\frac{1}{n}\sum (z_i-\overline{z}{)}^2$.
• If we substitute $z_i$ with our projection formula ($a^T{x}_i$), we can use algebra to pull the $a$ vector completely outside of the summation.
• When we pull $a$ out, the messy sum of data points left in the middle perfectly simplifies into the Covariance Matrix ($C$) of our original data.
• The Result: The entire complex problem boils down to a very clean linear algebra objective: Find $a$ to maximize $a^{T}Ca$.

4. PCA to k-dimensional space Usually, we want to compress our data to $k$ dimensions, not just 1.

• Instead of a single line $a$, we now need a matrix $A$ made up of $k$ different lines (vectors).
• These $k$ lines must be perfectly perpendicular (orthogonal) to each other, which is written mathematically as $A^{T}A=I_k$.
• Instead of maximizing a single variance, we want to maximize the sum of the variances across all $k$ directions. In matrix math, the sum of the diagonal (which contains these variances) is called the trace. Thus, our new goal is to maximize the $\text{trace}(A^{T}CA)$.

5. Ky Fan Theorem & Solutions to PCA How on earth do we actually solve $\arg max\text{trace}(A^{T}CA)$? Your professor introduces the Ky Fan Theorem, which is the magical key to PCA.

• The theorem states that if you have a symmetric matrix (and our Covariance Matrix $C$ is always symmetric), the absolute maximum possible trace you can achieve when projecting onto $k$ dimensions is simply the sum of its $k$ largest eigenvalues (${\lambda }_1+{\lambda }_2+\cdots +{\lambda }_k$).
• Furthermore, the theorem tells us exactly how to achieve this maximum: the optimal projection matrix $A^{\ast }$ is built by simply taking the $k$ eigenvectors that correspond to those $k$ largest eigenvalues.
• Summary: To compress your data to the best possible $k$ dimensions, just calculate the eigenvectors of your data's covariance matrix, pick the $k$ ones with the biggest eigenvalues, and use them as your projection axes!

Computing the covariance matrix:
To understand this, we have to look at how linear algebra allows us to take a long, tedious summation formula and compress it into a single, highly efficient matrix multiplication.

1. The Original Summation Formula The standard statistical formula for the Covariance Matrix ($C$) of a dataset is: $$C = \frac{1}{n} \sum_{i=1}^n(x_i - \bar{x})(x_i - \bar{x})^T$$ Let's look at the pieces of this equation:

• $x_i$ is a single data point (a column vector of size $p\times 1$).
• $\overline{x}$ is the mean of all data points (also a column vector of size $p\times 1$).
• $(x_i-\overline{x})$ is just the data point with the mean subtracted. It is still a column vector.
• $(x_i-\overline{x}{)}^T$ is that exact same vector, but transposed into a row vector ($1\times p$).

When you multiply a column vector by a row vector, you get a full matrix (this is an outer product). The summation symbol $\sum$ means you have to calculate this $p\times p$ matrix for every single data point $i$, and then add all $n$ of those matrices together. Doing this in a loop is incredibly slow.

2. Step 1: Constructing the Centered Data Matrix ($\tilde{X}$) Instead of looking at data points one by one, we want to look at the entire dataset at once. Suppose your original data matrix $X$ has all your data points stacked side-by-side as columns. To get rid of the $(x_i-\overline{x})$ part of the formula, we create a new matrix called the centered data matrix ($\tilde{X}$). You build this by simply taking your original matrix $X$ and subtracting the mean vector $\overline{x}$ from every single column.

• The Math Trick: To do this in pure matrix math, you take the mean vector $\overline{x}$ and multiply it by a row vector of all 1s ($1_n^T$). This perfectly copies the mean vector $n$ times side-by-side so it becomes a matrix of the exact same size as $X$.
• Then, you just subtract them: $\tilde{X}=X-\overline{X}{1}_n^T$. Now, $\tilde{X}$ is a massive matrix where column 1 is $(x_1-\overline{x})$, column 2 is $(x_2-\overline{x})$, and so on.

3. Step 2: The Matrix Multiplication Trick Now we have our centered data matrix $\tilde{X}$ (size $p\times n$). If we transpose it, we get ${\tilde{X}}^T$ (size $n\times p$), where all those centered columns become rows. What happens if we multiply $\tilde{X}$ by ${\tilde{X}}^T$? If you recall "Matrix times Matrix - 4 ways" (specifically Pattern MM4) from your earlier slides, multiplying a matrix by another matrix is mathematically identical to taking the outer product of their corresponding columns and rows, and summing them all together.

By simply computing $\tilde{X}{\tilde{X}}^T$, the rules of linear algebra automatically perform the exact summation of outer products that our original covariance formula required.

Therefore, the entire messy summation formula perfectly collapses into: $$C = \frac{1}{n}\tilde{X}\tilde{X}^T$$

EXAM TOPIC: How to compute Covariance Matrix ($C$) from Data ($X$)
If you are asked to compute the covariance matrix efficiently using matrices (no summations):

1. Find the Mean: Calculate the mean column vector $\overline{x}$ from your data.
2. Center the Data ($\tilde{X}$): Subtract the mean vector from every column of your original data matrix $X$.
   • Matrix Form: $\tilde{X}=X-\overline{X}{1}_n^T$ (where $1_n^T$ is a row vector of $n$ ones used to duplicate the mean vector across all columns).
3. Compute Covariance ($C$): Multiply the centered matrix by its transpose and divide by the number of samples ($n$).
   • Matrix Form: $C=\frac{1}{n}\tilde{X}{\tilde{X}}^T$.

• Why it works: Multiplying $\tilde{X}$ (columns) by ${\tilde{X}}^T$ (rows) perfectly replicates the sum of outer products $\sum (x_i-\overline{x})(x_i-\overline{x}{)}^T$ via standard matrix multiplication rules (Pattern MM4).

How to compute PCA efficiently?

(1) We define

where $1_n$ is the $n$-dimensional all-one vector. Here, $\tilde{\mathit{X}}$ is the centered $\mathit{X}$, which is obtained by subtracting the mean from each column.
(2) Then we have

If $p$ is large, it is very costly to compute eigenvectors of $\mathit{C}$ directly. Moreover, if $p\gg n$, there are known computational problems.

Notes:

• We can also write the covariance matrix as: $$C = \frac{1}{n}\tilde{X}\tilde{X}^T$$- $\overline{X}$ is each column summed together and divided by $n$
  • It represents the mean vector of your data
  • This is how you could do it if you only had 3 lines of code and no loop
• How can we subtract the data vector ($X$) by the mean vector ($\overline{X}$)?
  • You need a matrix of the same size as $X$, then subtract the matrix
  • You multiply a matrix of all 1s but transposed
    • This is to simply copy that vector $n$ times, and become a matrix
    • Now each column of that matrix is simply $\overline{X}$
      • (i.e. $\overline{X}[111\cdots ]$)
• These 3 operations are just one line of code!
• Now the second line is the following:
  • Actually get the covariance matrix by doing: $C=\frac{1}{n}\tilde{X}{\tilde{X}}^T$
  • Note this matrix is commonly symmetric
• In theory if we are dealing with a small dataset, that is fine, this is the way to do it.
• After this step we would just do eigen-decomposition of the covariance matrix
• If p (number of dimensions) is very large, the resulting matrix will be a $p\times p$ matrix, where $p$ is the dimension of your data
  • In practice this is hard, if $p$ is very large, this is commonly not practical
• You will need to know how to compute from $X$ to $C$ in the exam!
• What does a covariance matrix really tell you (not needed for exam)?
  • What does a $p\times p$ matrix tell you? what are these numbers?
  • The relationship between the variance of the dataset with each variable?
  • What are the diagonal elements?
    • Compute inner product with itself, for each row in $\tilde{X}$
    • Each row is the same feature for all data points
    • Tells you how much this number (for each two vectors) is different from the mean
  • The other elements tell you each variable variance across its mean
• The better way to do it is in #Relation to Eigen-Deconposition (you compute the SVD of the $\tilde{X}$ matrix)
  • You only need to compute the SVD of R
  • Remember how we move the transpose inside the parenthesis (we need to swap the order of the matrices)
  • Columns of $U$ will be the eigenvector
  • And remember $R$ is simply $\tilde{X}$
  • This is basically the second line of code (compute SVD of $\tilde{X}$)
    • What can you see from the eigen-decomposition of the $U$ matrix
    • Diagonal matrix squared is just the square of each of the diagonal elements
    • So this covariance matrix is positive semi-definite.
    • You can prove just by definition: $$x^TRR^Tx = (R^TX^T)(R^TX)$$
      • This is just a vector transpose of a vector
• Note up to here everything still depends on the data vector $X$
• So if $p$ is very large, you have another way to do it.
  1. Compute $\tilde{X}$ (centered data matrix) - YOU NEED TO KNOW HOW TO COMPUTE THIS - It is just a subtracted mean
  2. Compute the covariance matrix $C$
  3. Then compute eigen-decomposition of this $C$ matrix, which is equivalent to computing the SVD of $\tilde{X}$

(1) However, we show that the SVD of $\bar{\mathit{X}}$ provides what we need. If the SVD of $\tilde{\mathit{X}}$ is $\tilde{\mathit{X}}=\mathit{U}\tilde{\mathbf{\Sigma }}{\mathit{V}}^T$, the columns of $\mathit{U}$ (left-singular vectors) are orthonormal eigenvectors of $\tilde{\mathit{X}}{\tilde{\mathit{X}}}^T$. Note that we have ${\sigma }_1\ge {\sigma }_2\ge \cdots \ge {\sigma }_n\ge 0$ in Eqn. (1) and thus, the first $k$ columns of $\mathit{U}$ correspond to the largest $k$ eigenvalues of $\tilde{\mathit{X}}{\tilde{\mathit{X}}}^T$.

(2) With the SVD of $\tilde{\mathit{X}}$, if we want to project features to a $k$-dimensional $(k<p)$ space, simply take the first $k$ columns of $\mathit{U}$ as the projection matrix. Generally, the process of computing PCA can be described as

Then the projected features are

It is worth noting that the $k$-th row in $\mathit{Z}$ is called the $k$-th principal components (PC). Therefore, PCA achieves feature reduction by keeping only the first $k$ PCs.

Notes:

• This is a quick summary:
  1. You are given $X$
  2. You compute $\tilde{X}$
  3. You compute the SVD of $\tilde{X}$
  4. G is a matrix we will use to transform our data, we just need to get the $k$ columns of $U$.
• Centered data is better to use because it is zero-mean, numerically it is better (though nothing is wrong predicting the original data)
• The way to project that is to take $G^T\tilde{X}$
  • This is basically the last (third) line of your code
  • $Z$ is now your reduced data!
  • Each column in $Z$ is $k$-dimensional
• This is very nice because:
  • We can write SVD in terms of a summation of ${\sigma }_i{u}_i{v}_i^T$
  • This tells you something interesting:
    • We can do this operation incrementally
  • You do not need to redo calculations, if you want more dimensions, you just need to add the projections necessary to get to that dimension
    • Example: if you calculate k = 3, and you want to get k = 4, k = 5, etc. you do not have to repeat k = 3, you just need one more projection for k = 4 and one other projection for k = 5
• We still have a large step after this, which is to do reconstruction
  • Suppose you want to transfer images to someone but they are too large? you can give $Z$ and $G$ to that person, then they will be able to reconstruct some version of $\overline{X}$ (a low rank approximation to $\tilde{X}$)
  • This has nothing to do with passing the exam
• Look at the covariance matrix and think about what it means

Centered or not?

(1) Note that we project the centered data matrix $\tilde{\mathit{X}}$ instead of the original data matrix $\mathit{X}$ in Eqn (3). Maximal variance can be achieved in both cases, as the the covariance matrix $\mathit{C}$ will not change.

(2) But the minimal reconstruction error can only be achieved when $\tilde{\mathit{X}}$ is used, as shown in the next section.

(3) A common practice to avoid any confusion is to center the data before applying PCA, and use the centered data matrix in all computations.

Notes:

• Basically if you do not want to be wrong use $\tilde{X}$

Have We Achieved the Minimal Reconstruction Error?

(1) First, we perform the verification in the case where we project and reconstruct the centered data matrix $\tilde{\mathit{X}}$.

(2) Given the projection

the reconstruction process is

and the reconstruction error is

(3) We will show that

which means $\check{\mathit{X}}$ gives the minimum reconstruction error.

(4) We've already learned that ${\mathit{B}}^{\ast }$ is the truncated SVD of $\tilde{\mathit{X}}$. So, we only need to show that $\mathit{G}{\mathit{G}}^T\tilde{\mathit{X}}$ is indeed the truncated SVD of $\tilde{\mathit{X}}$ as follows. Note that similar arguments can be made for the spectral

Notes:

• Suppose $\tilde{X}$ is a bunch of images, what you do is to convert each image into a long vector, that vector is the columns of $X$ (a flatten image)
• Z is a matrix where each column is a data point
• If you want an image to maintain more information, use larger $k$.
  • Remember both $Z$ and $G$ depend on $k$.
• We can get an approximate $X$ matrix by doing the reconstruction step: $$
  \check{\boldsymbol{X}}=\boldsymbol{G} \boldsymbol{Z}=\boldsymbol{G} \boldsymbol{G}^T \tilde{\boldsymbol{X}},

\begin{aligned}
\boldsymbol{G G}^T \tilde{\boldsymbol{X}} & =\boldsymbol{U}_k \boldsymbol{U}_k^T \boldsymbol{U} \tilde{\boldsymbol{\Sigma}} \boldsymbol{V}^T \
& =\boldsymbol{U}_k \boldsymbol{U}_k^T\left[\boldsymbol{U}k \quad \boldsymbol{U}\right] \tilde{\boldsymbol{\Sigma}} \boldsymbol{V}^T \
& =\boldsymbol{U}_k\left[\begin{array}{ll}
\boldsymbol{I} & 0
\end{array}\right] \tilde{\boldsymbol{\Sigma}} \boldsymbol{V}^T \
& =\left[\begin{array}{ll}
\boldsymbol{U}_k & 0
\end{array}\right] \tilde{\boldsymbol{\Sigma}} \boldsymbol{V}^T \
& =\boldsymbol{U}_k \boldsymbol{\Sigma}_k \boldsymbol{V}k^T \
& =\sum^k \sigma_i \boldsymbol{u}_i \boldsymbol{v}_i^T
\end

\min _{\boldsymbol{B}: \operatorname{rank}(\boldsymbol{B}) \leq k}|\tilde{\boldsymbol{X}}-\boldsymbol{B}|_F=\left|\tilde{\boldsymbol{X}}-\boldsymbol{G} \boldsymbol{G}^T \tilde{\boldsymbol{X}}\right|F=\sqrt{\sum^n \sigma_i^2} .