Mathematical Foundations of Machine Learning

Last time

Last class: Wednesday September 04, 2024
- We talked about how to compute the coefficients of a projection (in finite dimension)
- We saw the importance of an orthobasis and extended the definition to infinite dimension
- We proved the continuity of the inner product and Bessel's inequality
- We introduced the notion of separable space to reproduce some of the properties of finite dimension
To be effectively prepared for today's class, you should have:
1. Gone over last week's slides and read associated lecture notes
2. Started looking at Homework 2 (due Friday September 13, 2024)
Logistics
- Office hours
  - Jack Hill: 11:30am-12:30pm on Wednesdays in TSRB and hybrid
  - Anuvab: 12pm-1pm on Thursdays in TSRB and hybrid
  - Dr. Bloch: TBA
- Solutions of HW1 will be released shortly
- Grading of HW1 in progress

Towards orthobases in infinite dimension

The following properties of a countable orthonormal set ${e_{i}}_{i \geq 1}$ are equivalent:

Finite linear combinations of elements in ${e_{i}}_{i \geq 1}$ are dense in $H$ ;
If $v \in H$ and $\forall j \geq 1$ ${⟨ v, e_{j} ⟩}_{} = 0$ then $v = 0$ ;
If $v \in H$ then $\sum_{i = 1}^{n} {⟨ v, e_{i} ⟩}_{} e_{i}$ converges to $v$ (in the norm ${‖ \cdot ‖}_{}$ ) as $n \to \infty$ ;
If $v \in H$ and $\forall k$ $a_{k} ≜ {⟨ v, e_{k} ⟩}_{}$ then ${‖ v ‖}_{}^{2} = \sum_{k \geq 1} {| a_{k} |}^{2}$ .

A space is separable if it contains a countable dense subset.

Separability is the key property to deal with sequences instead of collections

Any separable Hilbert space has an orthonormal basis.

Many useful Hilbert spaces are separable! We won't worry about non-separable Hilbert spaces

Isomorphism with $ℓ_{2}$

Key take away for separable Hilbert spaces
- $x = \sum_{i = 1}^{\infty} {⟨ x, v_{i} ⟩}_{} v_{i}$ is perfectly well defined for an orthonormal basis
- Parseval's identity tell us that ${‖ x ‖}_{}^{2} = \sum_{k \geq 1} {| {⟨ x, v_{k} ⟩}_{} |}^{2}$ .
- We don't need to even worry about the nature of $H$ and only think about coefficients ${⟨ x, v_{i} ⟩}_{}$

Any separable Hilbert space is isomorphic to $ℓ_{2}$ ; the isomorphism preserves the norm and inner product.

Non-orthogonal bases in finite dimension

Let ${v_{i}}_{i = 1}^{n}$ be a linearly independent set in a Hilbert space $H$ of dimension $n$ . Then, for any $x \in H$ , $x = \sum_{i = 1}^{n} α_{i} v_{i}$ for some $α \in R^{n}$ . In addition, there exists $A, B > 0$ such that $A {‖ α ‖}_{2}^{2} \leq {‖ x ‖}_{H}^{2} \leq B {‖ α ‖}_{2}^{2}$

Remarks
- Inequality is tight on both sides
- For orthobases, $A = B = 1$
Interpretation:
- The values of $A$ and $B$ govern the stability of the representation

Dual basis in finite dimension

Recall from orthobases:
- Perfectly stable representation $A = B = 1$
- Efficient computation of representations: $α_{i} = {⟨ x, v_{i} ⟩}_{}$

For any $x \in H$ with basis ${v_{i}}_{i = 1}^{n}$ we have $x = \sum_{i = 1}^{n} α_{i} v_{i} with α = G^{- 1} [\begin{matrix} {⟨ x, v_{1} ⟩}_{} \\ {⟨ x, v_{2} ⟩}_{} \\ ⋮ \\ {⟨ x, v_{n} ⟩}_{} \end{matrix}]$ There also exists a basis ${{\tilde{v}}_{i}}_{i = 1}^{n}$ such that $α_{i} = {⟨ x, {\tilde{v}}_{i} ⟩}_{}$

Non-orthogonal bases in infinite dimension

${v_{i}}_{i = 1}^{\infty}$ is a Riesz basis for Hilbert space $H$ if $cl (span ({v_{i}}_{i = 1}^{\infty})) = H$ and there exists $A, B > 0$ such that $A \sum_{i = 1}^{\infty} α_{i}^{2} \leq {‖ \sum_{i = 1}^{n} α_{i} v_{i} ‖}_{H}^{2} \leq B \sum_{i = 1}^{\infty} α_{i}^{2}$ uniformly for all sequences ${α_{i}}_{i \geq 1}$ with $\sum_{i \geq 1} α_{i}^{2} < \infty$ .

In infinite dimension, the existence of $A, B > 0$ is not automatic.

Dual basis in infinite dimension

Computing expansion on Riesz basis not as simple in infinite dimension: Gram matrix is "infinite"
The Gramian is a linear operator $G : ℓ_{2} (Z) \to ℓ_{2} (Z) : x \mapsto y with [G (x)]_{n} ≜ y_{n} = \sum_{ℓ = - \infty}^{\infty} {⟨ v_{ℓ}, v_{n} ⟩}_{} x_{ℓ}$
Fact: there exists another linear operator $H : ℓ_{2} (Z) \to ℓ_{2} (Z)$ such that $H (G (x)) = x$ We can replicate what we did in finite dimension!

Next time

Next class: Wednesday September 11, 2024
- We will talk about solving regression problems
- This will highlight why linear algebra concepts are relevant for machine learning
To be effectively prepared for next class, you should:
1. Go over today's slides and read associated lecture notes
2. Work on Homework 2 (due date: Friday September 13, 2024)
Optional
- Export slides for next lecture as PDF (be on the lookout for an announcement when they're ready)