Mathematical Foundations of Machine Learning

Prof. Matthieu Bloch

Monday, October 21, 2024 (v1.0)

Last time

Last class: Wednesday October 16, 2024
- We talked about the existence of eivenvalues and eigenvectors
- We are making our way towards the SVD
Today: We will talk about the spectral theorem

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
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

Every complex matrix $A$ has at least one complex eigenvector and every real symmetrix matrix has real eigenvalues and at least one real eigenvector.

Every matrix $A \in C^{n \times n}$ is unitarily similar to an upper triangular matrix, i.e., $A = V Δ V^{†}$ with $Δ$ upper triangular and $V^{†} = V^{- 1}$ .

Every hermitian matrix is unitarily similar to a real-valued diagonal matrix.

Note that if $A = V D V^{†}$ then $A = \sum_{i = 1}^{n} λ_{i} v_{i} v_{i}^{†}$

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

Symmetric positive definite matrices

A symmetric matrice $A$ is positive definite if it has positive eigenvalues, i.e., $\forall i \in {1, \dots, n} λ_{i} > 0$ .

A symmetric matrice $A$ is positive semidefinite if it has nonnegative eigenvalues, i.e., $\forall i \in {1, \dots, n} λ_{i} \geq 0$ .

Convention: $λ_{1} \geq λ_{2} \geq \dots \geq λ_{n}$

Variational form of extreme eigenvalues for symmetric positive definite matrices $A$ $λ_{1} = max_{x \in R^{n} : {‖ x ‖}_{2} = 1} x^{⊺} A x = max_{x \in R^{n}} \frac{x^{⊺} A x}{{‖ x ‖}_{2}^{2}} λ_{n} = min_{x \in R^{n} : {‖ x ‖}_{2} = 1} x^{⊺} A x = min_{x \in R^{n}} \frac{x^{⊺} A x}{{‖ x ‖}_{2}^{2}}$

For any analytic function $f$ , we have $f (A) = \sum_{i = 1}^{n} f (λ_{i}) v_{i} v_{i}^{⊺}$

System of symmetric definite equations

Consider the system $y = A x$ with $A$ symmetric positive definite

Let ${v_{i}}$ be the eigenvectors of $A$ . $x = \sum_{i = 1}^{n} \frac{1}{λ_{i}} {⟨ y, v_{i} ⟩}_{} v_{i}$

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

$\frac{1}{λ_{1}^{2}} {‖ e ‖}_{}^{2} \leq {‖ x - \tilde{x} ‖}_{2} \leq \frac{1}{λ_{n}^{2}} {‖ e ‖}_{}^{2} .$

What about the average case?

Next time

Next class: Wednesday October 23, 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)