\chapter{Signal Processing and Vector Spaces}\label{ChLinalg}
In the previous Chapter we have started to introduce different categories of discrete-time sequences (finite- and infinite-length, periodic); as we progress, we will encounter several more mathematical objects used to represent signals (Fourier Transforms, continuous-time functions). In this Chapter we will see how the concept of \textit{vector space} provides us with a common framework to manipulate and analyze the properties of signals irrespective of their type or category.
Today, the standard approach to vector space is rigorously inductive: given a set of objects called vectors, and a set of numbers, called scalars, the space is described by a set of axioms that regulate how vectors can be combined and rescaled. But, as always in math, we can travel backwards in time from this rarefied approach until we reach the initial intuition: in this case we land in the $17$th century where Descartes's original idea of marrying geometry and algebra proved extremely successful in solving problems that had long defied the classic ruler-and-compass methods (such as, famously, the trisection of the angle). The Cartesian plane was born and, with it, the concept of two- and three-dimensional Euclidean space.
Vectors, which started as coordinate pairs or triples, have been in time extended to multiple dimensions, then to infinite dimensions and finally to arbitrary objects such as functions. \textit{Linear algebra} emerged as a new branch of mathematics devoted to vector space, formalizing the axioms in use today. Crucially, the axioms ensure that any vector space retains the structure and interpretability of the familiar Euclidean space; concepts such as distance or orthogonality, for instance, which are immediate in three-dimensional space, conserve their meaning in arbitrary vector spaces and help us understand their properties even if an intuitive visualization of the vectors is no longer possible.
Most of the signal processing theory in this book can be usefully described using operations in a suitable vector space. 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). Finally, and this is on the practical side, vector notation is the standard paradigm for numerical analysis packages such as Matlab or Numpy; signal processing algorithms expressed in vector notation translate to working code with minimal effort.
%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
In the previous Chapter, we established the basic notation
for the different classes of discrete-time signals which we
will encounter time and again in the rest of the %course
book and
we hinted at the fact that a tight correspondence can be
established between the concept of signal and that of vector
space. In this Chapter, we %will
pursue this link further,
firstly by reviewing the familiar Euclidean space in finite
dimensions and then by extending the concept of
%basic
vector space to infinite-dimensional Hilbert spaces.
\section{Euclidean Space as a Vector Space}
Euclidean geometry is a straightforward idealization of physical space based on our sensory experience and, as such, the associated notions of translation, scaling, distance and angles require no complicated explanation. Here we will show how Euclidean space can be mapped to a vector space of real-valued tuples and how standard geometrical operations map to suitably defined vector operation. The idea is to associate the key ingredients of vector space to intuitive concepts before generalizing them to the more abstract vector spaces we will use later.
\subsection{The Euclidean Plane}
Consider a tuple of $N$ real numbers:
\[
\mathbf{x} = \begin{bmatrix}
x_0 \\ x_1 \\ \vdots \\ x_{N-1}
\end{bmatrix};
\]
call any such tuple a vector and call $\mathbb{R}^N$ the putative vector space it belongs to. For $N=2$ ($N=3$ later) we can map any vector in $\mathbb{R}^N$ to a point on the Euclidean plane; an intuitive method do to so is to consider a coordinate system...
Define now the \textit{sum} of two vectors in $\mathbb{R}^2$ like so:
although we could have chosen other definitions for the sum, this particular one makes a lot of sense since it corresponds to a \textit{translation} on the plane.
Similarly, define the scalar multiplication by a scalar $\alpha \in \mathbb{R}$ as
again, this makes geometrical sense since it corresponds to changing the ``size'' of the vector.
Linear combination
\itempar{Norm and distance.} Speaking of size, introduce topology via inner product
norm
angle
distance
\itempar{Bases and projections.} Let's look back at our choice for the graphical representation;
orthonormal basis
change of basis
where $x_i \in \mathbb{R}$, $ i = 0, 1, \ldots, N-1$. We
call this set of coordinates a \emph{vector}\index{vector|mie}
and the $N$-tuple will be denoted
synthetically by the symbol $\mathbf{x}$; coordinates are
usually expressed with respect to a ``standard'' orthonormal
basis.\footnote{The concept of basis will be defined more
precisely later on; for the time being, consider a standard
set of orthogonal axes.}
\subsection{Euclidean Space}
\subsection{Higher Dimensions}
\section{Vector Space: a Formal Definition}
\subsection{Inner Product Spaces}
Following are the axiomatic definitions for a vector space equipped with an inner product. The stuff is dry, no question, but it just encodes at an abstract level the very reasonable properties we have seen for the Euclidean space.
\itempar{Basic 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}. In addition, 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{scalar multiplication} and \textit{addition}. 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; note that in the following, we will always assume that $S = \mathbb{C}$, the set of complex numbers. 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}$:
\item the inner product scales with respect to scalar multiplication\footnote{Note that in our notation it is the left operand that is conjugated. This will allow us to write the Fourier transform analysis formula as a left product.}:
\itempar{Hilbert Space.} When we defined the axioms for addition and scalar multiplication, we stated that the operation of combining vectors should not leave the vector space we started from; in other words, linear combinations of vectors must live in $V$. Another common requirement for a vector space is that all converging limiting operations involving sequences of vectors in $V$ should converge to an element of $V$. This property is called \textit{completeness} and when an inner-product space is complete, it is called it a \textit{Hilbert space}. Completeness is both a rather technical property and one that is often difficult to prove rigorously\footnote{We will really need completeness only once later on when we prove the sampling theorem, and we will tacitly assume the property without proof.}. While there are no elementary examples of a noncomplete 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 properties of an inner-product space induce a topology on the vector space, namely, we can analyze the spatial relations between vectors and define quantitative measures of similarity. First of all,
orthogonal
norm
unit norm
Cauchy
Triangle
Pythagoras
inner product vs distance
\subsection{Subspaces, Bases and Projections}
\section{Euclidean Geometry: a Review}
\noindent
Euclidean geometry is a straightforward formalization of our
spatial sensory experience; hence its cornerstone role in
developing a basic intuition for vector spaces. Everybody is
(or should be) familiar with Euclidean geometry and the
natural ``physical'' spaces like $\mathbb{R}^2$ (the plane)
and $\mathbb{R}^3$ (the three-dimensional space). The
notion of \emph{distance} is clear; \emph{orthogonality} is
intuitive and maps to the idea of a ``right angle''. Even a
more abstract concept such as that of \emph{basis} is
quite % rather
easy to %think of
contemplate (the standard coordinate concepts of
latitude, longitude and height, which correspond to the
three orthogonal axes in $\mathbb{R}^3$). Unfortunately,
immediate spatial intuition fails us for higher dimensions
(i.e.\ for $\mathbb{R}^N$ with $N>3$), yet the basic
concepts introduced for $\mathbb{R}^3$ generalize easily to
$\mathbb{R}^N$ so that it is easier to state such concepts
for the higher-dimensional case and specialize them with
examples for $N=2$ or $N=3$. These notions, ultimately, will
be generalized even further to more abstract types of vector
spaces. For the moment, let us review the properties of
$\mathbb{R}^N$, the $N$-dimensional Euclidean space.
\itempar{Vectors and Notation.}\index{vector space|(}
A point in $\mathbb{R}^N$ is specified by an $N$-tuple of
coordinates:\footnote{$N$-dimensional vectors are by default