Mathematical Foundations of Machine Learning

Last time

• Last class: Monday October 21, 2024
  • We talked about the spectral theorem
  • We are making our way towards the SVD
• Today: We will talk about the singular value decomposition

• To be effectively prepared for today's class, you should have:
  1. Gone over slides and read associated lecture notes here
  2. Submitted Homework 4 and started working on Homework 5
• Logistics: use office hours to prepare for Homework 4
  • Jack Hill office hours: Wednesday 11:30am-12:30pm in TSRB and hybrid
  • Anuvab Sen office hours: Thursday 12pm-1pm in TSRB and hybrid
  • Dr. Bloch: Friday October 25, 2024 6pm
• Homework 5: due Tuesday October 22, 2024
  • Don't start accumulating delays, Homework 6 is coming

Spectral theorem

• Note that if $\mathbf{A}=\mathbf{V}\mathbf{D}{\mathbf{V}}^{†}$ then $\mathbf{A}=\sum _{i=1}^n{\lambda }_i{\mathbf{v}}_i{\mathbf{v}}_i^{†}$

• How about real-valued matrices $\mathbf{A}\in {\mathbb{R}}^{n\times n}$?

Symmetric positive definite matrices

• Convention: ${\lambda }_1\ge {\lambda }_2\ge \cdots \ge {\lambda }_n$

• Variational form of extreme eigenvalues for symmetric positive definite matrices $\mathbf{A}$ $${\lambda }_1=\underset{\mathbf{x}\in {\mathbb{R}}^n:{\Vert \mathbf{x}\Vert }_2=1}{max}{\mathbf{x}}^{⊺}\mathbf{A}\mathbf{x}=\underset{\mathbf{x}\in {\mathbb{R}}^n}{max}\frac{{\mathbf{x}}^{⊺}\mathbf{A}\mathbf{x}}{{\Vert \mathbf{x}\Vert }_2^2}{\lambda }_n=\underset{\mathbf{x}\in {\mathbb{R}}^n:{\Vert \mathbf{x}\Vert }_2=1}{min}{\mathbf{x}}^{⊺}\mathbf{A}\mathbf{x}=\underset{\mathbf{x}\in {\mathbb{R}}^n}{min}\frac{{\mathbf{x}}^{⊺}\mathbf{A}\mathbf{x}}{{\Vert \mathbf{x}\Vert }_2^2}$$

System of symmetric definite equations

• Consider the system $\mathbf{y}=\mathbf{A}\mathbf{x}$ with $\mathbf{A}$ symmetric positive definite

• Assume that there exists some observation error $\mathbf{y}=\mathbf{A}\mathbf{x}+\mathbf{e}$
  • $\mathbf{e}$ is unknown
  • we try to reconstruct $\mathbf{x}$ as $\tilde{\mathbf{x}}$ by applying ${\mathbf{A}}^{-1}$

• What about the average case?

Singular value decomposition

• What happens for non-square matrice?

• We say that $\mathbf{A}$ is full rank is $r=min(m,n)$

• We can write $\mathbf{A}=\sum _{i=1}^r{\sigma }_i{\mathbf{u}}_i{\mathbf{v}}_i^{⊺}$

Important properties of the SVD

• The columns of $\mathbf{V}$ ${\{{\mathbf{v}}_i\}}_{i=1}^r$ are eigenvectors of the psd matrix ${\mathbf{A}}^{⊺}\mathbf{A}$. $\{{\sigma }_i:1\le i\le n\text{ and }{\sigma }_i\ne 0\}$ are the square roots of the non-zero eigenvalues of ${\mathbf{A}}^{⊺}\mathbf{A}$.

• The columns of $\mathbf{U}$ ${\{{\mathbf{u}}_i\}}_{i=1}^r$ are eigenvectors of the psd matrix $\mathbf{A}{\mathbf{A}}^{⊺}$. $\{{\sigma }_i:1\le i\le n\text{ and }{\sigma }_i\ne 0\}$ are the square roots of the non-zero eigenvalues of $\mathbf{A}{\mathbf{A}}^{⊺}$.

• The columns of $\mathbf{V}$ form an orthobasis for $\text{row}(\mathbf{A})$

• The columns of $\mathbf{U}$ form an orthobasis for $\text{col}(\mathbf{A})$

• Equivalent form of the SVD: $\mathbf{A}=\tilde{\mathbf{U}}\tilde{\mathbf{\Sigma }}{\tilde{\mathbf{V}}}^T$ where

  • $\tilde{\mathbf{U}}\in {\mathbb{R}}^{m\times m}$ is orthonormal
  • $\tilde{\mathbf{V}}\in {\mathbb{R}}^{n\times n}$ is orthonormal
  • $\tilde{\mathbf{\Sigma }}\in {\mathbb{R}}^{m\times n}$ is

  $$\tilde{\mathbf{\Sigma }}\triangleq \left[\begin{array}{cc}\mathbf{\Sigma }& \mathbf{0}\\ \mathbf{0}& \mathbf{0}\end{array}\right]$$

Next time

• Next class: Monday October 28, 2024

• To be effectively prepared for next class, you should:
  1. Go over today's slides and read associated lecture notes here
  2. Work on Homework 5
• Optional
  • Export slides for next lecture as PDF (be on the lookout for an announcement when they're ready)