Signal Spaces: Linear, Banach and Hilbert Spaces, and Basis Expansions

In this chapter, we present a general review of signal spaces. These spaces form the mathematical foundation for everything that follows in the course: systems, transforms, stability, and control all rely on understanding the structure of the spaces in which signals live.

---

Normed Linear (Vector) Spaces and Metric Spaces

Linear Spaces

Intuitively, a linear space is a set where you can add elements together and scale them, and these operations behave the way you would expect. This is the most basic algebraic structure we need to talk about "signals" in a mathematically precise way.

In particular, the null element $\underline{0}$ is an element of every subspace. For $M$, $N$ two subspaces of a vector space $\mathbb{X}$, $M \cap N$ is also a subspace of $\mathbb{X}$.

Normed Linear Spaces

The norm gives us a way to measure the "size" of a signal. Different norms measure size in different ways -- for instance, the maximum value of a signal vs. its total energy. The choice of norm profoundly affects which signals are "small" or "large."

Let for two linear spaces $\mathbb{X}$, $\mathbb{Y}$, $\Gamma(\mathbb{X}; \mathbb{Y})$ denote the set of all maps $\gamma : \mathbb{X} \to \mathbb{Y}$ such that for all $x \in \mathbb{X}$, $\gamma(x) \in \mathbb{Y}$.

To show that $l_p$ defined above is a normed linear space, we need to show that $\|x + y\|_p \leq \|x\|_p + \|y\|_p$.

See Exercise, which also studies a proof of Holder's Inequality, that is critically used in the proof of Minkowski's inequality.

Transformations and Continuity

For some applications, sequential continuity may be more convenient to work with as one may not need to quantify $(\epsilon, \delta)$ pairs to verify continuity.

Metric Spaces

A normed linear space is also a metric space, with metric $d(x, y) = \|x - y\|$. Many spaces of functions that we encounter are not linear spaces. For such spaces the concept of metric, defined above, provides an appropriate generalization of the notion of norm studied earlier.

Banach Spaces

An important observation on Cauchy sequences is that every converging sequence is Cauchy, however, not all Cauchy sequences are convergent: This is because the limit might not live in the original space where the sequence elements take values from. This motivates the property of completeness.

Banach spaces are important for many applications in engineering and applied mathematics: In many mathematical applications (such as existence of and numerical methods for solutions to differential equations), machine learning problems (such as iterative updates of data driven dynamics), stochastic analysis or optimization problems (for which a sequence of approximating solutions may be obtained for example via dynamic programming methods), sometimes we would like to know whether a given sequence converges, without necessarily knowing what the limit of the sequence may be. Banach spaces allow us to use Cauchy sequence arguments to ensure the existence of limits and some of their properties.

An example is the following: consider the solutions to the $Ax = b$ for $A$ a square matrix and $b$ a vector. One can identify conditions on an iteration of the form $x_{k+1} = (I - A)x_k + b$ to form a Cauchy sequence and converge to a solution through the contraction principle. As noted above, existence of solutions to ordinary differential equations also follow from Cauchy sequence arguments.

A subset of a Banach space $X$ is complete if and only if it is closed. If the set is closed, every Cauchy sequence in this set has a limit in $X$ and this limit should be a member of this set, hence the set is complete. If it is not closed, one can provide a counterexample sequence which does not converge to a point in the subset.

The real space $\mathbb{R}$ with the usual distance $d(x, y) = |x - y|$ is a complete space.

This theorem illustrates a crucial point: the same set of functions can be complete or incomplete depending on the norm. The supremum norm is "strong enough" to prevent discontinuous limits, while the $L_1$ norm is not.

---

Hilbert Spaces

Thus, corresponding to each pair $(x, y) \in X \times X$ the inner product $\langle x, y \rangle$ is a scalar. The inner product gives us a notion of "angle" between signals and allows us to define orthogonality -- concepts that are essential for signal decomposition and optimal approximation.

The Cauchy-Schwarz inequality is one of the most important inequalities in all of mathematics. It tells us that the inner product of two signals is bounded by the product of their norms.

In a pre-Hilbert space, the inner-product defines a norm: $\|x\| = \sqrt{\langle x, x \rangle}$

The proof for this result requires one to show that $\sqrt{\langle x, x \rangle}$ satisfies the triangle inequality, that is

$\|x + y\| \leq \|x\| + \|y\|,$

which can be proven by an application of the Cauchy-Schwarz inequality.

In a given problem or application, the inner-product is to be defined. The inner product, in the special case of $\mathbb{R}^N$, is typically the usual inner vector product; hence $\mathbb{R}^N$ with the usual inner-product is a pre-Hilbert space.

Hence, a Hilbert space is a Banach space, endowed with an inner product, which induces its norm. For example, if we define $C([0, 1]; \mathbb{R})$ as a pre-Hilbert space with the inner-product $\langle x, y \rangle = \int_0^1 x(t)y(t)\,dt$, this would not be a Hilbert space, since this would not be a complete space.

The space $l_2(\mathbb{Z}_+; \mathbb{R})$ is a Hilbert space with $\langle x, y \rangle = \sum_{n \in \mathbb{Z}_+} x(n)y(n)$ for $x, y \in l_2(\mathbb{Z}_+; \mathbb{R})$. Furthermore, $\|x\| = \sqrt{\langle x, x \rangle}$ defines a norm in $l_2(\mathbb{Z}_+; \mathbb{R})$.

Likewise, the space $L_2(\mathbb{R}_+; \mathbb{R})$ is a Hilbert space with $\langle x, y \rangle = \int_{t \in \mathbb{R}_+} x(t)y(t)\,dt$ for $x, y \in L_2(\mathbb{R}_+; \mathbb{R})$ and its norm is $\|x\| = \sqrt{\langle x, x \rangle}$.

Why are we interested in Hilbert Spaces?

Hilbert spaces have several very useful properties:

1. Hilbert spaces allow us to have a geometric insight on a set of signals via the inner-product, orthogonality, and basis expansions.
2. If a Hilbert space is separable (to be defined shortly), there exists a countably (or sometimes only finitely) many sequence of orthonormal vectors which can be used as basis to represent all the members in this space. This is used in many areas of applied mathematics and engineering, such as Fourier expansions among many others.
3. A Hilbert space formulation allows us to develop approximations of signals using a finite number of basis signals.
4. Also related to the item above, we can state a Projection Theorem which certifies optimality in a wide variety of applications. This geometric insight carries over to more general optimization problems in spaces which are not Hilbert (via duality analysis, to be discussed later).

Orthogonality and the Projection Theorem

By the Pythagorean theorem, for $x, y$ orthogonal, we have that $\|x + y\|^2 = \|x\|^2 + \|y\|^2$.

A set $A \subset X$ is closed if $A$ contains the limit of any converging sequence taking values from $A$.

The Projection Theorem is one of the most powerful results in Hilbert space theory. It says that the best approximation to a signal from a subspace is obtained by "projecting" orthogonally onto that subspace -- the error is perpendicular to the subspace. This has direct applications in optimal filtering, least squares estimation, and signal compression.

---

Approximations and Signal Expansions

Orthogonality

The Gram-Schmidt orthogonalization procedure can be invoked to generate a set of orthonormal sequences. This procedure states that given a sequence $\{x_i\}$ of linearly independent vectors, there exists an orthonormal sequence of vectors $\{e_i\}$ such that for every $x_k, \alpha_k, 1 \leq k \leq n$, there exists $\beta_k, 1 \leq k \leq n$ with

$\sum_{k=1}^{n} \alpha_k x_k = \sum_{k=1}^{n} \beta_k e_k,$

that is, the linear span of $\{x_k, 1 \leq k \leq n\}$ is equal to the linear span of $\{e_k, 1 \leq k \leq n\}$ for every $n \in \mathbb{N}$.

Recall that a set of vectors $\{e_i\}$ is linearly dependent if there exists a complex-valued vector $\mathbf{c} = \{c_1, c_2, \ldots, c_N\}$ such that $\sum_i^N c_i e_i = 0$ with at least one coefficient $c_i \neq 0$.

We say that a sequence $\sum_{i=1}^{n} \epsilon_i e_i$ converges to $x$, if for every $\epsilon > 0$ there exists $N \in \mathbb{N}$ such that $\|x - \sum_{i=1}^{n} \epsilon_i e_i\| < \epsilon$, for all $n \geq N$.

This theorem provides the fundamental link between Hilbert space theory and signal representation: a signal can be expanded in an orthonormal basis if and only if the sum of squared coefficients is finite -- which is exactly the condition that the signal has finite energy.

Separable Hilbert Spaces and Countable Expansions

Examples of countable spaces are finite sets, the set $\mathbb{Z}$ of integers, and the set $\mathbb{Q}$ of rational numbers. An example of uncountable sets is the set $\mathbb{R}$ of real numbers.

Cantor's diagonal argument and the triangular enumeration are important steps in proving the theorem above.

Separability states that it suffices to work with a countable set, when a set is uncountable, for computational purposes. Examples of separable sets are $\mathbb{R}$, and the set of continuous and bounded functions on a compact set metrized with the maximum distance between the functions.

The proof above also showed the following result:

This is the fundamental representation theorem for signals in Hilbert spaces. Every signal can be decomposed into a (possibly infinite) sum of orthonormal basis vectors, with coefficients given by inner products. This is the abstract framework underlying Fourier series, wavelet expansions, and many other signal representations.

Separability of $l_2$ and $L_2$ spaces

In view of Theorem, the following result builds on the fact that the sequence of orthonormal vectors

$\left\{e_n, n \in \mathbb{N} : \quad e_n : \mathbb{Z}_+ \to \mathbb{R}, \quad e_n(m) = 1_{\{m = n\}}, \quad m \in \mathbb{Z}_+\right\}$

is a countable complete orthonormal set in $l_2(\mathbb{Z}_+; \mathbb{R})$: Note that for any $h = \{h(1), h(2), \cdots\} \in l_2(\mathbb{Z}_+; \mathbb{R})$, $\langle h, e_n \rangle = h(n)$ and hence for any vector $v \in l_2(\mathbb{Z}_+; \mathbb{R})$

$\langle v, e_n \rangle = 0 \quad \forall n \in \mathbb{Z}_+ \implies \|v\| = 0.$

Next, we will show that $L_2([a, b]; \mathbb{R})$ is separable for $a, b \in \mathbb{R}$. To establish this result, we will review some useful facts.

Two further results:

Signal expansions in $L_2([a, b]; \mathbb{R})$ or $L_2([a, b]; \mathbb{C})$: Fourier, Haar and Polynomial Bases

Fourier Signals as Basis Vectors and Fourier Series

Fourier series is a very important class of orthonormal sequences which are used to represent both discrete-time and continuous-time signals. These will be studied later on in much detail. In particular, we will soon see that in $L_2([0, P]; \mathbb{C})$ the family of complex exponentials

$\left\{e_k : e_k(t) = \frac{1}{\sqrt{P}} e^{i2\pi \frac{k}{P} t}, k \in \mathbb{Z}\right\},$

provides a complete orthonormal sequence.

Accordingly, for any $x \in L_2([0, P]; \mathbb{C})$, we can write

$x = \sum_{k \in \mathbb{Z}} \langle x, e_k \rangle e_k$

or by expanding the inner-product, we have

$x(t) = \sum_{k \in \mathbb{Z}} \left(\int_{\mathbb{R}} x(s) \frac{1}{\sqrt{P}} e^{-i2\pi \frac{k}{P} s}\,ds\right) \frac{1}{\sqrt{P}} e^{i2\pi \frac{k}{P} t}$

where the convergence of the infinite sum is in the $L_2$ sense.

This expansion is precisely the Fourier series expansion of the function $x$ in $L_2([0, P]; \mathbb{C})$. The inner-product $\langle x, e_k \rangle$ defines the Fourier transform.

Legendre Polynomials as Basis Vectors

We have seen, in the context of Theorems 2.3.7 and 2.3.8 (see the proof of 2.3.9), the functions $\{t^k, k \in \mathbb{Z}_+\}$ can be used to construct an orthonormal collection of signals which is complete in $L_2([a, b]; \mathbb{R})$. These complete orthonormal polynomials are called Legendre polynomials.

Haar Functions as Basis Vectors

One further practically very important basis is the class of Haar functions (known as wavelets). Define

$\Psi_{0,0}(x) = \begin{cases} 1, & \text{if } 0 \leq x \leq 1 \\ 0 & \text{else} \end{cases} \qquad \text{}$

and for $n \in \mathbb{Z}_+$, $k \in \{0, 1, 2, \ldots, 2^n - 1\}$,

$\Phi_{n,k}(x) = \begin{cases} 2^{n/2}, & \text{if } k2^{-n} \leq x < (k + 1/2)2^{-n} \\ -2^{n/2}, & \text{if } (k + 1/2)2^{-n} \leq x < (k+1)2^{-n} \\ 0 & \text{else} \end{cases} \qquad \text{}$

The important observation to note here is that, different expansions might be suited for different engineering applications: for instance Haar series are occasionally used in image processing with certain edge behaviours, whereas Fourier expansion is extensively used in speech processing and communications theoretic applications.

Approximations

Approximations allow us to represent data using finitely many vectors. The basis expansions studied above can be used to obtain the best approximation of a signal up to finitely many terms to be used in an approximation: This can be posed as a projection problem, and we have seen that the best approximation is one in which the approximation error is orthogonal to all the vectors used in the approximation (defining an approximation subspace).

---

Exercises

Exercise

(a) The set $C^\infty(\mathbb{R})$, which is the set of all functions from $\mathbb{R}$ to $\mathbb{R}$ that are infinitely differentiable, together with the operations of addition and scalar multiplication defined as follows, is a vector space: For any $f_1, f_2 \in C^\infty(\mathbb{R})$

$(f_1 + f_2)(x) = f_1(x) + f_2(x), \qquad x \in \mathbb{R}$

and for any $\alpha \in \mathbb{R}$ and $f \in C^\infty(\mathbb{R})$

$(\alpha \cdot f)(x) = \alpha f(x), \qquad x \in \mathbb{R}$

(i) Now, consider $\mathcal{P}(\mathbb{R})$ to be the set of all (polynomial) functions that maps $\mathbb{R}$ to $\mathbb{R}$ such that any $f \in \mathcal{P}(\mathbb{R})$ can be written as $f(x) = \sum_{i=0}^{n} a_i x^i$ for some $n \in \mathbb{N}$ with $a_0, a_1, \cdots, a_n \in \mathbb{R}$. Suppose that we define the same addition and scalar multiplication operations as defined above. Is $\mathcal{P}(\mathbb{R})$ a subspace in $C^\infty(\mathbb{R})$?

(ii) Show that the space of all functions in $C^\infty(\mathbb{R})$ which map $\mathbb{R}$ to $\mathbb{R}$ which satisfy $f(10) = 0$ is a vector space with addition and multiplication defined as above.

(b) Consider the set $\mathbb{R}^n$. On $\mathbb{R}^n$, define an addition operation and a scalar multiplication operation as follows:

$(x_1, x_2, \cdots, x_n) + (y_1, y_2, \cdots, y_n) = (x_1 + y_1, x_2 + y_2, \cdots, x_n + y_n)$

$\alpha \cdot (x_1, x_2, \cdots, x_n) = (\alpha x_1, \alpha x_2, \cdots, \alpha x_n)$

Show that, with these operations, $\mathbb{R}^n$ is a vector space.

(c) Consider the set

$\mathbb{W} = \{(x, y) : x \in \mathbb{R}, x \in \mathbb{R}, x > 0, y > 0\}$

On this set, define an addition operation and a scalar multiplication operation as follows:

$(x_1, y_1) + (x_2, y_2) = (x_1 x_2, y_1 y_2)$

$\alpha \cdot (x, y) = (x^\alpha, y^\alpha)$

Show that, with these operations, $\mathbb{W}$ is a vector space. Hint: Consider a bijection between $\mathbb{W}$ and the space $\mathbb{R}^2$ with $\mathbb{W} \ni (x, y) \mapsto (\log(x), \log(y)) \in \mathbb{R}^2$.

Exercise (Holder's and Minkowski's Inequalities)

Let $1 \leq p, q \leq \infty$ with $1/p + 1/q = 1$. Let $x \in l_p(\mathbb{Z}_+)$ and $y \in l_q(\mathbb{Z}_+)$. Then,

$\sum_{i=0}^{\infty} |x_i y_i| \leq \|x\|_p \|y\|_q$

This is known as Holder's inequality. Equality holds if and only if

$\left(\frac{x_i}{\|x\|_p}\right)^{(1/q)} = \left(\frac{y_i}{\|y\|_q}\right)^{(1/p)},$

for each $i \in \mathbb{Z}_+$.

To prove this, perform the following:

(a) Show that for $a \geq 0, b \geq 0, c \in (0, 1)$: $a^c b^{1-c} \leq ca + (1 - c)b$ with equality if and only if $a = b$. To show this, you may consider the function $f(t) = t^c - ct + c - 1$ and see how it behaves for $t \geq 0$ and let $t = a/b$.

(b) Apply the inequality $a^c b^{1-c} \leq ca + (1 - c)b$ to the numbers:

$a = \left(\frac{|x_i|}{\|x\|_p}\right)^p, \quad b = \left(\frac{|y_i|}{\|y\|_q}\right)^q, \quad c = 1/p$

Holder's inequality is useful to prove Minkowski's inequality which states that for $1 < p < \infty$,

$\|x + y\|_p \leq \|x\|_p + \|y\|_p$

This proceeds as follows:

$\sum_{i=1}^{n} |x_i + y_i|^p \leq \sum_{i=1}^{n} |x_i + y_i|^{p-1}|x_i + y_i| \leq \sum_{i=1}^{n} |x_i + y_i|^{p-1}|x_i| + \sum_{i=1}^{n} |x_i + y_i|^{p-1}|y_i|$

$= \left(\sum_{i=1}^{n} |x_i + y_i|^{(p-1)q}\right)^{1/q}\left(\sum_{i=1}^{n} |x_i|^p\right)^{1/p} + \left(\sum_{i=1}^{n} |x_i + y_i|^{(p-1)q}\right)^{1/q}\left(\sum_{i=1}^{n} |y_i|^p\right)^{1/p}$

$= \left(\sum_{i=1}^{n} |x_i + y_i|^p\right)^{1/q}\left(\left(\sum_{i=1}^{n} |x_i|^p\right)^{1/p} + \left(\sum_{i=1}^{n} |y_i|^p\right)^{1/p}\right) \qquad \text{}$

Thus, using that $1 - 1/q = 1/p$,

$\left(\sum_{i=1}^{n} |x_i + y_i|^p\right)^{1/p} \leq \left(\sum_{i=1}^{n} |x_i|^p\right)^{1/p} + \left(\sum_{i=1}^{n} |y_i|^p\right)^{1/p},$

Now, the above holds for every $n$. Taking the limit $n \to \infty$ (first on the right and then on the left), it follows that

$\|x + y\|_p \leq \|x\|_p + \|y\|_p$

which is the desired inequality.

Exercise

Given a normed linear space $(X, \|\cdot\|)$, introduce a map $n : X \times X \to \mathbb{R}$:

$n(x, y) = \frac{\|x - y\|}{1 + \|x - y\|}$

Show that $n(x, y)$ is a metric: That is, it satisfies the triangle inequality:

$n(x, y) \leq n(x, z) + n(z, y), \qquad \forall x, y, z \in X,$

and that $n(x, y) = 0$ iff $x = y$, and finally $n(x, y) = n(y, x)$.

Exercise

Let $\{e_n, n \in \mathbb{N}\}$ be a complete orthonormal sequence in a real Hilbert space $H$. Let $\mathcal{M}$ be a subspace of $H$, spanned by $\{e_k, k \in S\}$, for some finite set $S \subset \mathbb{N}$. That is,

$\mathcal{M} = \{v \in H : \exists \alpha_k \in \mathbb{R}, k \in S,\quad v = \sum_{k \in S} \alpha_k e_k\}$

Let $x \in H$ be given. Find $x^* \in \mathcal{M}$ which is the solution to the following:

$\min_{x_0 \in \mathcal{M}} \|x - x_0\|,$

in terms of $x$, and $\{e_n, n \in \mathbb{N}\}$.

Hint: Any vector in $H$ can be written as $x = \sum_{n \in \mathbb{N}} \langle x, e_n \rangle e_n$.

Exercise

Let $T : L_2(\mathbb{R}_+; \mathbb{R}) \to \mathbb{R}$ be a mapping given by:

$T(f) = \int_1^{\infty} f(t) \frac{1 + t^2}{t^4}\,dt$

Is $T$ continuous at any given $f_0 \in L_2(\mathbb{R}_+; \mathbb{R})$?

Exercise

Consider an inner-product defined by:

$\langle x, y \rangle = \lim_{T \to \infty} \frac{1}{T} \int_{t=0}^{T} x(t) y(t)$

Is the resulting inner-product (pre-Hilbert) space separable?

Exercise

Let $x, y \in f(\mathbb{Z}; \mathbb{R})$; that is, $x, y$ map $\mathbb{Z}$ to $\mathbb{R}$, such that $x = \{\ldots, x_{-2}, x_{-1}, x_0, x_1, x_2, \ldots\}$ and $y = \{\ldots, y_{-2}, y_{-1}, y_0, y_1, y_2, \ldots\}$ and $x_k, y_k \in \mathbb{R}$, for all $k \in \mathbb{Z}$.

For (a)-(c) below, state if the following are true or false with justifications in a few sentences:

(a) $\langle x, y \rangle = \sum_{i \in \mathbb{Z}} i^2 x_i y_i$ is an inner-product.

(b) $\langle x, y \rangle = \sum_{i \in \mathbb{Z}} x_i y_i$ is an inner-product.

(c) $\{x : \|x\|_2^2 < \infty\}$ contains a complete orthonormal sequence, where $\|x\|_2 = \sqrt{\sum_{i \in \mathbb{Z}} |x(i)|^2}$.

Exercise

Let $\mathbb{X}$ be a Hilbert space and $x, y \in \mathbb{X}$. Prove the following:

(a) (Parallelogram Law)

$\|x + y\|^2 + \|x - y\|^2 = 2\|x\|^2 + 2\|y\|^2.$

(b)

$|\langle x, y \rangle| \leq (\|x\|)(\|y\|).$

(c)

$2|\langle x, y \rangle| \leq \|x\|^2 + \|y\|^2.$

Exercise

Let $H$ be a finite dimensional Hilbert space and $\{v_1, v_2\}$ be two linearly independent vectors in $H$.

Let $b_1, b_2 \in \mathbb{R}$. Show that, among all vectors $x \in H$, which satisfies

$\langle x, v_1 \rangle = b_1,$

$\langle x, v_2 \rangle = b_2,$

the vector $x^* \in H$ has the minimum norm if $x^*$ satisfies:

$x^* = \alpha_1 v_1 + \alpha_2 v_2,$

with

$\langle v_1, v_1 \rangle \alpha_1 + \langle v_2, v_1 \rangle \alpha_2 = b_1,$

$\langle v_1, v_2 \rangle \alpha_1 + \langle v_2, v_2 \rangle \alpha_2 = b_2.$

Exercise

Let $H$ be a Hilbert space and $C \subset H$ be a dense subset of $H$. Suppose that any element $h_C$ in $C$ is such that for every $\epsilon > 0$, there exist $n \in \mathbb{N}$ and $\beta_i \in \mathbb{R}, i \in \mathbb{N}$ so that

$\left\|\sum_{i=0}^{n} \beta_i e_i - h_C\right\| \leq \epsilon$

where $\{e_\alpha, \alpha \in \mathbb{N}\}$ is a countable sequence of orthonormal vectors in $H$.

Is it the case that $H$ is separable?

Exercise

Let $x$ be in the real Hilbert space $L_2([0, 1]; \mathbb{R})$ with the inner product

$\langle x, y \rangle = \int_0^1 x(t) y(t)\,dt.$

We would like to express $x$ in terms of the following two signals (which belong to the Haar signal space)

$u_1(t) = 1_{\{t \in [0, 1/2)\}} - 1_{\{t \in [1/2, 1]\}}, \qquad t \in [0, 1]$

$u_2(t) = 1_{\{t \in [0, 1]\}}, \qquad t \in [0, 1]$

such that

$\int_0^1 \left|x(t) - \sum_{i=1}^{2} \alpha_i u_i(t)\right|^2 dt$

is minimized, for $\{\alpha_1, \alpha_2 \in \mathbb{R}\}$.

(a) Using the Gram-Schmidt procedure, obtain two orthonormal vectors $\{e_1(t), e_2(t)\}$ such that these vectors linearly span the same space spanned by $\{u_1(t), u_2(t)\}$.

(b) State the problem as a projection theorem problem by clearly identifying the Hilbert space and the projected subspace.

(c) Let $x(t) = 1_{\{t \in [1/2, 1]\}}$. Find the minimizing $\alpha_1, \alpha_2$ values.

Exercise

Let $C([0, 1]; \mathbb{R})$ denote the normed linear space of continuous functions from $[-1, 1]$ to $\mathbb{R}$ under the supremum norm. We observed earlier that polynomials can be used to approximate any function in this space with arbitrary precision, under the supremum norm (Weierstrass Theorem).

Given this, repeating the arguments we made in class, argue that the family of polynomials $\{1, t, t^2, \cdots\}$ can be used to form a complete orthonormal sequence in $L_2([0, 1]; \mathbb{R})$. This also establishes that $L_2([0, 1]; \mathbb{R})$ is separable.

Exercise

Alice and Bob are approached by a generous company and asked to solve the following problem: The company wishes to store any signal $f$ in $L_2(\mathbb{R}_+; \mathbb{R})$ in a computer with a given error of $\epsilon > 0$, that is for every $f \in L_2(\mathbb{R}_+)$, there exists some signal $h \in H$ such that $\|f - h\|_2 \leq \epsilon$ (thus the error is uniform over all possible signals), where $H$ is the stored family of signals (in the computer's memory).

To achieve this, they encourage Alice or Bob to use a finite or a countable expansion to represent the signal and later store this signal in an arbitrarily large memory. Hence, they allow Alice or Bob to purchase as much memory as they would like for a given error value of $\epsilon$.

Alice turns down the offer and says it is impossible to do that for any $\epsilon$ with a finite memory and argues then she needs infinite memory, which is impossible.

Bob accepts the offer and says he may need a very large, but finite, memory for any given $\epsilon > 0$; thus, the task is possible.

Which one is the accurate assessment?

(a) If you think Alice is right, which further conditions can she impose to make this possible? Why is she right?

(b) If you think Bob is right, can you suggest a method? Why is he right?

Exercise

Prove Theorem using a probability theoretic method. Proceed as follows: The number

$B_{n,f}(t) = \sum_{k=0}^{n} f\left(\frac{k}{n}\right) \binom{n}{k} t^k (1-t)^{n-k}.$

can be expressed as the expectation $E[f_t(\frac{S_n}{n})]$, where $S_n = X_1 + X_2 + \cdots + X_n$, where $X_i$ is an i.i.d. collection of Bernoulli random variables where $X_i = 1$ with probability $t$ and $X_i = 0$ with probability $1 - t$. Here, observe that the sum $S_n$ has a binomial distribution. Thus,

$\sup_{t \in [0,1]} |f(t) - B_{n,f}(t)| = \sup_{t \in [0,1]} |E_t[f(\frac{S_n}{n})] - f(t)|,$

where $E_t$, for each $t$, denotes the expectation with respect to the i.i.d. Bernoulli random variables $X_i$ each with $P(X_i = 1) = t$. Let $P_t$ denote the probability measure induced by these $t$-parametrized i.i.d. sequence of Bernoulli random variables.

Since $f$ is continuous and $[0,1]$ is compact, $f$ is uniformly continuous. Thus, for every $\epsilon > 0$, there exists $\delta > 0$ such that $|x - y| < \delta$ implies that $|f(x) - f(y)| \leq \epsilon$. Thus,

$|E_t[f(\frac{S_n}{n})] - f(t)|$

$= \int_{\omega: |\frac{S_n}{n} - t| \leq \delta} |f(\frac{S_n}{n}) - f(t)| P(d\omega) + \int_{\omega: |\frac{S_n}{n} - t| > \delta} |f(\frac{S_n}{n}) - f(t)| P(d\omega)$

$\leq \epsilon + 2 \sup_{y \in [0,1]} |f(y)| P_t(|\frac{S_n}{n} - t| > \delta) \qquad \text{}$

The last term converges to $\epsilon$ as $n \to \infty$ by the law of large numbers. The above holds for every $\epsilon > 0$.

Now, one needs to show that this convergence is uniform in $t$: For this show that for all $t \in [0, 1]$, via Markov's inequality and the independence of $X_i$

$P_t(|\frac{S_n}{n} - t| > \delta) = P_t(|\frac{S_n}{n} - t|^2 > \delta^2) \leq \frac{1}{4n\delta^2},$

establishing uniform convergence (over $t \in [0, 1]$), and thus complete the proof.

Exercise (A useful result on countability properties)

Let $F : \mathbb{R} \to \mathbb{R}$ be a monotonically increasing function (that is, $x_1 \leq x_2$ implies that $F(x_1) \leq F(x_2)$). Show that $F$ can have at most countably many points of discontinuity.

Hint: If a point is such that $F$ is discontinuous, then there exists $n \in \mathbb{N}$ with $F(x^+) := \lim\inf_{x_n \downarrow x} F(x)$, $F(x^-) := \lim\sup_{x_n \uparrow x} F(x)$, $F(x^+) - F(x^-) > \frac{1}{n}$. Express $\mathbb{R} = \cup_{m \in \mathbb{Z}} (m, m+1]$. Let $B_n^m := \{x \in (m, m+1] : F(x^+) - F(x^-) > \frac{1}{n}\}$. It must be that $B_n^m$ is finite for otherwise the jump would be unbounded in the interval $(m, m+1]$. Then, the countable union $\cup_n B_n^m$ will be countable. Finally $\cup_m B_n^m$ is also countable.

Exercise

Prove Theorem (that the Haar system is a complete orthonormal sequence in $L_2([0,1]; \mathbb{R})$).