Mathematical Foundations of Machine Learning

Prof. Matthieu Bloch

Wednesday September 4, 2024 (v1.2)

Last time

Image
(c) xkcd
  • Last class: Wednesday August 28, 2024
    • We talked about the notion of completeness
    • We talked about the orthogonal projection theorem
    • We proved it in infinite dimension
    • We explicitly used the notion of completeness in our proof
  • To be effectively prepared for today's class, you should have:
    1. Gone over last week's slides and read associated lecture notes
    2. Turned in Homework 1
    3. Started looking at Homework 2

Computing approximations

  • The orthogonality principle gives us a procedure for computing the closest point

Let \(\calH\) be a Hilbert space, \(\calT\) be a subspace of \(\calH\) with dimension \(n\), and \(x\in\calH\). Let \(\set{e_i}_{i=1}^n\) be a basis for \(\calT\). Then the projection \(\hat{x}\) of \(x\) onto \(\calT\) is \[ \hat{x} = \sum_{i=1}^n\alpha_i e_i \] where \(\bfalpha\eqdef\mat{c}{\alpha_1&\cdots&\alpha_n}^\intercal\) is the solution of \(\bfG\bfalpha=\bfb\) with \(\bfG\) the Gram matrix of the basis and \(\bfb\) the coordinates of \(x\) on the basis.

Orthobases

A collection of vectors \(\set{v_i}_{i=1}^n\) in a finite dimensional Hilbert space \(\calH\) is an orthobasis if

  1. \(\text{span}(\set{v_i}_{i=1}^n)=\calH\);
  2. \(\forall i\neq j\in\intseq{1}{n}\,v_i\perp v_j\);
  3. \(\forall i\in\intseq{1}{n} \,\norm{v_i}=1\).
  • Notes
    • If the last condition is not met, this is just called an orthogonal basis
    • Orthobases are useful because we can write \(x=\sum_{i=1}^n\dotp{x}{v_i}v_i\) (what happens in a non-orthonormal basis?)
  • We would like to extend this idea to infinite dimension and happily write \(x=\sum_{i=1}^\infty\dotp{x}{v_i}v_i\)
    • We have to be a bit careful
    • With a little bit of machinery, this works: separability + completeness

What we know works in infinite dimension

  • Consider a Hilbert space \(\calH\). The following notions we encountered work without problems:
    • Norm induced by inner product
    • Cauchy-Schwartz inequality
    • Orthogonality + Pythagorean theorem + projection theorem

A collection of vectors \(\set{v_i}_{i\in\calI}\) in a Hilbert space \(\calV\) is orthonormal if

  1. \(\forall i\neq j\in\intseq{1}{n}\,v_i\perp v_j\);
  2. \(\forall i\in\intseq{1}{n} \,\norm{v_i}=1\).
  • Notes
    • We do not even require \(\calI\) to be countable at this stage.
    • We are not saying anything about this being a basis

Towards orthobases in infinite dimension

Let \(c\in\calH\) and let \(\set{x_n}_{n\geq 1}\) be a sequence of vectors in \(\calH\) that converges to \(x^*\in\calH\). Then \(\lim_{n\to\infty}\dotp{x_n}{c} = \dotp{x^*}{c}\)

Let \(\set{v_n}_{n\geq 1}\) be a sequence of orthonormal vectors in \(\calH\). Then for any \(x\in\calH\), \(\sum_{n=1}^\infty\abs{\dotp{x}{v_n}}^2\leq\norm{x}^2\).

The following properties of a countable orthonormal set \(\set{e_i}_{i\geq 1}\) are equivalent:

  1. Finite linear combinations of elements in \(\set{e_i}_{i\geq 1}\) are dense in \(\calH\);
  2. If \(v\in\calH\) and \(\forall j\geq 1\) \(\dotp{v}{e_j}=0\) then \(v=0\);
  3. If \(v\in\calH\) then \(\sum_{i=1}^n\dotp{v}{e_i}e_i\) converges to \(v\) (in the norm \(\norm{\cdot}\)) as \(n\to\infty\);
  4. If \(v\in\calH\) and \(\forall k\) \(a_k\eqdef \dotp{v}{e_k}\) then \(\norm{v}^2=\sum_{k\geq 1}\abs{a_k}^2\).
  • This does not say anything about the existence of such a nice orthornormal set

Separable space

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
  • Key take away for separable Hilbert spaces
    • \(x=\sum_{i=1}^\infty\dotp{x}{v_i}v_i\) is perfectly well defined for an orthonormal basis
    • Parseval's identity tell us that \(\norm{x}^2=\sum_{k\geq 1}\abs{\dotp{x}{v_k}}^2\).
    • We don't need to even worry about the nature of \(\calH\) and only think about coefficients \(\dotp{x}{v_i}\)

Any separable Hilbert space is isomorphic to \(\ell_2\)

Next time

  • Next class: Monday September 9, 2024
    • We will talk about orthobases
    • We will prove a fundamental result called Parseval's theorem
  • 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)