ece7750-2024-08-28-linear-approximaton.tmpv82cHb

Last time

Last class: Monday August 26, 2024
- We talked about Hilbert spaces, inner product, completeness
To be effectively prepared for today's class, you should have:
1. Gone over the previous slides and read associated lecture notes
2. Made sure you have access to Canvas, Piazza, Gradescope
3. Spent a bit of time on Homework 1
  - due date: Tuesday September 3, 2024 (updated to account for Labor day)
  - It's a fast turnover but you'll have more time for future homework
  - Work on Problem 2 last

Infinite dimensions

In infinite dimensions, things are a little bit tricky. What does the following mean? $x (t) = \sum_{n = 1}^{\infty} α_{n} ψ_{n} (t)$
We need to define a notion of convergence, e.g., $lim_{N \to \infty} {‖ x (t) - \sum_{n = 1}^{N} α_{n} ψ_{n} (t) ‖}_{} = 0$
Problems can still arise if "points are missing"
We avoid this by introducing the notion of completeness

Hilbert space

A sequence ${x_{n}}_{n \geq 0}$ in $V$ is Cauchy if $\forall ϵ > 0$ $\exists N \in N^{*}$ such that $\forall n, m > N$ ${‖ x_{n} - x_{m} ‖}_{} \leq ϵ$

A Hilbert space $H$ is a complete inner product space, i.e., an inner product space in which every Cauchy sequence in $H$ converges to a point in $H$

Intuition: a Hilbert space has no "missing point"

A finite dimensional inner product space is complete (many Hilbert spaces are infinite dimensional!)

We won't worry too much about proving that spaces are complete

A complete normed vector space is a Banach space; a lot of things are still possible without an inner product

Orthogonality principle

Let $H$ be a Hilbert space with inner product ${⟨ \cdot, \cdot ⟩}_{}$ and induced norm ${‖ \cdot ‖}_{}$ ; let $T$ be a subspace of $H$

For $x \in H$ , what is the closest point $\hat{x} \in T$ ? How do we solve $min_{y \in T} {‖ x - y ‖}_{}$ ?

This problem has a unique solution given by the orthogonality principle

Let $X$ be a pre-Hilbert space, $T$ be a subspace of $X$ , and $x \in X$ .

If there exists a vector $m^{*} \in T$ such that $\forall m \in T$ ${‖ x - m^{*} ‖}_{} \leq {‖ x - m ‖}_{}$ , then $m^{*}$ is unique.

$m^{*} \in T$ is a unique minimizer if and only if the error $x - m^{*}$ is orthogonal to $T$ .

This doesn't say that $m^{*}$ exists!

Let $H$ be a Hilbert space, $T$ be a closed subspace of $X$ , and $x \in X$ .

There exists a unique vector $m^{*} \in T$ such that $\forall m \in T$ ${‖ x - m^{*} ‖}_{} \leq {‖ x - m ‖}_{}$ .

Computing approximations

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

Let $H$ be a Hilbert space, $T$ be a subspace of $H$ with dimension $n$ , and $x \in H$ . Let ${e_{i}}_{i = 1}^{n}$ be a basis for $T$ . Then the projection $\hat{x}$ of $x$ onto $T$ is $\hat{x} = \sum_{i = 1}^{n} α_{i} e_{i}$ where $α ≜ {[\begin{matrix} α_{1} & \dots & α_{n} \end{matrix}]}^{⊺}$ is the solution of $G α = b$ with $G$ the Grammiam matrix of the basis and $b$ the coordinates of $x$ on the basis.

Next time

Next class: Wednesday September 4, 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 1 (due date: Tuesday September 03, 2024)
Optional
- Export slides for next lecture as PDF (be on the lookout for an announcement when they're ready)

Mathematical Foundations of Machine Learning