ece7750-2024-08-26-inner-product-and-norms.tmpnq04Ik

Logistics

ECE 7750 in numbers
- 138 students (including Q and QSZ sections)
- 29 lectures left
- 8 Homework assignments left
- 2 GTAs who will have a lot of grading to do
- 1 Instructor who is looking forward to a fun semester
Action items
- Submit your Homework 0
  - due date: Monday August 26, 2024
  - hard cut-off on Wednesday August 28, 2024
- Please complete the Verification of Participation poll on Piazza

Last time

Last class: Wednesday August 21, 2024
- We talked about vector spaces
- We talked about how to approach mathematical statements and proofs
  - Take-away 1: inspect statements and make sure you appreciate details
  - Take-away 2: doodle the statements by using special cases to comfort your understanding

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 time on Homework 0 (due date: Monday August 26, 2024)

Linear independence

Let ${v_{i}}_{i = 1}^{n}$ be a set of vectors in a vector space $V$

${v_{i}}_{i = 1}^{n}$ is linearly independent (or the vectors ${v_{i}}_{i = 1}^{n}$ are linearly independent ) if (and only if) $\sum_{i = 1}^{n} a_{i} v_{i} = 0 \Rightarrow \forall i \in [1; n] a_{i} = 0$ Otherwise the set is (or the vectors are) linearly dependent.

$V ≜ R^{3} v_{1} = {[\begin{array}{ccc} 2 & 1 & 0 \end{array}]}^{⊺}, v_{2} = {[\begin{array}{ccc} 1 & 1 & 0 \end{array}]}^{⊺}, v_{3} = {[\begin{array}{ccc} 1 & 2 & 0 \end{array}]}^{⊺}$

$V ≜ C ([0; 1]) v_{1} = \cos (2 π t), v_{2} = \sin (2 π t), v_{3} = 2 \cos (2 π t + \frac{π}{3})$

Any finite set of linearly dependent vectors contains a subset of linearly independent vectors with the same span.

Bases

A basis of vector subspace $W$ of a vector space $V$ is a countable set of vectors $B$ such that:

$span (B) = W$
$B$ is linearly independent

If a vector space $V \neq {0}$ has a finite basis with $n \in N^{*}$ elements, $n$ is called the dimension of $V$ , denoted $\dim V$ . If the basis has an infinite number of elements, the dimension is infinite

Any two bases for the same finite dimensional vector space contain the same number of elements.

You should be somewhat familiar with bases (at least in $R^{n}$ ):
- the representation of a vector on a basis is unique
- every subspace has a basis
- having a basis reduces the operations on vectors to operations on their components
Things sort of work in infinite dimensions, but we have to be bit more careful

Norm

The properties of vector space seen thus far provide an algebraic structure
We are missing a topological structure to measure length and distance

A norm on a vector space $V$ over $R$ is a function ${‖ \cdot ‖}_{} : V \to R$ that satisfies:

Positive definiteness: $\forall x \in V$ ${‖ x ‖}_{} \geq 0$ with equality iff $x = 0$
Homogeneity: $\forall x \in V$ $\forall α \in R$ ${‖ α x ‖}_{} = | α | {‖ x ‖}_{}$
Subadditivity: $\forall x, y \in V$ ${‖ x + y ‖}_{} \leq {‖ x ‖}_{} + {‖ y ‖}_{}$

${‖ x ‖}_{}$ measures a length, ${‖ x - y ‖}_{}$ measures a distance

$x \in R^{d} {‖ x ‖}_{0} ≜ | {i : x_{i} \neq 0} | {‖ x ‖}_{1} ≜ \sum_{i = 1}^{d} | x_{i} | {‖ x ‖}_{2} ≜ \sqrt{\sum_{i = 1}^{d} x_{i}^{2}}$

Inner product

In addition to a topological and algebraic strucure, what if we want to do geometry?

An inner product space over $R$ is a vector space $V$ equipped with a positive definite symmetric bilinear form ${⟨ \cdot, \cdot ⟩}_{} : V \times V \to R$ called an inner product

An inner product space is also called a pre-Hilbert space

An inner product satisfies $\forall x, y \in V$ ${⟨ x, y ⟩}_{}^{2} \leq {⟨ x, x ⟩}_{} {⟨ y, y ⟩}_{}$

Equality holds if and only if $x$ and $y$ are colinear, i.e., $\exists α \in R$ such that $y = α x$

Unless stated otherwise, we will only deal with vector spaces on $R$
- Things don't change too much on $C$ but one should be a bit more careful
- One has to deal with a conjugate

Induced norm

In an inner product space, an inner product induces a norm ${‖ x ‖}_{} ≜ \sqrt{{⟨ x, x ⟩}_{}}$

A norm ${‖ \cdot ‖}_{}$ induces an inner product on $V$ iff $\forall x, y \in V$ ${‖ x ‖}_{}^{2} + {‖ y ‖}_{}^{2} = \frac{1}{2} ({‖ x + y ‖}_{}^{2} + {‖ x - y ‖}_{}^{2})$

If this is the case, the inner product is given by the polarization identity ${⟨ x, y ⟩}_{} = \frac{1}{2} ({‖ x ‖}_{}^{2} + {‖ y ‖}_{}^{2} - {‖ x - y ‖}_{}^{2})$

Orthogonality

In the following $V$ is always an inner product space with induced norm ${‖ \cdot ‖}_{}$

The angle between two non-zero vectors $x, y \in V$ is $\cos θ ≜ \frac{{⟨ x, y ⟩}_{}}{{‖ x ‖}_{} {‖ y ‖}_{}}$

Two vectors $x, y \in V$ are orthogonal if ${⟨ x, y ⟩}_{} = 0$ . We write $x ⊥ y$ for simplicity.

A vector $x \in V$ is orthogonal to a set $S \subset V$ if $\forall s \in S$ ${⟨ x, s ⟩}_{} = 0$ . We write $x ⊥ S$ for simplicity.

If $x ⊥ y$ then ${‖ x + y ‖}_{}^{2} = {‖ x ‖}_{}^{2} + {‖ y ‖}_{}^{2}$

Let $W$ be a vector subspace of $V$ . The orthogonal subspace of $W$ is $W^{⊥} ≜ {v \in V : \forall w \in W {⟨ w, v ⟩}_{} = 0} .$

$W^{⊥}$ is a subspace of $V$ and $(W^{⊥})^{⊥} = W$

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

Next time

Next class: Wednesday August 28, 2024
- We will talk about linear approximations
- We will prove a very fundamental result called the orthogonality principle
To be effectively prepared for next class, you should:
1. Go over today's slides and read associated lecture notes
2. Make sure you have access to Canvas, Piazza, Gradescope
3. Work on Homework 1 (due date: Monday September 2, 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