\chapter[Signal Processing and Vector Spaces]{Signal Processing and \\ Vector Space}
\label{ch:vector_space}\label{ch:vs}
In the previous chapter we already started to classify signals according to their mathematical properties by discriminating, for instance, between finite- and infinite-length entities. As we progress in the book, we will encounter several more types of signal, both in discrete and in continuous time but, rather than trying to create a complex taxonomy, in this chapter we will show how the concept of \textit{vector space} provides an ideal framework to describe and analyze signals irrespective of the details inherent to their type or category.
Pedagogically speaking, today's standard approach to vector space is purely inductive: given a set of objects, called vectors, and a set of numbers, called scalars, vector space is defined by a set of rules that stipulate how vectors can be resized and combined. The approach, while elegant and concise, regrettably hides the historical sequence of brilliant intuitions that, over the course of centuries, produced the formalism currently in use. After a long pragmatic separation between the Greek ideal of synthetic geometry and the bag of tricks that was algebra, in 1637 Ren\`e Descartes arranged a remarkably fruitful union: by tackling geometric questions with algebraic methods, his \textit{analytic geometry} managed to provide an answer to problems that had long defied the classic ruler-and-compass methods (such as, famously, the trisection of the angle). Yet, it would take almost two more centuries before another crucial step in the formalization of vector space were put in place; this happened around the year 1800, when at least three different mathematicians\footnote{Friedrich Gauss and Caspar Wessel in 1799, and Jean-Robert Argand in 1806.} independently developed a geometric interpretation of complex numbers (entities de facto in use since the 16th century) that was consistent with their algebraic properties. In a way, the ideas behind the concept of complex plane contain all the fundamental ingredients that define a vector space, from the notions of norm and direction to the roles of the real and imaginary units as elements of a two-dimensional canonical basis. And yet, the extension of these results to the next logical level, that is, to three dimensions, proved a difficult nut to crack, and created a fork in the road to modern vector theory. While Hamilton and his followers continued along the algebraic path and developed the theory of quaternions (with the endorsement of leading physicists of the era such as Maxwell) it was Gibbs (and later Heaviside) that formalized the properties of vector space as we use them today as a more straightforward generalization of Cartesian geometry. Finally, \textit{linear algebra} emerged as a new branch of mathematics devoted to the study of vector space, by now extended to encompass not only tuples of arbitrary or even infinite dimension but also more abstract entities such as functions.
Most of the signal processing theory in this book can be conveniently described using vector space formalism. While by no means the only possible approach, there are several advantages to this choice, the first one of which is the ability to leverage simple geometric intuition to understand sophisticated abstract concepts. As an example, take the notion of \textit{orthogonality:}\/ the basic properties of orthogonal angles have been clearly apparent even to unschooled masons or carpenters well before their Euclidean formalization; the concept was then mathematically extended to generic vectors so that we can now talk about, say, orthogonal functions and, even if the details of how to verify such orthogonality are not spelled out, we immediately understand that two such functions must be fundamentally different in some respect. Interesting, the concept is so powerful that it has even seeped into common language, as in the sentence ``our political views are orthogonal to each other.'' So, in the next chapter, when we introduce the orthogonality of discrete-time harmonic sinusoids, we will be able to start the discussion with an intuitive understanding of the subject already in place for free.
Finally, and this as well is no small advantage, vector notation closely mirrors the data structures used by numerical analysis packages and programming languages so that signal processing algorithms expressed in vector notation translate to working code with minimal effort.
%The first advantage of this approach is compactness: the entire linear algebra toolbox becomes available and this greatly simplifies the formalism used in mathematical proofs while fostering a good geometry-based intuition with respect to the underlying principles. Secondly, vector notation provides \textit{general} theoretical results by hiding all unnecessary details (such as, for instance, the actual length of finite-length signals).
%formalizing the axioms in use today. Crucially, the latter ensure that any axiom-abiding vector space retains the structure and interpretability of the familiar Euclidean space; concepts such as distance or orthogonality, for instance, which are immediately understandable in three-dimensional space, conserve their meaning in all spaces and help us understand the properties of highly abstract vectors even when intuitive or graphical visualizations are no longer possible.
%Basic arithmetic, back at the beginning of human history, was borne of practical necessities that involved counting and measuring and, to this day, arithmetic is taught to children in a deductive manner that mirrors its early inception: apples are gathered in baskets and pies are sliced and eaten. \textit{Algebra}, i.e. the set of recipes that are used to find missing quantities in an equation, followed closely in the development of the mathematical mind and, although formalized only in the 16th century, practical recipes had started accumulating from the very beginning. Once it was clear that arithmetic operations had an inner structure of their own that did not require a physical embodiment, apples and pies became simply $x$'s and $y$'s. In the $17$th century, algebra and geometry indissolubly married: Descartes's original idea of translating geometric constructs into algebraic form spurred a new successful line of attack for a number of problems which had long defied the classic methods using ruler and compass (such as, famously, the trisection of the angle). The Cartesian plane was born and, with it, the concept of two- and three-dimensional \textit{vectors}. In two and three dimensions, that is, in Euclidean space, vectors have the same intuitive power of arithmetical apples and pies since we can rather successfully conjure up a physical representation of their nature. Again, however, it was soon realized that operations on Euclidean vectors can be defined for any dimensionality of the underlying space, leading to the concept of \textit{linear algebra}; and, although we cannot visualize $N$-dimensional space for $N>3$, we can use our low-dimensional intuition to extend to any dimension the meaning (and therefore the understanding) of concepts such as distance and orthogonality.
%Today, of course, vector spaces are introduced almost exclusively in an inductive, operational way: if a certain set of properties is satisfied by the vectors and by an operation defined on them, we have a vector space. Nothing is said about the vectors themselves, least of all how the vectors should ``look like;'' indeed, common vector spaces can have an infinite number of dimensions and contain esoteric objects such as functions. The power of the formalism, nevertheless, is that we can always use Euclidean geometry as a helpful crutch
Euclidean geometry is a straightforward idealization of the physical space that we experience with our senses and therefore the concepts of length, angle, translation or scaling require no formal explanation. In this section we will show how Euclidean space can be mapped to a vector space of real-valued tuples and, consequently, how the properties of these vectors can be described in terms of standard geometrical constructs. The idea is to associate the key ingredients of vector space to intuitive geometrical concepts before generalizing them to the more abstract vector spaces that we will use later.
\subsection{The Euclidean Plane}
\itempar{The vectors.} Consider a vector $\mathbf{x}$ defined as a pair of real numbers:
\begin{equation}
\mathbf{x} = \begin{bmatrix}
x_0 \\ x_1
\end{bmatrix}, \quad x_0, x_1 \in\mathbb{R};
\end{equation}
we call the set of all such vectors $\mathbb{R}^2$.
Consider now the Euclidean plane, equipped with a Cartesian reference system as in Figure. Each point on the plane is uniquely identified by a pair of real-valued coordinates on the two reference axes, and therefore we can associate any point on the plane to a vector in $\mathbb{R}^2$. The standard graphical representation of such a vector is an arrow that from the origin (i.e. the point with coordinates\footnote{
The superscript $T$ indicates transposition so that $[0\;\;0]^T$ is a column vector.
}
$[0\;\;0]^T$) reaches the point with coordinates $[ x_0\;\; x_1]^T$, as in Figure~\ref{fig:vs:vector_representation_r2}.
although we could have invented a different ``recipe'' for addition, this particular one makes a lot of sense since it corresponds to a \textit{translation} of $\mathbf{y}$ by $\mathbf{x}$: geometrically, we place $\mathbf{y}$ at the end of $\mathbf{x}$ and we connect the origin to the endpoint of the joined vectors as in Figure~\ref{fig:vs:vector_addition_r2}. This is the classic parallelogram rule for vector addition.
again, this makes geometrical sense since it corresponds to changing the ``size'' of the vector, as in Figure~\ref{fig:vs:scalar_multiplication_r2}. Given these definitions for sum and scalar multiplication, it is easy to verify that they possess all the nice properties we expect them to have, including distributivity, associativity and so on. We will formalize all this later. Multiple vectors can be joined together in \textit{linear combinations} of the form:
\begin{equation}
\mathbf{y} = \sum_{n=0}^{N}\alpha_n \mathbf{x}_n
\end{equation}
where the subscript, when applied to a boldface symbol, indicates the ordinal number of an item in a given set of vectors.
\itempar{Norm, similarity and distance.} We said that scalar multiplication changes the ``size'' of a vector but we haven't defined a way to quantify said size. Once again, by looking at the geometric interpretation of $\mathbb{R}^2$, the natural choice is using the length of the arrow that represents the vector; that is commonly called the \textit{norm} and is represented by the symbol $\|\cdot\|$. From Figure~\ref{fig:vs:vector_representation_r2}, using Pythagoras Theorem, it's easy to see that
\begin{equation}\label{eq:vs:norm_r2}
\|\mathbf{x}\| = \sqrt{x_0^2 + x_1^2}
\end{equation}
Consider now the problem of estimating the degree of \textit{similarity} between two vectors; if we start with vectors of equal norm, the only thing left to compare is their directions or, in other words, the angle that they form. If the angle is small, the vectors will be basically oriented equally and almost interchangeable; at the other extreme, if they form a right angle, they will be maximally dissimilar in the sense that the second vector shares no directionality component with the first. The \textit{inner product} of two vectors in $\mathbb{R}^2$ is a function from $\mathbb{R}^2\times\mathbb{R}^2$ to $\mathbb{R}$ and it is defined as:
\begin{equation}\label{eq:vs:inner_product_r2}
\langle\mathbf{x, y}\rangle = x_0 y_0 + x_1 y_1.
\end{equation}
Although the definition is not instantly intuitive, the following properties will help: first of all, again by invoking Pythagoras, we can see that
\begin{equation}
\langle\mathbf{x, x}\rangle = \|\mathbf{x}\|^2
\end{equation}
namely, a vector's self inner product is equal to the square of the norm as defined in~(\ref{eq:vs:norm_r2}). Secondly, using basic trigonometry, we can rewrite the inner product as
where $\theta$ is the angle between $\mathbf{x}$ and $\mathbf{y}$ as in Figure~\ref{fig:vs:inner_product_r2}. The inner product as defined above, therefore, is a qualitative measure of similarity between vectors. Vectors forming a right angle, that is, vectors that are maximally dissimilar, will have an inner product of zero. Such vectors are called \textit{orthogonal}.
Finally, for a quantitative measure of how far apart two vectors are, we can use the norm of their difference to compute the \textit{distance} between vectors as
\begin{equation}
d(\mathbf{x, y}) = \|\mathbf{x - y}\|;
\end{equation}
by using the definition of the norm in terms of the inner product, we have
\begin{align*}
\|\mathbf{x - y}\|^2 &= \langle\mathbf{x - y, x - y}\rangle\\
The fact that any vector in $\mathbb{R}^2$ can be expressed as a linear combination of $\boldsymbol{\delta}_0$ and $\boldsymbol{\delta}_1$ makes the set $\{\boldsymbol{\delta}_0, \boldsymbol{\delta}_1\}$ a \textit{basis} for $\mathbb{R}^2$. This basis is also particularly good since its elements have unit norm and are orthogonal, that is, they form an \textit{orthonormal} basis; if we look at the way we have been drawing vectors on the plane, as exemplified in Figure~\ref{fig:vs:bases_r2}-(a), we can see that the Cartesian reference grid uses $\boldsymbol{\delta}_0$ and $\boldsymbol{\delta}_1$ as the units on the horizontal and vertical axis, respectively. For this particular basis, the coefficients in the expansion~(\ref{eq:vs:basis_expansion_r2}) coincide with the elements of the vector; this unique fact gives $\{\boldsymbol{\delta}_0, \boldsymbol{\delta}_1\}$ the prestigious title of \textit{canonical basis}.
There is however an infinity of other bases that can be used for $\mathbb{R}^2$. For instance, any rotation by an angle $\theta$ of the canonical basis is also an orthonormal basis whose elements are
and the grid they induce on $\mathbb{R}^2$ is shown in Figure~\ref{fig:vs:bases_r2}-(b). Note that a basis need not be orthonormal; for instance the vectors
from a valid basis for $\mathbb{R}^2$ and they induce the non-rectangular grid shown in Figure~\ref{fig:vs:bases_r2}-(c). On the other hand, the vectors
(Figure~\ref{fig:vs:bases_r2}-(d)) do not form a basis for $\mathbb{R}^2$ since any linear combination will necessarily yield a point on the horizontal axis (the second element of the resulting vector will always be zero). Stated differently, the two vectors are not \textit{linearly independent}.
Consider a vector $\mathbf{x}$ in the canonical basis and pick new basis $\{\mathbf{w}_0, \mathbf{w}_1\}$; how can we find the coefficients that express $\mathbf{x}$ in the new basis? In the Euclidean plane (and in Euclidean space in general), we can always expand the equation
(we use the notation $w_{n,m}$ to indicate the $m$-th element of vector $\mathbf{w}_n$). For instance, looking at Figure~\ref{fig:vs:bases_r2}-(c) and given $\mathbf{x} =[3\;\;2]^T$ we have
We use the left inner product because it mirrors the order of the operands when the change of basis is expressed as a matrix-vector multiplications as in~(\ref{eq:vs:matrixcob}). The order is of course irrelevant when we operate over the field of reals, since in that case the inner product is commutative; over the field of complex numbers, however, the inner product is commutative with conjugation (see definition~(\ref{eq:vs:inner_prod_comm}) later) and so the order is crucial.\label{page:vs:order}}
inner product of both sides in~(\ref{eq:vs:change_of_basis_r2}) with $\mathbf{w}_0$ and $\mathbf{w}_1$ in turn, we can obtain directly:
Bases play a fundamental role in signal processing since, as we will see in the next Chapter, the Fourier Transform can be interpreted as a change of basis in an appropriate vector space. Intuitively, a change of basis is a change of perspective: we're looking at the same data but from a different reference system and this change of viewpoint can highlight properties of a signal that are difficult to see in the original dataset.
Let's now look once again at the definition of inner product in~\ref{eq:vs:inner_product_r2}. Consider Figure~\ref{fig:vs:orthogonal_projection_r2} and assume $\|\mathbf{x}\|=1$; the vector
is called the \textit{orthogonal projection} of $\mathbf{y}$ over $\mathbf{x}$ and it represents the best approximation of $\mathbf{y}$ using a scaled version of $\mathbf{x}$. The approximation is optimal in the sense that it achieves the minimum distance (or, in other words, the minimum Mean Square Error) between the original vector and any approximation based on $\mathbf{x}$:
this is illustrated graphically in Figure~\ref{fig:vs:min_dist_r2} and can be easily derived analytically by solving $\partial\|\mathbf{y} -\alpha\mathbf{x} \|^2/\partial\alpha=0$. Additionally, the approximation error $\mathbf{y - y_x}$ is orthogonal to the approximation itself
meaning that all the information of $\mathbf{y}$ that was expressible by $\mathbf{x}$ has been captured by the approximation. Please note that if $\|\mathbf{x}\|\neq1$, the orthogonal projection simply includes a normalization term:
Although these results are nearly self-evident in $\mathbb{R}^2$, they will be particularly interesting when generalized to spaces of higher dimensionality.
One dimension up from the plane is the three-dimensional Euclidean space, which can be described in terms of vectors in $\mathbb{R}^3$ of the form
\begin{equation}
\mathbf{x} = \begin{bmatrix}
x_0 \\ x_1 \\ x_2
\end{bmatrix}, \quad x_0, x_1, x_2 \in\mathbb{R}.
\end{equation}
Addition, scalar multiplication and inner product all retain their definitions (by adjusting for one more component) and their geometrical meaning. Euclidean space, however, allows us to illustrate the concept of subspace approximation better than the plane.
\itempar{Subspaces and Least Squares approximation.} A vector subspace is a subset of the original vector space closed under addition and scalar multiplication; consider for example a plane in 3D space: if we sum (or rescale) vectors laying on the plane we remain on the plane and therefore we have a proper subspace. Subspaces have their own bases, which can be orthonormal of course. For instance, Figure~\ref{fig:vs:plane_in_3d} illustrates the planar subspace spanned by the first two 3D canonical vectors
\caption{Three-dimensional Euclidean space and the planar subspace spanned by the first two canonical basis vectors; the subspace is closed under addition and scalar multiplication.}\label{fig:vs:plane_in_3d}
The existence of orthonormal bases for subspaces provides a very elegant answer to the problem of approximating an arbitrary vector with elements of a subspace. While the problem may appear quite abstract at first, it is actually at the core of many signal processing applications: modern image or video compression algorithms, for example, proceed by approximating a signal living in a high-dimensional space with a set of basis vectors from a subspace of much lower dimensionality.
Consider a vector space $V$ and a subspace $W \subseteq V$; assume $\{\mathbf{w}_k \}_{k =0,1,\ldots, K-1}$ is an orthonormal basis for $W$. The \textit{projection theorem} states that the vector
is the ``best'' approximation of $\mathbf{x} \in V$ over $W$. To see why, let's first unpack the above Equation; the sum is a linear combination of orthogonal projections of $\mathbf{x}$ onto all the basis vectors for the subspace. We already know from Equation~(\ref{eq:vs:orthogonality_of_projection}) that each orthogonal projection is the best approximation of $\mathbf{x}$ using a single unit norm basis vector. To show that (\ref{eq:vs:projection_theorem}) is the best global approximation in $W$ we need to show that the error $\mathbf{x -\hat{x}}$ is orthogonal to the approximation $\mathbf{\hat{x}}$:
this means that no further portion of the error could be accounted for by elements of the subspace and we've done the best we could. To prove~(\ref{eq:vs:orthogonality_of_approximation}) just substitute for~(\ref{eq:vs:projection_theorem}), use the distributivity of the inner product and remember that the basis $\{\mathbf{w}_k \}$ is orthonormal. If the error is orthogonal to the subspace, the approximation minimizes the (square) norm of the error:
the approximation is therefore optimal in the least squares sense. An example of subspace approximation in Euclidean Space is given in Figure~\ref{fig:vs:projection_theorem}.
Note that the approximation provided by a set of orthonormal vectors can be \emph{successively refined}. Assume you have an approximation using the first $m$ basis vectors:
While this may seem obvious, it is actually a small miracle, since it does not hold for more general, non-orthonormal bases; a classic application of this property is used in algorithms for variable-bit-rate transmission of audio and video.
\caption{Least-squares approximation of a 3D vector onto the subspace spanned by the first two canonical basis vectors.}\label{fig:vs:projection_theorem}
Formally, it's quite easy to increase the number of dimensions beyond three: just consider the set of all tuples of $N$ real numbers
\begin{equation}
\mathbf{x} = \begin{bmatrix}
x_0 \\ x_1 \\\vdots\\ x_{N-1}
\end{bmatrix}.
\end{equation}
By extending the Euclidean definitions of sum, scalar multiplication and inner product in a straightforward manner we obtain a vector space called $\mathbb{R}^N$. While formally equivalent to Euclidean space, $\mathbb{R}^N$ does not correspond to any physical entity that we can visualize; yet, the intuition gained in 2 and 3 dimensions can help us understand the properties of higher-dimensional spaces that defy graphical representation.
Similarly, we can define vectors as tuples of complex numbers; the resulting vector space, $\mathbb{C}^N$, cannot be represented graphically for $N$ greater than one, but properties like norm, orthogonality and distance remain intuitive by analogy to Euclidean space. In general, no matter how abstract the vector space, we can always try to resort to the geometrical interpretation of $\mathbb{R}^2$ or $\mathbb{R}^3$ to get an intuitive grasp on the space's properties.
Following are the axiomatic definitions for a vector space equipped with an inner product. The stuff is dry, no question, but it simply encodes at an abstract level the very reasonable properties we have seen for Euclidean space\footnote{
Although the analogy is a bit tenuous, readers with more than a passing acquaintance with object-oriented programming could be excused for drawing a parallel between the concept of vector space and that of an interface class: internal variables and implementations in derived classes can be arbitrary as long as they conform with the interface.}.
\itempar{Vector Space.} A vector space $H(V, S)$ is defined in terms of $V$, a set of objects called \textit{vectors}, and $S$, a set of numbers called \textit{scalars}; note that we will always assume $S=\mathbb{C}$. For the vector space to have any use, we need to be able to resize and combine vectors together and this is achieved via two operations called, respectively, \textit{addition} and \textit{scalar multiplication}. For $H(V, S)$ to be a vector space, these two operations, while arbitrarily definable, must fulfill the following set of axioms:
For any $\mathbf{x, y, z,} \in V$ and any $\alpha, \beta\in S$:
Note that no restrictions are set on what's ``inside'' a vector or on the internal mechanics of the vector operations; this leads to the great power of generalization of the vector space paradigm.
\itempar{Inner Product Space.} In order to compare vectors in a space, we need some function that takes two vectors and returns some measure of their similarity. The usual choice is to equip the space with an \textit{inner product} (or \textit{dot product}), namely, a function defined on $V\times V$ that returns a scalar; remember that our set of scalars is $\mathbb{C}$. Again, the inner product can be defined arbitrarily, as long as it satisfies the following properties:
For any $\mathbf{x, y, z} \in V$ and $\alpha\in\mathbb{C}$:
\begin{itemize}
\item the inner product is distributive:
\begin{equation}
\langle\mathbf{x + y, z}\rangle = \langle\mathbf{x, z}\rangle + \langle\mathbf{y, z}\rangle
\end{equation}
\item the inner product is commutative, with complex conjugation:
\itempar{Hilbert Space.} The axioms for addition and scalar multiplication require that the result of these operations remain in the original vector space; as a consequence, all linear combinations of a \textit{finite} number of vectors from $V$ will live in $V$ as well. However, that is not sufficient to guarantee that the limit of a convergent sequence of vectors in $V$ is also in $V$. Closure of a vector space under convergent limiting operations is an independent property called \textit{completeness} and a inner-product space that is complete is called a \textit{Hilbert space}. Completeness is a rather technical property and one that is often difficult to prove rigorously\footnote{In this book, we will really need completeness only once in Chapter~\ref{ch:sampling} when we prove the sampling theorem, and we will tacitly assume the property without proof.}. While there are no elementary examples of a non-complete vector space, to gain some intuition think of the set of rational numbers $\mathbb{Q}$; this set is not complete because there are many sequences in $\mathbb{Q}$ that converge to irrational numbers. Consider for instance, the sequence
\[
s_k =\sum_{n=1}^{k}\frac{1}{n^2};
\]
while it's easy to see that $s_k \in\mathbb{Q}$ for all values of $k$, it can be shown that
The set of rational numbers $\mathbb{R}$, on the other hand, is complete.
\subsection{Norms and Distances}
The properties of the inner-product induce a topology on the vector space, namely, once we have an inner product, we can start to compare vectors and define qualitative and quantitative measures of similarity. The most important concept is orthogonality
\[
\langle\mathbf{x, y} \rangle=0,
\]
which encodes the notion of maximal difference between vectors. The \textit{norm}, defined in terms of the self inner product
\begin{equation}\label{eq:vs:norm}
\|\mathbf{x}\|^2 = \langle\mathbf{x, x}\rangle,
\end{equation}
is used to quantitatively describe the size of a vector. The norm also extends the concept of Euclidean distance to arbitrary vector spaces as
\begin{equation}
d(\mathbf{x, x}) = \|\mathbf{x - y}\|;
\end{equation}
this distance measure is also known as the Mean Square Error between vectors.
\itempar{Triangle Inequality} To quickly show the power of the abstract definitions above, let's formally prove the \textit{triangle inequality} in an generic inner product space $H(V,\mathbb{C})$. The statement is simple: given any two vectors $\mathbf{x,y} \in V$, it is always
where the norm is the natural norm induced by the inner product as in~(\ref{eq:vs:norm}). On the Euclidean plane, the above relation is obvious since it states that, for any triangle, the sum of the length of two sides can't be smaller than the length of the third side. The result is however valid for all inner-product spaces and, to prove the inequality in the general case, we first need an intermediate result, called the \textbf{Cauchy-Schwarz inequality}:
To prove this, assume $\mathbf{x, y \neq0}$ (otherwise the result is obvious) and consider the orthogonal projection (\ref{eq:vs:orthProj}) of $\mathbf{y}$ onto $\mathbf{x}$
call $\mathbf{d = y - y_x}$ the approximation error and remember that the error is orthogonal to $\mathbf{y_x}$; you can look at a graphical representation of the vectors involved in the proof in Figure~\ref{fig:vs:cauchy_schwarz}. Since $\mathbf{y = y_x + d}$ we can write
where we have used~(\ref{eq:vs:inner_prod_comm}), the fact that $|z| \geq\Re\{z\}$ for all $z \in\mathbb{C}$ and, of course, the Cauchy-Schwarz inequality. Please note that nowhere in the proof we made use of the internal structure of the vectors; we only used the axioms.
\itempar{Other Norms} We should mention in passing that, although the norm induced by the inner product is the natural norm for a Hilbert space, we are free to define alternative quantitative measures of a vector's size. In Euclidean space, for instance, the so-called $p$-norm is defined as
The latter, in particular, will reappear in a major role when we study FIR filter design. Norms not derived from the inner product, in order to be valid norms, must be \textit{designed} to satisfy the triangle inequality.
\subsection{Bases and Subspaces}\label{sec:vs:bases}
Given a vector space $H(V,\mathbb{C})$, a subset of $N$ vectors $S =\{\mathbf{s}_k\}_k$, is said to be linearly independent if the equation
\[
\sum_{k=0}^{N-1}\beta_k\mathbf{s}_k =\mathbf{0}
\]
only admits the solution $\beta_k =0$ for $k =0, 1, \ldots, N-1$. Linear independence states that the subset $S$ contains no redundancies, that is, none of its members can be expressed as a linear combination of the others. Now, suppose we can determine a subset of $N$ vectors $W =\{\mathbf{w}_k\}_k \subseteq H$ so that any element $\mathbf{x} \in H$ can be written as a linear combination of elements of $W$:
\[
\mathbf{x} =\sum_{k=0}^{N-1}\alpha_k\mathbf{w}_k;
\]
in this case we say that $W$ is a \textit{spanning set} for $H$. If the set is also linearly independent (i.e., it contains no redundancy) then we call $W$ a \textit{basis} for $H$. If $W$ is a basis, the coefficients $\alpha_k$ are unique, as a consequence of linear independence. The laborious process of finding the analysis coefficients $\alpha_k$ for an arbitrary vector $\mathbf{x}$ is greatly simplified if the basis is orthonormal:
If a basis for $H$ contains $N$ elements, it is relatively straightforward (at least for finite $N$) to show that any other basis will also contain exactly $N$ vectors; $N$ is therefore called the \textit{dimensionality} of $H$. As a consequence, for finite-dimensional vector spaces, any set $S =\{\mathbf{s}_k\}_k$ of $N$ linearly-independent vectors will constitute a basis; indeed, if $S$ did not span $H$ then there exists at lease one nonzero element $\mathbf{x} \in H$ so that
\[
\mathbf{x} \neq\sum_{k=0}^{N-1}\alpha_k\mathbf{s}_k \quad\mbox{for all $\alpha_k$},
\]
that is, $S' =\{\mathbf{s}_0,\ldots,\mathbf{s}_{N-1}, \mathbf{x}\}$ is a set of $N+1$ linearly independent vectors. Now, if $S'$ spans $H$, it will be $\dim(H)= N+1$, which is a contradiction; otherwise we can repeat the procedure and augment $S'$ until we have a basis, but, a fortiori, the dimensionality of $H$ will be larger than $N$.
Finally, mutually orthogonal vectors are inherently linearly independent; pick a set of $N$ nonzero orthogonal vectors $\{\mathbf{w}_k\}_k$ and assume we can write
\[
\sum_{k=0}^{N-1} c_k\mathbf{w}_k =\mathbf{0}
\]
with at least one nonzero coefficient $c_i$. By the properties of the inner product, since $\langle\mathbf{0}, \mathbf{x} \rangle=0$, we have
After an informal introduction using Euclidean space and a precise axiomatic definition, we are now ready to see how vector spaces are going to be used for signal processing in the rest of the book.
\subsection{Discrete-time Signals}
\label{sec:vs:dt_space}
As we have seen in the previous chapter, in signal processing it is common practice to use the expression $x[n]$ to indicate a discrete-time signal in its entirety; this is an abuse of notation, since the term $x[n]$ in fact pinpoints the value of the signal $x[\cdot]$ at a specific index value $n$. Vector notation, on the other hand, provides us with a much more compact and precise symbolism: we can use the symbol $\mathbf{x}$ to indicate an entire signal and the expression $x[n]$ to indicate its $n$-th value.
\itempar{Finite-length signals} Length-$N$ signals are simply ordered tuples of $N$ complex numbers and therefore they belong to $\mathbb{C}^N$:
\begin{equation}
\mathbf{x} = \begin{bmatrix}
x[0] \\ x[1] \\\vdots\\ x[N-1]
\end{bmatrix}
\end{equation}
Addition and scalar multiplication are defined in the intuitive, straightforward way. The inner product is defined as
We will soon see that, in signal processing, a \textit{filter} works by implementing an inner product; indeed, by filtering a data set, we are evaluating the local degree of similarity of the input with a prototype ``shape'', known as the filter's impulse response. Similarly, many communication systems work by comparing the incoming waveform to a set of predefined ``pulses'' that encode different symbols; the measure of similarity that is used for the selection of the closest pulse is also an inner product.
The canonical basis for $\mathbb{C}^N$ also intuitive:
In $\mathbb{C}^N$ a particularly nice thing happens: the set of $N$ coefficients $\alpha_k$ is itself a member of $\mathbb{C}^N$ and this opens up the full linear algebra toolbox for us to use. For example, remembering the definition of inner product in~(\ref{eq:vs:inner_product_rn}), we can build an $N\times N$ matrix $\mathbf{M}$ by stacking the conjugates of the basis vectors as rows\footnote{The notation $\mathbf{x}^H$ denotes the \textit{Hermitian transpose} i.e. a vector or a matrix where the original elements have been transposed \textit{and} conjugated.}
\begin{equation}
\def\arraystretch{1.7}
\mathbf{M} = \left[ \begin{array}{c}
\mathbf{s}_0^H \\\hline
\mathbf{s}_1^H \\\hline
\vdots\\\hline
\mathbf{s}_{N-1}^H
\end{array}\right]
\end{equation}
and, with this, obtain all the coefficient $\alpha_k$ in one go using the matrix-vector product:
\begin{equation}
\mbox{\boldmath{$\alpha$}} = \mathbf{Mx}.
\end{equation}
Note that $\mathbf{M}^H$ is a matrix whose columns are simply the basis vectors side by side; we can therefore write
The possibility of applying the constructs of linear algebra to signal manipulation further allows us to cast all linear operations on signals as matrix-vector multiplications. Although we will not really pursue this approach in the rest of the book, some examples are in the exercise section for Chapter~\ref{ch:lti}.
\itempar{Periodic Signals} Periodic signals of period $N$ are completely described by $N$ consecutive samples and therefore they are equivalent to finite-length signals of length $N$; they also live in $\mathbb{C}^N$ and, when the periodicity is to be made explicit, we will sometimes use the notation $\tilde{\mathbb{C}}^N$.
\itempar{Infinite-length signals} From a purely formal point of view, we can let $N$ in $\mathbb{C}^N$ grow to infinity and, by keeping the same definitions for sum, scalar multiplication and inner product, we obtain the vector space $\mathbb{C}^\infty$ (sometimes also notated as $\mathbb{C}^{\mathbb{Z}}$ since, in signal processing, we are usually using both positive and negative indexes). Because the resulting space is now infinite-dimensional, we need to exercise much caution; for example, it is immediate to see that the inner product can diverge even for elementary signals such as a constant signal whose samples are all equal to one; indeed
To avoid these type of problems we can consider instead the set of infinite-length vectors whose Euclidean norm is finite, that is, the space of square-summable sequences; the space is called $\ell_2(\mathbb{Z})$, with
and is also known as the space of \textit{finite-energy} signals, given the definition of energy in~(\ref{eq:dts:energy}). In this space the inner product is always well defined, as can be shown by using the Cauchy-Schwarz inequality. Be forewarned, however, that there are a lot of interesting signals that are not in $\ell_2(\mathbb{Z})$ and we will see how to deal with them while trying to preserve the vector space formalism.
In the case of infinite dimensions, the concept of basis also becomes tricky since it is not necessarily safe to allow for linear combinations of vectors with an infinite number of terms in the sum. In $\ell_2(\mathbb{Z})$, however, all is well: the canonical basis for the space is the extension to infinite dimensions of the canonical basis for $\mathbb{C}^N$, that is, an infinite set of vectors in which only a single element at a time is equal to one.
\subsection{Function Spaces}
\label{sec:vs:funcs}
Function vector spaces, as the name implies, are spaces in which the vectors are functions; since we know from calculus how to combine, rescale and measure the difference between functions, we can re-cast those operations in such a way that they comply with the axioms of a vector space. Here we are really performing a task of profound abstraction because our vectors are no longer tuples of numbers but sophisticated mathematical entities.
In this book we will only be interested in two specific function spaces, the space of square-integrable functions over an interval and the space of bandlimited functions on the real line; we will wait until Chapter~\ref{ch:is} to introduce the latter, but the former is easily described: consider an interval $I$ and the set of complex-valued functions of a real variable $\mathbf{x} = x(t)$ such that
\begin{equation}
\int_I |x(t)|^2 \de t < \infty.
\end{equation}
The space of all such functions is denoted by $L_2(I)$; addition and scalar multiplication are defined in the intuitive manner:
\dspFunc{x 180 mul sin x abs 1 exch sub mul dup 0 ge {pop 0}{} ifelse}}
\dspFunc[linecolor=ColorOne]{x 180 mul sin}
\dspFunc[linecolor=ColorTwo]{x abs 1 exch sub }
\end{dspPlot}
\caption{Orthogonality of symmetric and antisymmetric functions. The shaded areas show the integration area in the inner product.}\label{fig:vs:orthogonal_functions}
The concept of orthogonality carries on, with the same meaning, to function spaces. Consider for instance the two vectors
\begin{align}
\mathbf{x}&= \sin(\pi t)\\
\mathbf{y}&= 1 - |t|
\end{align}
over $I =[-1, 1]$, as shown in Figure~\ref{fig:vs:orthogonal_functions}. Their inner product is the integral
\[
\int_{-1}^{1} (1- |t|)\sin(\pi t)\de t
\]
which, graphically, is the sum of the positive green area and the negative red areas in the picture; since this sum is zero, the functions are orthogonal. This makes sense since the first function is odd and the second is even: clearly no symmetric shape can be captured by an antisymmetric curve. Similarly, two sinusoids at different multiples of a fundamental frequency are also orthogonal, as shown in Figure~\ref{fig:vs:orthogonal_sinusoids}; the orthogonality of harmonically-related sinusoids is one of the key concepts in signal processing.
\dspFunc{x 180 mul 4 mul sin x 180 mul 5 mul sin mul dup 0 ge {pop 0}{} ifelse}}
\dspFunc[linecolor=ColorOne]{x 180 mul 4 mul sin}
\dspFunc[linecolor=ColorTwo]{x 180 mul 5 mul sin}
\end{dspPlot}
\caption{Orthogonality of sinusoids $\mathbf{x} =\sin(4\pi t)$ and $\mathbf{y} =\sin(5\pi t)$ over $[-1, 1]$; the sinusoids' frequencies are multiples of the fundamental frequency for the interval. The sum of the shaded areas yields the value of the integral in the inner product, which is zero.}\label{fig:vs:orthogonal_sinusoids}
Function vector spaces possess bases as well, obviously. For instance, an orthonormal basis for $L_2\bigl([-\pi, \pi]\bigr)$ is the well-known Fourier basis
\begin{equation}
\{ (1/\sqrt{2\pi}) \,e^{jnt}\}_{n \in\mathbb{Z}}.
\end{equation}
The number of vectors is understandably infinite but, perhaps surprisingly, they forms a \textit{countable} set. While it's easy to verify that the vectors are orthogonal, proving that they indeed span $L_2\bigl([-\pi, \pi]\bigr)$ is a much harder task --- unfortunately, this is very much the rule for all non-trivial, infinite-dimensional basis sets, as we will have to admit again for the space of bandlimited functions in Chapter~\ref{ch:sampling}.
\begincoda
\section{Appendix: Approximation via Legendre Polynomials}
In this section we will illustrate how the concept of subspace projection can lead to optimal polynomial approximation (in the min-square-error sense) for functions over an interval. This example will give us the chance to talk about polynomial vector spaces, orthonormalization procedures and optimal approximation via subspace projections with a concrete case study. While the section is not a direct signal processing application, approximation by projection is routinely used in compression algorithm and the concepts illustrated here will show the flexibility of the vector space approach.
Let's start by considering $P_N(I)$, the vector space of all polynomials of degree up to $N-1$ over the interval $I$; a generic element of $P_N(I)$ is of the form
\begin{equation}
\mathbf{a} = a_0 + a_1 t + \ldots + a_{N-1}t^{N-1}, \quad a_k\in\mathbb{R}, t\in I.
\end{equation}
Addition and scalar multiplication are defined according to standard polynomial algebra and, since $P_N(I)\in L_2(I)$, we will use the standard definition for the inner product as in~(\ref{eq:vs:inner_product_function}). A natural basis for $P_N(I)$ is the family
\begin{equation}
\{1, t, t^2, \ldots, t^{N-1}\}
\end{equation}
since every vector is a linear combination of powers of $t$. The natural basis, however, is not orthonormal so before we can address the issue of subspace approximation we need to rectify that.
\itempar{Gram-Schmidt Orthonormalization} A basis for a vector (sub)space can be transformed into an orthonormal basis via the Gram-Schmidth iteration. Given a basis $\{\mathbf{s}_k\}$, the procedure progressively ``whittles'' away from each basis vector the portions that are linearly dependent to the previously processed elements. In detail, the orthonormal basis $\{\mathbf{u}_k\}$ is built one vector at a time by first converting $\mathbf{s}_m$ into $\mathbf{p}_m$, a vector orthogonal to the set of the previously-computed $\{\mathbf{u}_0, \ldots, \mathbf{u}_{m-1}\}$, and then by normalizing $\mathbf{p}_m$ and adding it to the pool:
The resulting family of orthonormal basis vectors is known under the name of Legendre polynomials; the basis for $P_6([-1,1])$ is plotted in Figure~\ref{fig:vs:legendre_basis}.
\itempar{Subspace approximation} Now that we have an orthonormal polynomial basis for the interval, let's try to approximate a function via subspace projection. We will pick an element from $L_2([-1,1])$
\[
\mathbf{x} =\sin t
\]
and project it over the basis for $P_3([-1,1])$ that we computed before. We will then compare the result to another well known linear approximation for the sine, namely its Taylor series expansion.
The expansion coefficients over the Legendre basis are readily computed:
note that we need to explicitly compute just the value for $\alpha_1$ since, in the other two cases, the inner products are between an even and an odd function, which we know to be orthogonal. In the end, the least-squares approximation to $\sin t$ over $P_3([-1,1])$ is:
By comparison, the second-degree Taylor approximation of the sine around zero is the function $\mathbf{y} = t$. Although $\mathbf{y}$ and $\hat{\mathbf{x}}$ seem very similar, let's look at the approximation error over the interval as shown in Figure~\ref{fig:vs:legendre_vs_taylor}. Although the Taylor approximation is more precise around the origin, we can see that the Legendre approximation minimizes the \textit{global} error, i.e. the mean square error over the entire interval.