Statistical Learning Theory A The Singular Value Decomposition C Convexity

Appendix B Function Spaces

These notes give a quick overview of a few linear algebra concepts that go beyond $\mathbb{R}^{d}$ . For a more thorough introduction, the book of [DFO20] is focused towards ML, that of [AXL25] is meant as a second course in linear algebra from a more mathematical viewpoint, and that of [ROM07] is a comprehensive graduate-level reference book.

B.1 Vector spaces

You should already be familiar with $\mathbb{R}^{d}$ . You might not be familiar yet with more general notions of vector spaces, which abstract important pieces of the structure of $\mathbb{R}^{d}$ to let us treat things other than Euclidean vectors in a similar way.

While the definitions can be made more general, we’re only going to deal with real vector spaces.

Definition B.1.

A real vector space is a nonempty set $V$ along with the operations of vector addition, denoted $v+w\in V$ for any $v,w\in V$ , and scalar multiplication, denoted $av\in V$ for any $v\in V$ and $a\in\mathbb{R}$ , satisfying the following requirements:

•

Vector addition is associative: for all $u,v,w\in V$ , $u+(v+w)=(u+v)+w$ .
•
Vector addition is commutative: for all $v,w\in V$ , $v+w=w+v$ .
•

Vector addition has an identity: there is some zero vector $0\in V$ such that for all $v\in V$ , $v+0=v$ .
•

Vector addition has inverses: for each $v\in V$ , there is some $-v\in V$ such that $v+(-v)=0$ .
•
Compatibility of scalar multiplication: for all $a,b\in\mathbb{R}$ and $v\in V$ , $a(bv)=(ab)v$ .
•
Identity of scalar multiplication: for all $v\in V$ , $(1)v=v$ .
•
Vector addition distributes: for all $a\in\mathbb{R}$ and $v,w\in V$ , $a(v+w)=av+aw$ .
•
Scalar addition distributes: for all $a,b\in\mathbb{R}$ and $v\in V$ , $(a+b)v=av+bv$ .

The axioms imply many things you’d expect, like that the additive identity is unique, that additive inverses are unique and given by

(-1)v

, that

0v=0

(where the left-hand

0

is in

\mathbb{R}

and the right-hand is the zero vector in

V

), etc.

These eight axioms are all things that you probably use all the time without thinking about it for $\mathbb{R}^{d}$ . Given anything with those structures, though, we can do a lot that we do with $\mathbb{R}^{d}$ . For example, we often use function spaces. Here $\mathcal{F}$ is some set of functions $\mathcal{X}\to\mathcal{Y}$ , and we can treat them as vectors if we define a way to add two functions and to do scalar multiplication, which we will always define as follows: if $f,g\in\mathcal{F}$ and $a\in\mathbb{R}$ ,

f+g=(x\mapsto f(x)+g(x))\qquad af=(x\mapsto af(x)).

These definitions make sense if:

•
$\mathcal{Y}$ is itself a vector space, so that adding $f(x)+g(x)$ and multiplying $af(x)$ make sense. This could be just $\mathbb{R}$ , or could be more general: $\mathbb{R}^{d}$ would be common, but it could be itself a function space….
•

The set $\mathcal{F}$ needs to be “closed” under both of these operations, so that $f+g$ and $a f$ are also in $\mathcal{F}$ . (This is the $v+w\in V$ and $av\in V$ part of the definition.)

So, one reasonable function space could be where $\mathcal{X}=\mathbb{R}=\mathcal{Y}$ and $\mathcal{F}$ is the set of quadratic functions (where here linear or constant functions also count as quadratic). Adding two quadratics gets you another quadratic, as does scaling by a constant. More generally, $\mathcal{F}$ could be the space of polynomials with degree at most $k$ . Much more generally, we can also think about spaces like “all continuous functions” or “all infinitely-differentiable functions.”

Definition B.2.

A subspace $U$ of a real vector space $V$ is a nonempty subset $U\subseteq V$ such that for all $v,w\in U$ and $a\in\mathbb{R}$ , $v+w\in U$ and $av\in U$ .

The sum of two subspaces $U, W$ of $V$ , given by $U+W=\{u+w:u\in U,w\in W\}$ , is itself a subspace, and is the smallest subspace containing both $U$ and $W$ . The sum of finitely many subspaces is analogous: $\sum_{i}U_{i}=\{\sum_{i}u_{i}:\forall i,\;u_{i}\in U_{i}\}$ .

Note that this implies that any subspace must contain

0

(why?), and that for any

V

both

\{0\}

and

V

are subspaces of

V

Linear functions are a subspace of the space of quadratic functions. More generally, the space of polynomials with degree at most $k$ is a subspace of the space of polynomials with degree at most $K$ for any $k\leq K$ , and is also a subspace of the space of all continuous functions.

Something like $\{f\in\mathcal{F}:\lvert f(0)\rvert\leq 1\}$ , however, is not a subspace unless $f(0)=0$ for all $f\in\mathcal{F}$ , since a subspace containing $f$ must also contain e.g. $\frac{3}{f(0)}f$ .

Definition B.3.

The span of a set of vectors

S\subseteq V

is the subspace

\operatorname{span}(S)=\{a_{1}v_{1}+\dots+a_{m}v_{m}:m\in\mathbb{N},a_{1},% \dots,a_{m}\in\mathbb{R},v_{1},\dots,v_{m}\in S\}.

We define

\operatorname{span}(\{\})=\{0\}

It can be seen that

\operatorname{span}(S)

is the intersection of all subspaces of

V

containing

S

Definition B.4.

A nonempty set of vectors $S\subseteq V$ is linearly independent if for any distinct $v_{1},\dots,v_{m}\in S$ ,

a_{1}v_{1}+\dots+a_{m}v_{m}=0\text{ implies }a_{1}=\cdots=a_{m}=0.

The set

\{\}

is defined to be linearly independent. A set which is not linearly independent is linearly dependent.

A basis for $V$ is a linearly independent set which spans $V$ .

The dimension of a vector space $V$ , $\dim V$ , is the size of the smallest basis for $V$ ; this may be a natural number, or may be infinite.

Every vector space has a basis, and thus has a unique, well-defined dimension. Note that $\dim\{0\}=0$ , while any other vector space has dimension at least one. It can also be seen that if $\lvert S\rvert>\dim V$ , then $S$ is linearly dependent; thus all bases are of the same size, $\dim V$ .

B.1.1 Linear maps

Definition B.5.

Let $V$ and $W$ be real vector spaces. ¹¹1Some authors use “linear operator” only for $V\to V$ maps. A linear map or linear operator is a function $T:V\to W$ satisfying that for all $v,v^{\prime}\in V$ and $a\in\mathbb{R}$ ,

T(av+v^{\prime})=aT(v)+T(v^{\prime}).

We also frequently write

T v

rather than

T(v)

If $\mathcal{F}$ is the function space of infinitely differentiable functions $\mathbb{R}\to\mathbb{R}$ , then the derivative operator $Df=(x\mapsto f^{\prime}(x))$ is a linear operator $\mathcal{F}\to\mathcal{F}$ . If $\mathcal{F}_{k}$ is the space of functions with $k$ derivatives, then $D:\mathcal{F}_{k}\to\mathcal{F}_{k-1}$ is a linear map.

Definition B.6.

A bijective linear map

T:V\to W

is called an isomorphism. If an isomorphism exists, we say that

V

and

W

are isomorphic.

It turns out that two vector spaces are isomorphic if and only if they have the same dimension. Note that not all infinite-dimensional vector spaces are isomorphic, because they could have different infinite dimensions, e.g. having a countable or an uncountable basis; we won’t need to worry about this.

The space of all linear maps from $V$ to $W$ is itself a vector space.

Definition B.7.

Let $T:V\to W$ be linear. ²²2The null space is also called the “kernel” of $T$ . “Kernel” refers to about ten thousand different concepts in ML and adjacent areas, so please don’t use this terminology if you can help it! The null space of $T$ is $\operatorname{null}(T)=\{v\in V:Tv=0\}$ , a subspace of $V$ ; the image of $T$ is $\operatorname{image}(T)=\{Tv:v\in V\}$ , a subspace of $W$ . The rank of $T$ is $\operatorname{rank}(T)=\dim\operatorname{image}(T)$ .

The celebrated rank-nullity theorem says that, when

\dim V<\infty

\operatorname{rank}(T)+\dim\operatorname{null}(T)=\dim V

B.2 Normed spaces

One thing that our vector spaces don’t yet have is a notion of magnitude. In

\mathbb{R}^{d}

, we usually use the Euclidean norm

\lVert x\rVert=\sqrt{\sum_{i}x_{i}^{2}}

, but you’ve also probably seen at least

\lVert x\rVert_{1}=\sum_{i}\lvert x_{i}\rvert

and

\lVert x\rVert_{\infty}=\max_{i}\lvert x_{i}\rvert

. What properties do these have in common?

Definition B.8.

A real normed vector space is a real vector space

V

with a norm: a function

V\to\mathbb{R}

, written

\lVert v\rVert

, satisfying

•

Non-negativity: for all $v\in V$ , $\lVert v\rVert\geq 0$ .
•
Positive-definiteness: for every $v\in V$ , $\lVert v\rVert=0$ if and only if $v=0$ .
•

Absolute homogeneity: for every $a\in\mathbb{R}$ and $v\in V$ , $\lVert av\rVert=\lvert a\rvert\,\lVert v\rVert$ .
•
Sub-additivity / triangle inequality: for every $v,w\in V$ , $\lVert v+w\rVert\leq\lVert v\rVert+\lVert w\rVert$ .

The norm of a normed vector space induces the metric

\rho(v,w)=\lVert v-w\rVert

; the properties of a metric (definition 4.1) are easy to see from the properties of a norm.

Definition B.9.

Consider a sequence

x_{1},x_{2},\dots

in a metric space

\mathcal{X}

This sequence has a limit $x_{\infty}\in\mathcal{X}$ if for every $\varepsilon>0$ , there exists a positive integer $N$ such that for all $n>N$ , $\rho(x_{n},x_{\infty})<\varepsilon$ .

This sequence is called Cauchy if, for every

\varepsilon>0

, there exists a positive integer

N

such that for all

m,n>N

\rho(x_{m},x_{n})<\varepsilon

The metric space

\mathcal{X}

is called complete if all Cauchy sequences in

\mathcal{X}

have limits in

\mathcal{X}

Definition B.10.

A real Banach space is a real normed vector space whose norm induces a complete metric space.

You can check that, for example, the space of all bounded continuous functions $\mathcal{X}\to\mathbb{R}$ , with the norm $\lVert f\rVert_{\infty}=\sup_{x\in\mathcal{X}}\lvert f(x)\rvert$ , is a Banach space.

B.3 Inner product spaces

There’s one other major structure in

\mathbb{R}^{d}

that we don’t have yet: dot products.

Definition B.11.

A real inner product space is a real vector space $V$ together with an inner product, a function $V\times V\to\mathbb{R}$ written $\langle v,w\rangle$ , satisfying

•

Symmetry: for all $v,w\in V$ , $\langle v,w\rangle=\langle w,v\rangle$ .
•
Linearity: for all $u,v,w\in V$ and $a,b\in\mathbb{R}$ , $\langle au+bv,w\rangle=a\langle u,w\rangle+b\langle v,w\rangle$ .
•
Positive-definiteness: if $v\neq 0$ , then $\langle v,v\rangle>0$ .

An inner product space is also a normed vector space with

\lVert v\rVert=\sqrt{\langle v,v\rangle}

, and hence a metric space with

\rho(v,w)=\lVert v-w\rVert=\sqrt{\langle v-w,v-w\rangle}

Definition B.12.

A real Hilbert space is a real inner product space whose induced metric space is complete.

A common example of a Hilbert space onfunctions

\mathcal{X}\to\mathbb{R}

(…almost …) is

L_{2}

, which has the usual vector space operations and the inner product

\langle f,g\rangle_{L_{2}}=\int f(x)g(x)\,\mathrm{d}x.

A function

f

L_{2}

\lVert f\rVert_{L_{2}}<\infty

, i.e. it’s square-integrable. A slight variant is

L_{2}(P)

, where

P

is a probability distribution on

\mathcal{X}

; this has inner product

\langle f,g\rangle_{L_{2}(P)}=\operatorname*{\mathbb{E}}_{X\sim P}f(X)g(X).

The reason this is “almost” a function space is that we have to treat some functions that are slightly different, but equal almost everywhere, as the same. If

P

is standard normal, and

\tilde{f}(x)=\begin{cases}f(x)&x\neq 0\\ 100&x=0,\end{cases}

then

\lVert f-\tilde{f}\rVert=0

, all inner products are the same, etc. So we usually think of these as being spaces of equivalence classes of functions, rather than of functions proper.

The other major kind of function space is reproducing kernel Hilbert spaces (chapter 14).