Page MenuHomec4science
Files F104939240

99-vectorsOrig.tex
No OneTemporary
Actions

File Metadata

Created
Thu, Mar 13, 12:56

99-vectorsOrig.tex
View Options

\chapter{Signals and Hilbert Spaces}\label{ChLinalg}
In the $17$th century, algebra and geometry started to
interact in a fruitful synergy which continues to the
present day. Descartes's original idea of translating
geometric constructs into algebraic form spurred a new line
of attack in mathematics; soon, a series of astonishing
results was produced for a number of problems which had long
defied geometrical solutions (such as, famously, the
trisection of the angle). It also spearheaded the notion of
vector space, in which a geometrical point could be
represented as an $n$-tuple of coordinates; this, in turn,
readily evolved into the theory of linear algebra. Later,
the concept proved useful in the opposite direction: many
algebraic problems could benefit from our innate geometrical
intuition once they were cast in vector form; from the easy
three-dimensional visualization of concepts such as distance
and orthogonality, more complex algebraic constructs could
be brought within the realm of intuition. The final leap of
imagination came with the realization that the concept of
vector space could be applied to much more abstract entities
such as infinite-dimensional objects and functions. In so
doing, however, spatial intuition could be of limited help
and %so
for this reason, the notion of vector space had to be formalized in
much more rigorous terms; we will see that the definition of
Hilbert space is one such formalization.
Most of the signal processing theory which
%we will study in the course
in this book
can be usefully cast in terms of vector notation
and the advantages of this approach are exactly what we have
just delineated.
%before.
Firstly of all, all the standard machinery
of linear algebra becomes immediately available and
applicable; this greatly simplifies the formalism used in
the mathematical proofs which will follow and, at the same
time, it fosters a good intuition with respect to the
underlying principles which are being put in place.
Furthermore, the vector notation creates a frame of thought
which seamlessly links the more abstract results involving
infinite sequences to the algorithmic reality involving
finite-length signals. Finally, on the practical side,
vector notation is the standard paradigm for numerical
analysis packages such as Matlab; signal processing
algorithms expressed in vector notation translate to working
code with very little effort.
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 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
\emph{column} vectors.}
\[
\mathbf{x} = \left[ \begin{array}{c}
x_0 \\ x_1 \\ \vdots \\ x_{N-1} \end{array} \right] =
[ \begin{matrix} x_0 & x_1 & \ldots & x_{N - 1} \end{matrix} ]^T
\]
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.}
The vector
$\mathbf{0} = [ \begin{matrix} 0 & 0 & \ldots & 0 \end{matrix}]^T$,
i.e.\ the null vector, is considered the
origin of the coordinate system.
The generic $n$-th element in vector $\mathbf{x}$ is
indicated by the subscript $\mathbf{x}_n$. In the following
we will often consider a \emph{set} of $M$ arbitrarily
chosen vectors in $\mathbb{R}^N$ and this set will be
indicated by the notation
$\bigl\{\mathbf{x}^{(k)} \bigr\}_{k = 0 \, \ldots\, M- 1}$.
Each vector in the set is indexed by the
superscript $\cdot^{(k)}$. The $n$-th element of the $k$-th
vector in the set is indicated by the notation
$\mathbf{x}^{(k)}_n$
\medskip \medskip
\itempar{Inner Product.}\index{inner product|mie}
The inner product between two vectors $\mathbf{x},
\mathbf{y} \in \mathbb{R}^N$ is defined as
\begin{equation}\label{eq:mb.1}
\langle \mathbf{x}, \mathbf{y} \rangle = \sum_{n = 0}^{ N - 1} x_n y_n
\end{equation}
We say that $\mathbf{x}$ and $\mathbf{y}$ are orthogonal,
or $\mathbf{x} \perp \mathbf{y}$, when their inner
product is zero:\index{vector!orthogonality}
\begin{equation}\label{eq:mb.2}
\mathbf{x} \perp \mathbf{y} \; \Longleftrightarrow \;
\langle \mathbf{x}, \mathbf{y} \rangle = 0 \end{equation}
\itempar{Norm.}
The norm\index{vector!norm} of a vector is defined in terms of the inner product as
\begin{equation}\label{eq:mb.3}
\| \mathbf{x} \|_2 = \sqrt{ \sum_{n = 0}^{N - 1} x_n^2 } =
\langle \mathbf{x}, \mathbf{x} \rangle^{ 1/2}
\end{equation}
It is easy to visualize geometrically that the norm of a
vector corresponds to its length, i.e.\ to the distance
between the origin and the point identified by the vector's
coordinates. A remarkable property linking the inner product
and the norm is the Cauchy-Schwarz inequality
%(whose proof is a little tricky)
(the proof of which is %rather complicated
nontrivial); given $\mathbf{x}, \mathbf{y} \in
\mathbb{R}^N$ we %\emph{always} have:
can state that
\[
\bigl| \langle \mathbf{x}, \mathbf{y} \rangle \bigr|
\leq \| \mathbf{x} \|_{2} \, \| \mathbf{y} \|_{2}
\]
\itempar{Distance.}
The concept of norm is used to introduce the notion of
Euclidean \emph{distance}\index{vector!distance} between two
vectors $\mathbf{x}$ and $\mathbf{y}$:
\begin{equation}\label{eq:mb.4}
d(\mathbf{x}, \mathbf{y}) = \| \mathbf{x} - \mathbf{y} \|_2
= \sqrt{ \sum_{n = 0}^{ N - 1} (x_n - y_n)^2}
\end{equation}
%% 3.1 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{figure}[h]
\center\small
\psset{unit=2cm,linewidth=1.2pt}
\begin{tabular}{ccc}
\begin{pspicture}(-.1,-.1)(1.5,1.1)
\psset{labelsep=2pt}
\psframe[linewidth=0.8pt](0,0)(0.2,0.2)
\psline{->}(0,1) \uput[u](0,1){$\mathbf{y}$}
\psline{->}(1,0) \uput[r](1,0){$\mathbf{x}$}
\end{pspicture}
&
\begin{pspicture}(-.1,-.1)(1.5,1.1)
\psset{labelsep=2pt}
\psline{->}(.3,.8) \uput[u](.3,.8){$\mathbf{y}$}
\psline{->}(.9,.2) \uput[r](.9,.2){$\mathbf{x}$}
\psline[linecolor=gray]{->}(.3,.8)(.9,.2) \rput(.8,.6){$\mathbf{x-y}$}
\end{pspicture}
&
\begin{pspicture}(-.1,-.1)(1.5,1.1)
%\psframe[linewidth=0.8pt](0,0)(0.2,0.2)
\psset{labelsep=2pt}
\psline{->}(0,1) \uput[u](0,1){$\mathbf{y}$}
\psline{->}(1,0) \uput[r](1,0){$\mathbf{x}$}
\psline[linecolor=lightgray,linestyle=dashed](1,0)(1,1)
\psline[linecolor=gray]{->}(1,1) \uput[u](1,1){$\mathbf{z=x+y}$}
\end{pspicture}
\end{tabular}
\vskip-5mm
\caption{Elementary properties of vectors in
$\mathbb{R}^2$: orthogonality of two vectors $\mathbf{x}$ and
$\mathbf{y}$ (left);
difference vector $\mathbf{x} - \mathbf{y}$ (middle);
sum of two orthogonal vectors
$\bz = \mathbf{x} + \mathbf{y}$, also known as Pythagorean theorem
(right).}\label{fi:elementary_properties}
\vskip-1mm
\end{figure}
From this, we can easily derive the Pythagorean theorem for
$N$ dimensions: if two vectors are orthogonal, $\mathbf{x}
\perp \mathbf{y}$, and we consider the sum vector $\bz =
\mathbf{x} +
\mathbf{y}$, we have %:
\begin{equation}\label{eq:mb.5}
\| \bz \|_{2}^{2} = \| \mathbf{x} \|_{2}^{2} + \| \mathbf{y} \|_{2}^{2}
\end{equation}
The above properties are graphically shown in
Figure~\ref{fi:elementary_properties} for $\mathbb{R}^2$.
%\vskip2mm
\itempar{Bases.}\index{vector space!basis}\index{basis (vector space)}
Consider a set of $M$ arbitrarily chosen vectors in
$\mathbb{R}^N$: $\{\mathbf{x}^{(k)} \}_{k = 0 \ldots M- 1}$.
Given such a set, a key question is that of completeness:
can \emph{any} vector in $\mathbb{R}^N$ be written as a
linear combination of vectors from the set? In other words,
we ask ourselves whether, for any $\mathbf{z} \in
\mathbb{R}^{N}$, we can find a set of $M$ coefficients
$\alpha_k \in \mathbb{R}$ such that $\mathbf{z}$ can be
expressed as
\begin{equation}\label{eq:mb.6}
\mathbf{z} = \sum_{k = 0}^{M - 1} \alpha_k \mathbf{x}^{(k)}
\end{equation}
Clearly, $M$ needs to be greater or equal to $N$, but what
conditions does a set of vectors $\{ \mathbf{x}^{(k)} \}_{k
= 0 \ldots M - 1}$ need to satisfy so that (\ref{eq:mb.6})
holds for any $\mathbf{z} \in \mathbb{R}^N$? There needs to
be a set of $M$ vectors that \emph{span} $\mathbb{R}^N$, and
it can be shown that this is equivalent to saying that the
set must contain at least $N$ \emph{linearly independent}
vectors. In turn, $N$ vectors $\{ \mathbf{y}^{(k)} \}_{k = 0
\ldots N - 1}$ are linearly independent if the equation
\begin{equation}\label{eq:mb.7}
\sum_{k = 0}^{N - 1} \beta_k \mathbf{y}^{(k)} = 0
\end{equation}
is satisfied only when all the $\beta_k$'s are zero. A set
of $N$ linearly independent vectors for $\mathbb{R}^N$ is
called a \emph{basis} and, amongst bases, the ones with
mutually orthogonal vectors of
norm equal to one are called \emph{orthonormal
bases}\index{basis (vector space)!orthonormal}\index{orthonormal basis}.
For an orthonormal basis $\{
\mathbf{y}^{(k)} \}$ we therefore have
\begin{equation}
\bigl\langle \mathbf{y}^{(k)}, \mathbf{y}^{(h)} \bigr\rangle =
\left \{ \!
\begin{array}{ll}
1 & \mbox{ if } k = h \\
0 & \mbox{ otherwise}
\end{array}
\right.
\end{equation}
Figure~\ref{fi:linear_independence} %\pagebreak
reviews the above concepts in low dimensions.\index{basis (vector space)|)}\index{vector space|)}
\eject
%%
%% 3.2 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{figure}[h]
\vskip-9mm
\center\small
\psset{unit=3cm}
\begin{pspicture}(-1.5,-.8)(1.5,1.8)
\psset{Alpha=45,linewidth=1pt,labelsep=2pt}
\pstThreeDCoor[linecolor=black,linewidth=1pt,%
xMax=1.5,yMax=1.5,zMax=1.5,%
xMin=-.2,yMin=-.2,zMin=-.2,%
nameX=$\mathbf{x}^{(0)}$,
nameY=$\mathbf{x}^{(1)}$,
nameZ=$\mathbf{x}^{(3)}$]
\pstThreeDLine[linestyle=dashed,linewidth=0.5pt](0,.5,0)(1,.5,0)
\pstThreeDLine[linestyle=dashed,linewidth=0.5pt](1,.5,0)(1,0,0)
\pstThreeDLine{->}(0,0,0)(1,.5,0)
\pstThreeDPut(1.13,.63,0){$\mathbf{x}^{(2)}$}
\end{pspicture}
\vskip-5mm
\caption{Linear independence and bases:
$\mathbf{x}^{(0)}$, $\mathbf{x}^{(1)}$ and $\mathbf{x}^{(2)}$
are coplanar in $\mathbb{R}^3$ and,
therefore,
they do not form a basis; conversely,
$\mathbf{x}^{(3)}$ and any two of $\{ \mathbf{x}^{(0)},
\mathbf{x}^{(1)}, \mathbf{x}^{(2)} \}$ are linearly
independent.}\label{fi:linear_independence}
\end{figure}
\medskip \medskip
The standard orthonormal basis for $\mathbb{R}^N$ is the
\emph{canonical basis}
$\bigl\{ \boldsymbol{\delta}^{(k)} \bigr\}_{k = 0 \ldots N - 1}$
with
\[
\boldsymbol{\delta}^{(k)}_n = \delta[n-k] =
\left \{\!
\begin{array}{ll}
1 & \mbox{ if } n = k \\
0 & \mbox{ otherwise}
\end{array}
\right.
\]
The orthonormality of such a set is immediately apparent.
Another important orthonormal basis for $\mathbb{R}^N$ is
the normalized \emph{Fourier basis}\index{basis (vector
space)!Fourier}\index{Fourier basis}
$\{ \mathbf{w}^{(k)} \}_{k = 0 \ldots N - 1}$ for which
\[
\mathbf{w}^{(k)}_n = \frac{1}{\sqrt{N}}\, e^{-j\frac{2\pi}{N}nk}
\]
The orthonormality %proof for the basis is left as an exercise
of the basis will be proved in the next Chapter.
\medskip\smallskip \medskip
\section{From Vector Spaces to Hilbert Spaces}\index{Hilbert space|(}
\noindent
The purpose of the previous Section was to briefly review the
elementary notions and spatial intuitions of Euclidean
geometry. A thorough study of vectors in $\mathbb{R}^N$ and
$\mathbb{C}^N$ is the subject of linear algebra; yet, the
idea of vectors, orthogonality and bases is much more
general, the basic ingredients being an inner product and
the use of a square norm as in (\ref{eq:mb.3}).
While the analogy between vectors in $\mathbb{C}^N$ and
length-$N$ signal is readily apparent, the question now
hinges on how we are to proceed in order to generalize the
above concepts to the class of infinite sequences.
Intuitively, for instance, we can let $N$ grow to infinity
and obtain $\mathbb{C}^\infty$ as the Euclidean space for
infinite sequences; in this case, however, much care must be
exercised with expressions such as~(\ref{eq:mb.1})
and~(\ref{eq:mb.3}) which can diverge for sequences as
simple as $x[n] = 1$ for all~$n$. In fact, the proper
generalization of $\mathbb{C}^N$ to an infinite number of
dimensions is in the form of a particular vector space
called \emph{Hilbert space\/}; the structure of this kind of
vector space imposes a set of constraints on its elements so
that divergence problems, such as the one we just mentioned,
no longer bother us. When we embed infinite sequences into a
Hilbert space, these constraints translate to the condition
that the corresponding signals have finite energy -- which
is a mild and reasonable requirement.
Finally, it is important to remember that the notion of Hilbert
space is applicable to much more general vector spaces than
$\mathbb{C}^N$; for instance, we can easily consider spaces
of functions over an interval or over the real line. This
generality is actually the cornerstone of a branch of
mathematics called \emph{functional analysis}. While we will
not %tread very far into caves
follow in great depth
these kinds of generalizations, we
will certainly point out a few of them along the way. The
space of square integrable functions, for instance, will
turn out to be a marvelous tool a few Chapters from now
when, finally, the link between
continuous---and discrete---time signals will be explored in detail.
\medskip \medskip
\subsection{The Recipe for Hilbert Space}
A word of caution: we are now starting to operate in a world
of complete abstraction. Here a vector is an entity
\emph{per se} and, while analogies and examples in terms of
Euclidean geometry can be useful visually, they are, by no
means, exhaustive. In other words: vectors are no longer just
$N$-tuples of numbers; they can be anything. This said, a
Hilbert space can be defined in incremental steps starting
from a general notion of vector space and by supplementing
this space with two additional features: the existence of an
inner product and the property of completeness.
\itempar{Vector Space.}
Consider a set of vectors $V$ and a set of scalars $S$
(which can be either $\mathbb{R}$ or $\mathbb{C}$ for our
purposes). A vector space $H(V,S)$ is completely defined by
the existence of a vector addition operation and a scalar
multiplication operation which satisfy the following
properties for any $\mathbf{x, y, z,} \in V$ and any
$\alpha, \beta \in S$:
\begin{itemize}
\item Addition is commutative:
\begin{equation}\label{eq:mb.8}
\mathbf{x + y = y + x}
\end{equation}
\item Addition is associative:
\begin{equation}\label{eq:mb.9}
\mathbf{(x + y) + z = x + (y + z) }
\end{equation}
\item Scalar multiplication is distributive:
\begin{equation}\label{eq:mb.11}
\alpha \mathbf{(x + y)} = \alpha \mathbf{x} + \alpha \mathbf{y}
\end{equation}
\begin{equation}\label{eq:mb.12}
(\alpha + \beta) \mathbf{x} = \alpha \mathbf{x} + \beta \mathbf{x}
\end{equation}
\begin{equation}\label{eq:mb.12bis}
\alpha(\beta \mathbf{x}) = (\alpha\beta) \mathbf{x}
\end{equation}
\item There exists a null vector $\mathbf{0}$ in $V$ which
is the additive identity so that $\forall\; \mathbf{x} \in
V$:
\begin{equation}\label{eq:mb.13}
\mathbf{x + 0 = 0 + x = x}
\end{equation}
\item $\forall\; \mathbf{x} \in V$ there exists in $V$ an
additive inverse $\mathbf{-x}$ such that
\begin{equation}\label{eq:mb.14}
\mathbf{x + (-x) = (-x) + x = 0}
\end{equation}
%
\item There exists an identity element ``$1$'' for
\emph{scalar} multiplication so that $\forall\; \mathbf{x}
\in V$:
\begin{equation}\label{eq:mb.15}
1 \cdot \mathbf{x} = \mathbf{x} \cdot 1 = \mathbf{x}
\end{equation}
\end{itemize}
\medskip \medskip
\itempar{Inner Product Space.}
What we have so far is the simplest type of vector space;
the next ingredient which we %will
consider is the
\emph{inner product} which is essential to build a notion of
\emph{distance} between elements in a vector space. A vector
space with an inner product is called an inner product
space. An inner product for $H(V, S)$ is a function from $V
\times V$ to $S$ which satisfies the following properties
for any $\mathbf{x, y, z,} \in V$:
\begin{itemize}
\item It is \emph{distributive} with respect to vector addition:
\begin{equation}\label{eq:mb.16}
\langle \mathbf{ x} + \mathbf{ y}, \mathbf{ z} \rangle
= \langle \mathbf{ x}, \mathbf{ z } \rangle +
\langle \mathbf{ y}, \mathbf{ z} \rangle
\end{equation}
\item It possesses the \emph{scaling property} with respect
to scalar multiplication\footnote{Note that in our notation,
the left operand is conjugated.}:
\begin{equation}\label{eq:mb.17}
\langle \mathbf{x}, \alpha \mathbf{y} \rangle =
\alpha \langle \mathbf{ x}, \mathbf{y} \rangle
\end{equation}
\begin{equation}\label{eq:mb.18}
\langle \alpha \mathbf{x}, \mathbf{y} \rangle =
\alpha^* \langle \mathbf{x}, \mathbf{y} \rangle
\end{equation}
%
\item It is commutative within complex conjugation:
\begin{equation}\label{eq:mb.19}
\langle \mathbf{x}, \mathbf{y} \rangle =
\langle \mathbf{y}, \mathbf{x} \rangle^*
\end{equation}
%
\item The self-product is positive:
\begin{equation}\label{eq:mb.20}
\langle \mathbf{ x},\mathbf{ x}\rangle \geq 0
\end{equation}
\begin{equation}\label{eq:mb.21}
\langle \mathbf{ x},\mathbf{ x} \rangle = 0
\; \Longleftrightarrow \; \mathbf{x = 0}.
\end{equation}
\end{itemize}
From this definition of the inner product, a series of
additional definitions and properties can be derived: first
of all, orthogonality between two vectors is defined with
respect to the inner product, and we %will
say that the non-zero
vectors $\mathbf{x}$ and $\mathbf{y}$ are orthogonal, or
$\mathbf{x \perp y}$, if and only if
\begin{equation}\label{eq:mb.27}
\langle \mathbf{x}, \mathbf{ y} \rangle = 0
\end{equation}
From the definition of an inner product, we can define the
\emph{norm} of a vector as (we will omit from now on the
subscript $ 2 $ from the norme symbol):
\begin{equation}\label{eq:mb.22}
\Vert \mathbf{x}\Vert = \langle \mathbf{x}, \mathbf{ x} \rangle ^{1/2}
\end{equation}
In turn, the norm satisfies the \emph{Cauchy-Schwartz
inequality\/}:
\begin{equation}\label{eq:mb.25}
\bigl| \langle \mathbf{x}, \mathbf{ y} \rangle \bigr|
\leq \| \mathbf{x} \| \cdot \| \mathbf{y} \|
\end{equation}
with strict equality if and only if $\mathbf{x} = \alpha
\mathbf{y}$. The norm also satisfies the \emph{triangle
inequality\/}:
\begin{equation}\label{eq:mb.26}
\| \mathbf{x} + \mathbf{ y} \| \leq \| \mathbf{x} \| + \| \mathbf{y} \|
\end{equation}
with strict equality if and only if
$\mathbf{x} = \alpha \mathbf{y}$ and $\alpha \in \mathbb{R}^+$. For orthogonal
vectors, the triangle inequality becomes the famous
Pythagorean theorem:
\begin{equation}\label{eq:mb.28}
\| \mathbf{x} + \mathbf{ y} \|^2 =
\| \mathbf{x} \|^2 + \| \mathbf{y} \|^2
\quad\qquad \mbox{for } \mathbf{x \perp y}
\end{equation}
\itempar{Hilbert Space.}
A vector space $H(V, S)$ equipped with an inner product is
called an inner product space. To obtain a Hilbert
\pagebreak%
space, we need completeness\index{Hilbert space!completeness}.
This is a slightly more technical
notion, which essentially implies that convergent sequences
of vectors in $V$ have a limit that is also in $V$. To gain
intuition, think of the set of rational numbers $\mathbb{Q}$
versus the set of real numbers $\mathbb{R}$.
The set of rational numbers is incomplete, because there are convergent
sequences in $\mathbb{Q}$ which converge to irrational
numbers. The set of real numbers contains these irrational
numbers, and is in that sense the completion of
$\mathbb{Q}$. Completeness is usually hard to prove in the
case of infinite-dimensional spaces; in the following
%Section
it will be tacitly assumed and the interested reader can easily
find the relevant proofs in advanced analysis textbooks.
%As a last technicality
Finally, we will also only consider
\emph{separate} Hilbert spaces, which are the ones that
admit orthonormal bases.
\medskip
\subsection{Examples of Hilbert Spaces}\label{vsex}
\itempar{Finite Euclidean Spaces.}
The vector space $\mathbb{C}^N$, with the ``natural''
definition for the sum of two vectors $\mathbf{z=x+y}$ as
\begin{equation}\label{euclidsum}
z_n = x_n + y_n
\end{equation}
and the definition of the inner product as
\begin{equation}
\langle \mathbf{x}, \mathbf{y} \rangle =
\sum_{n = 0}^{ N - 1} x^*_n y_n
\end{equation}
is a Hilbert space.
\medskip
\itempar{Polynomial Functions.}
An example of ``functional'' Hilbert space is the vector
space $\mathbb{P}_N \bigl([0, 1] \bigr)$
of polynomial functions on the
interval $[0, 1]$ with maximum degree $N$. It is a good
exercise to show that $\mathbb{P}_\infty \bigl([0, 1] \bigr)$ is not
complete; consider for instance the sequence of polynomials
\[
p_n(x) = \sum_{k = 0}^{n} \frac{x^k}{k!}
\]
This series converges as $p_n(x) \rightarrow e^x \not\in
\mathbb{P}_\infty\bigl([0, 1] \bigr)$.
\medskip
\itempar{Square Summable Functions.}
Another interesting example of functional Hilbert space is
the space of \emph{square integrable functions} over a
finite interval. For instance,
$L_2 \bigl( [-\pi, \pi] \bigr)$ is the
space of real or complex functions on the interval
$[-\pi, \pi]$ which have a finite norm. The inner product over
$L_2 \bigl([-\pi, \pi] \bigr)$ is defined as
\begin{equation}\label{eq:mb.24}\label{l2piInnerProduct}
\langle f, g \rangle = \int_{-\pi}^{\pi} f^*(t) g(t)\, dt
\end{equation}
so that the norm of $f(t)$ is
\begin{equation}\label{eq:mb.31}
\| f \| = \sqrt{\int_{-\pi}^{\pi} \bigl|f(t) \bigr|^2 \, dt}
\end{equation}
For $f(t)$ to belong to
$L_2 \bigl([-\pi, \pi] \bigr)$ it must be
$\| f \| < \infty$\index{Hilbert space|)}.
\subsection{Inner Products and Distances}
The inner product is a fundamental tool in a vector space
since it allows us to introduce a notion of \emph{distance}
between vectors. The key intuition about this is a typical
instance in which a geometric construct helps us to generalize
a basic idea to much more abstract scenarios. Indeed, take
the simple Euclidean space $\mathbb{R}^N$ and a given vector
$\mathbf{x}$; for any vector $\mathbf{y} \in \mathbb{R}^N$
the inner product $\langle \mathbf{x}, \mathbf{ y} \rangle$ is the
measure of the \emph{orthogonal projection} of $\mathbf{y}$
over $\mathbf{x}$. We know that the orthogonal projection
defines the point on $\mathbf{x}$ which is closest to
$\mathbf{y}$ and therefore this indicates
%``
how well %''
we can approximate\index{inner product!approximation by}
$\mathbf{y}$ by a simple scaling of $\mathbf{x}$.
%To see this, just note that
To illustrate this, it should be noted that
\[
\langle \mathbf{x, y} \rangle
= \| \mathbf{x} \| \, \| \mathbf{y} \| \cos \theta
\]
where $\theta$ is the angle between the two vectors (you can
work out the expression in $\mathbb{R}^2$ to easily
convince yourself %you
of this; the result generalizes to any other dimension).
Clearly, if the vectors are orthogonal, the cosine is zero
and no approximation %will be
is possible. Since the inner
product is dependent on the angular separation between the
vectors, it represents a first rough measure of similarity
between $\mathbf{x}$ and $\mathbf{y}$; in broad terms, it
provides a measure of the difference in \emph{shape} between
vectors.
In the context of signal processing, this is particularly
relevant since
most of the times, we are interested in the difference in
%the difference in ``
shape'' between signals.
%%%%is what we are interested in most of the time.
As we have
%stated several times
said before, discrete-time signals \emph{are}
vectors; the computation of their inner product will assume
different names according to the processing context in which
we find ourselves%in
: it will be called \emph{filtering}, when we
are trying to approximate or modify a signal %;
or it will be
called \emph{correlation} when we are trying to detect one
particular signal amongst many. Yet, in all cases, it will
still be an inner product, i.e.\ a \emph{qualitative}
measure of similarity between vectors. In particular, the
concept of orthogonality between signals implies that the
signals are perfectly distinguishable or, in other words,
that their shape is completely different.
%\vspace{1ex}
The need for a \emph{quantitative} measure of similarity in
some applications calls for the introduction of the
Euclidean distance, which is derived from the inner product
as\index{inner product!Euclidean distance}
\begin{equation}
d(\mathbf{x},\mathbf{y})
= \langle \mathbf{x} - \mathbf{y}, \mathbf{x} - \mathbf{y} \rangle ^{1/2}
= \|\mathbf{x} - \mathbf{y}\|
\end{equation}
In particular, for $\mathbb{C}^N$ the Euclidean distance is
defined by the expression:
\begin{equation}\label{eucliddist}
d(\mathbf{x}, \mathbf{y} ) =
\sqrt{\sum_{n=0}^{N-1} |x_n - y_n|^2}
\end{equation}
whereas for $L_2 \bigl( [-\pi, \pi ] \bigr)$ we have
\begin{equation}
d(\mathbf{x}, \mathbf{y}) =
\sqrt{\int_{-\pi}^{\pi} \bigl| x(t) - y(t) \bigr|^2 \, dt}
\end{equation}
In the practice of signal processing, the Euclidean distance
is referred to as the \emph{root mean square
error\/};\footnote{Almost always, the square distance is
considered instead; its name is then the \emph{mean square
error}, or MSE.}
this is a global, quantitative goodness-of-fit
measure when trying to approximate signal $\mathbf{y}$
with $\mathbf{x}$.
Incidentally, there are other types of distance measures
which do not rely on a notion of inner product; for example
in $\mathbb{C}^N$ we could define
\begin{equation}
d(\mathbf{x} , \mathbf{y})
= \max_{0 \leq n < N} | \mathbf{x}_n - \mathbf{y}_n |
\end{equation}
This distance is based on the supremum norm and is usually
indicated by $\|\mathbf{x} - \mathbf{y}\|_\infty$; however,
it can be shown that there is no inner product from which
this norm can be derived and therefore no Hilbert space can
be constructed where $\| \,\cdot \,\|_\infty$ is the natural norm.
Nonetheless, this norm will reappear later, in the context
of optimal filter design.
%%S3.3
\section{Subspaces, Bases, Projections}\index{basis (vector space)|(}
Now that we have defined the properties of Hilbert space, it
is only natural to start looking at the consequent inner
\emph{structure} of such a space. The best way to do so is
by introducing the concept of \emph{basis}. You can think of
a basis as the ``skeleton'' of a vector space, i.e.{} a structure
which holds everything together; yet, this skeleton is
flexible and we can twist it, stretch it and rotate it in
order to highlight some particular structure of the space
and %bring out the
facilitate access to particular information
%we are interested in
that we may be seeking.
All this is accomplished by a linear transformation
called a \emph{change of basis\/}; to anticipate the topic of
the next Chapter, we will see shortly that the Fourier
transform is an instance of basis change.
Sometimes, we %will be
are interested in exploring in more detail
a specific subset of a given vector space; this is
accomplished via the concept of \emph{subspace}. A subspace
is, as the name implies, a restricted region of the global
space, with the additional property that it is
\emph{closed} under the usual vector operations. This
implies that, once in a subspace, we can operate freely
without ever leaving its confines; just like a full-fledged
space, a subspace has its own skeleton (i.e.\ the basis)
and, again, we can exploit the properties of this basis to
highlight the features %we are interested in
that interest us.
\subsection{Definitions}
Assume $H(V, S)$ is a Hilbert space, with $V$ a vector space
and $S$ a set of scalars (i.e.\ $\mathbb{C}$).
\itempar{Subspace.}\index{basis (vector space)!subspace}
A subspace of $V$ is defined as a subset $P \subseteq V$
that satisfies the following properties:
\begin{itemize}
\item Closure under addition, i.e.
\begin{equation}\label{eq:mb.35}
\forall\;\mathbf{x}, \mathbf{y} \in P \;
\Rightarrow \; \mathbf{x} + \mathbf{y} \in P
\end{equation}
\item Closure under scalar multiplication, i.e.
\begin{equation}\label{eq:mb.36}
\forall\;\mathbf{x} \in P ,\;\, \forall\;\alpha \in S
\; \Rightarrow \; \alpha \mathbf{x} \in P
\end{equation}
\end{itemize}
Clearly, $V$ is a subspace of itself.
\itempar{Span.}\index{basis (vector space)!span}
Given an arbitrary set of $M$ vectors
$W = \bigl\{ \mathbf{x}^{(m)} \bigr\}_{m =0,1,\ldots, M-1}$,
the \emph{span} of these vectors is defined as
\begin{equation}\label{eq:mb.34}
\mbox{span}(W) = \left\{ \sum_{m=0}^{M-1} \alpha_m \mathbf{x}^{(m)}\right\},
\qquad \quad \alpha_m \in S
\end{equation}
i.e.\ the span of $W$ is the set of all possible linear
combinations of the vectors in $W$. The set of vectors $W$
is called \emph{linearly independent} if the following
holds:
\begin{equation}\label{eq:mb.32}
\sum_{m=0}^{M-1} \alpha_m \mathbf{x}^{(m)} = 0 \;
\Longleftrightarrow \; \alpha_m = 0
\qquad \quad \mbox{ for } m =0,1,\ldots, M-1
\end{equation}
\itempar{Basis.}
A set of $K$ vectors
$W = \bigl\{ \mathbf{x}^{(k)} \bigr\}_{k
=0,1,\ldots, K-1}$ from a subspace $P$ is a \emph{basis}
for that subspace if %:
\begin{itemize}
\item The set $W$ is linearly independent.
\item Its span covers $P$, i.e.\ $\mbox{span}(W) = P$.
\end{itemize}
The last statement affirms that any $\mathbf{y} \in P$ can
be written as a linear combination of $ \bigl\{\mathbf{x}^{(k)}
\bigr\}_{k =0,1,\ldots, K-1}$ or that, for all $\mathbf{y} \in
P$, there exist $K$ coefficients $\alpha_k$ such that
\begin{equation}\label{eq:mb.38}
\mathbf{y} = \sum_{k=0}^{K-1} \alpha_k \mathbf{x}^{(k)}
\end{equation}
%this
which is equivalently expressed by saying that the set $W$
is \emph{complete} in $P$.
\itempar{Orthogonal/Orthonormal Basis.}\index{basis (vector space)|orthonormal|(}
An orthonormal basis for a subspace $P$ is a set of $K$
basis vectors $W = \bigl\{ \mathbf{x}^{(k)} \bigr\}_{k =0,1,\ldots, K-
1}$ for which
\begin{equation}\label{eq:mb.39}
\bigl\langle \mathbf{x}^{(i)}, \mathbf{x}^{(j)} \bigr\rangle
= \delta[i - j] \qquad \quad 0 \leq i, j < K
\end{equation}
which means orthogonality across vectors and unit norm.
Sometimes, %we can have that
the set of vectors %is
can be
orthogonal but not normal (i.e.\ the norm of the vectors is not
unitary). This is %hardly
not a problem provided that we remember
to include the appropriate normalization factors in the
analysis and/or synthesis formulas. Alternatively, an
%orthogonal
lineary idependent
set of vectors can be orthonormalized via the
Gramm-Schmidt procedure, which
%you can find
can be found in any linear algebra textbook.
Among all bases, \emph{orthonormal bases} are the most ``beautiful''
%in some sense
in a way because of their structure and their properties.
One of the most important properties for finite-dimensional
spaces is the following:
\begin{itemize}
\item A set of $N$ orthogonal vectors in an $N$-dimensional
subspace is a basis for the subspace.
\end{itemize}
In other words, in finite dimensions, once we find a full
set of orthogonal vectors, we are sure that the set spans the
space.
\subsection{Properties of Orthonormal Bases}\label{ssecOrtBas}
Let $W = \bigl\{ \mathbf{x}^{(k)} \bigr\}_{k =0,1,\ldots, K-1}$
be an orthonormal basis for a (sub)space $P$. Then the following
properties (all of which are easily verified) hold:
\itempar{Analysis Formula.}
The coefficients in the linear combination~(\ref{eq:mb.38}) are obtained simply as
\begin{equation}\label{eq:mb.41}
\alpha_k = \bigl\langle \mathbf{x}^{(k)}, \mathbf{y} \bigr\rangle
\end{equation}
The coefficients $\{ \alpha_k \}$ are called the
\emph{Fourier coefficients}\footnote{Fourier coefficients
often refer to the particular case of Fourier series.
However, the term generally refers to coefficients in any
orthonormal basis.} of the orthonormal expansion of
$\mathbf{y}$ with respect to the basis $W$
and~(\ref{eq:mb.41}) is called the Fourier \emph{analysis
formula\/}; conversely, Equation~(\ref{eq:mb.38}) is called
the \emph{synthesis formula}.
\itempar{Parseval's Identity}\index{Parseval's identity}
For an orthonormal basis, there is a norm conservation
property given by \emph{Parseval's identity}:
\begin{equation}\label{eq:mb.42}
\| \mathbf{y} \|^2 =
\sum_{k=0}^{K-1} \left|
\bigl\langle \mathbf{x}^{(k)}, \mathbf{y} \bigr\rangle \right|^2
\end{equation}
For physical quantities, the norm is dimensionally
equivalent to a measure of energy; accordingly, Parseval's
identity is also known as the \emph{energy conservation
formula}.
\smallskip
\itempar{Bessel's Inequality.}\index{Bessel's inequality}
The generalization of Parseval's equality is \emph{Bessel's
inequality}. In our subspace $P$, consider a set of $L$
orthonormal vectors $G \subset P$ (a set which is not
necessarily a basis since it may be $L < K$), with
$G = \bigl\{
\mathbf{g}^{(l)} \bigr\}_{l=1, 2, \ldots L-1}$; then the norm of
any vector $\mathbf{y} \in P$ is lower bounded as :
\begin{equation}\label{eq:mb.43}
\| \mathbf{y} \|^2 \geq \sum_{l=0}^{L-1}
\left| \bigl\langle \mathbf{g}^{(l)}, \mathbf{y} \bigr\rangle \right|^2
\end{equation}
and the lower bound is reached for all $\mathbf{y}$ if and
only if the system $G$ is complete, that is, if it is an
orthonormal basis for $P$.
\smallskip
\itempar{Best Approximations.}
Assume $P$ is a subspace of $V$; if we try to approximate a
vector $\mathbf{y} \in V$ by a linear combination of basis
vectors from the subspace $P$, then we are led to the
concepts of least squares approximations and orthogonal
projections. First of all, we define the \emph{best} linear
approximation $\hat{\mathbf{y}} \in P$ of a general vector
$\mathbf{y} \in V$ to be the approximation which minimizes
the norm $\| \mathbf{y} - \hat{\mathbf{y}} \|$. Such
approximation is easily obtained by projecting $\mathbf{y}$
onto an orthonormal basis for $P$, as shown in
Figure~\ref{fi:orthogonal_projection}.
With $W$ as
our usual orthonormal basis for $P$, the projection
is given by
\begin{equation}\label{eq:mb.44}
\hat{\mathbf{y}} = \sum_{k=0}^{K-1}
\bigl\langle \mathbf{x}^{(k)}, \mathbf{y} \bigr\rangle
\mathbf{x}^{(k)}
\end{equation}
Define the approximation error as the vector $\mathbf{d} =
\mathbf{y} - \hat{\mathbf{y}}\,$; it can be easily shown that:
\begin{itemize}
\item The error is orthogonal to the approximation, i.e.\
$\mathbf{d} \perp \hat{\mathbf{y}}$.
\item The approximation minimizes the error square norm, i.e.
\begin{equation}\label{eq:mb.47}
\arg\min_{\hat{\mathbf{y} } \in P}
\|\mathbf{y} - \hat{\mathbf{y}} \|_2 = \mathbf{d}
\end{equation}
\end{itemize}
This approximation with an orthonormal basis has a key
property: it can be \emph{successively refined}. Assume you
have the approximation with the first $m$ terms of the
orthonormal basis:
\begin{equation}\label{eq:mb.48}
\hat{\mathbf{y}}_m =
\sum_{k = 0}^{m - 1}
\bigl\langle \mathbf{x}^{(k)}, \mathbf{y} \bigr\rangle
\mathbf{x}^{(k)}
\end{equation}
and now you want to compute the $(m + 1)$-term
approximation. This is simply given by
\begin{equation}\label{eq:mb.49}
\hat{\mathbf{y}}_{m + 1}
= \hat{\mathbf{y}}_{m} +
\bigl\langle \mathbf{x}^{(m)}, \mathbf{y} \bigr\rangle
\mathbf{x}^{(m)}
\end{equation}
While this seems obvious, it is actually a small miracle,
since it does not hold for more general, non-orthonormal
bases.\index{basis (vector space)|orthonormal|)}\index{basis (vector space)|)}
%% 2. 3 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{figure}[h]
\vskip-8mm
\center\small
\psset{unit=3cm}
\begin{pspicture}(-1.5,-.8)(1.5,1.8)
\psset{Alpha=40,linewidth=1pt,labelsep=2pt}
\pstThreeDCoor[linecolor=black,linewidth=1pt,%
xMax=1.5,yMax=1.5,zMax=1.5,%
xMin=-.2,yMin=-.2,zMin=-.2,%
nameX=$\mathbf{x}^{(0)}$,
nameY=$\mathbf{x}^{(1)}$,
nameZ=$\mathbf{x}^{(2)}$]
\pstThreeDLine[linestyle=dashed,linewidth=0.5pt](0,.5,0)(1,.5,0)
\pstThreeDLine[linestyle=dashed,linewidth=0.5pt](1,.5,0)(1,0,0)
\pstThreeDLine[linestyle=dashed,linewidth=0.5pt](1,.5,0)(1,.5,2)
\pstThreeDLine[linecolor=gray,linewidth=1.8pt]{->}(0,0,0)(1,.5,0)
\pstThreeDLine[linewidth=1.8pt]{->}(0,0,0)(1,.5,2)
\pstThreeDPut(1,.5,2.1){$\mathbf{y}$}
\pstThreeDPut(1.125,.625,0){$\hat{\mathbf{y}}$}
\end{pspicture}
\vskip-5mm
\caption{Orthogonal projection of the vector $\mathbf{y}$
onto the subspace $W$ spanned by $\{\mathbf{x}^{(0)},
\mathbf{x}^{(1)}\}$, leading to the approximation
$\hat{\mathbf{y}}$. This approximation minimizes the
square norm $\| \mathbf{y} - \hat{\mathbf{y}} \|_2$ among
all approximations belonging to $W$.}\label{fi:orthogonal_projection}
\end{figure}
%
\medskip%\smallskip
\subsection{Examples of Bases}\label{basisexample}
Considering the examples of~\ref{vsex}, we have the following:
\itempar{Finite Euclidean Spaces.}
For the simplest case of Hilbert spaces, namely
$\mathbb{C}^N$, orthonormal bases are also the most
intuitive since they contain exactly $N$ mutually orthogonal
vectors of unit norm. The classical example is the canonical
basis $ \bigl\{ \boldsymbol{\delta}^{(k)} \bigr\}_{k = 0 \ldots N - 1}$
with
\begin{equation}\label{eq:mb.50}
\boldsymbol{\delta}^{(k)}_n = \delta [n - k]
\end{equation}
but we will soon study more interesting bases such as the
Fourier basis $ \bigl\{ \mathbf{w}^{(k)} \bigr\}$, for which
\[
\mathbf{w}^{(k)}_n = e^{j\frac{2\pi}{N}nk}
\]
In $\mathbb{C}^N$, the analysis and synthesis
formulas~(\ref{eq:mb.41}) and~(\ref{eq:mb.38}) take a
particularly neat form. For any set
$ \bigl\{ \mathbf{x}^{(k)} \bigr\}$
of $N$ orthonormal vectors one can indeed arrange the
conjugates of the basis vectors\footnote{Other definitions
may build $\mathbf{M}$ by stacking the \emph{non}-conjugated
basis vectors instead; the procedure is however entirely
equivalent. Here we choose this definition in order to be
consistent with the usual derivation of the Discrete Fourier
Transform, which we will see in the next Chapter.} as the
successive rows of an $N\times N$ square matrix $\mathbf{M}$
so that each matrix element is
the conjugate of the $ n $-th element of the $ m $-th basis
vector:
\[
\mathbf{M}_{mn} = \left(\mathbf{x}^{(m)}_n \right)^*
\]
$\mathbf{M}$ is called a \emph{change of basis} matrix.
Given a vector $\mathbf{y}$, the set of expansion
coefficient $ \{ \alpha_k \}_{k = 0 \ldots N - 1}$ can now
be written \emph{itself} as a vector\footnote{This
isomorphism is rather special and at the foundation of
Linear Algebra. If the original vector space $V$ is not
$\mathbb{C}^N$, the analysis formula will always provide us
with a vector of complex values, but this vector will
\emph{not} be in $V$.} $\boldsymbol{\alpha} \in
\mathbb{C}^N$. Therefore, we can rewrite the analysis
formula~(\ref{eq:mb.41}) in matrix-vector form and we have
\begin{equation}\label{eq:mb.51}
\boldsymbol{\alpha} = \mathbf{M} \mathbf{y}
\end{equation}
The reconstruction formula~(\ref{eq:mb.38}) for $\mathbf{y}$
from the expansion coefficients, becomes, in turn,
\begin{equation}\label{eq:mb.53}
\mathbf{y} = \mathbf{M}^H \boldsymbol{\alpha}
\end{equation}
where the superscript denotes the Hermitian transpose
(transposition and conjugation of the matrix). The previous
equation shows that $\mathbf{y}$ is a linear combination of
the columns of $\mathbf{M}^H$, which, in turn, are of course
the vectors $ \bigl\{ \mathbf{x}^{(k)} \bigr\}$. The orthogonality
relation~(\ref{eq:mb.50}) takes the following forms:
\begin{align}
\mathbf{M}^H \mathbf{M} & = \mathbf{I} \label{eq:mb.54} \\
\mathbf{M} \mathbf{M}^H & = \mathbf{I} \label{eq:mb.55}
\end{align}
since left inverse equals right inverse for square matrices;
this implies that $\mathbf{M}$ has orthonormal rows as well
as orthonormal columns.
\itempar{Polynomial Functions.}
A basis for
$\mathbb{P}_N \bigl([0,1] \bigr)$ is
$\bigl\{ x^k \bigr\}_{0 \leq k < N}$.
This basis, however, is not an orthonormal basis. It can be
transformed to an orthonormal basis by a standard
Gramm-Schmidt procedure; the basis vector thus obtained are called
\emph{Legendre polynomials}.
\itempar{Square Summable Functions.}
An orthonormal basis set for
$L_2 \bigl([-\pi, \pi] \bigr)$ is the set
$\bigl\{ (1/\sqrt{2\pi}) \,e^{jnt} \bigr\}_{n \in \mathbb{Z}}$.
This is actually the classic Fourier basis for functions on
an interval. Please note that, here, as opposed to the
previous examples, the number of basis vectors is actually
infinite. The orthogonality of these basis vectors is easily
verifiable; their completeness, however, is %extremely
rather hard to
prove and this, unfortunately, is very %pretty
much the rule for
all non-trivial, infinite-dimensional basis sets.
\section{Signal Spaces Revisited}
\noindent
We are now in %the
a position to formalize our intuitions so
far, with respect to the equivalence between discrete-time
signals and vector spaces, with a particularization for the
three main classes of signals that we have introduced in the
previous Chapter. Note that in the following, we will
liberally interchange the notations $\mathbf{x}$ and $x[n]$
to denote a sequence as a vector embedded in its appropriate
Hilbert space.
\subsection{Finite-Length Signals}\index{finite-length signal}
The correspondence between the class of finite-length,
length-$N$ signals and $\mathbb{C}^N$ should be so immediate
at this point that it does not need further comment. As a
reminder, the canonical basis is the canonical basis for
$\mathbb{C}^N$. The $k$-th canonical basis vector %will
is often %be
expressed in signal form as
\[
\delta[n-k] \qquad \quad
n = 0, \ldots, N-1, \quad k = 0, \ldots, N-1
\]
\subsection{Periodic Signals}\index{periodic signal}
As we have seen, $N$-periodic signals are equivalent to
length-$N$ signals. The space of $N$-periodic sequences is
therefore isomorphic to $\mathbb{C}^N$. In particular, the
sum %between
of two sequences considered as vectors is the
standard pointwise sum for the elements:
\begin{equation}
z[n] = x[n] + y[n]\qquad \quad n\in \mathbb{Z}
\end{equation}\label{periodicInnerProd}
while, for the inner product, we extend the summation over a period only:
\begin{equation}\label{periodicInnerProduct}
\bigl\langle x[n], y[n] \bigr\rangle
= \sum_{n=0}^{N-1} x^*[n] y[n]
\end{equation}
The canonical basis for the space of $N$-periodic sequences
is the canonical basis for $\mathbb{C}^N$, because of the
isomorphism; in general, any basis for $\mathbb{C}^N$ is
also a basis for the space of $N$-periodic sequences.
Sometimes, however, we will also consider an explicitly
\emph{periodized} version of the basis. For the canonical
basis, in particular, the periodized basis is composed of
$N$~vectors of infinite-length
$\bigl\{ \tilde{\boldsymbol{\delta}}^{(k)} \}_{k = 0 \ldots N - 1}$ with
\[
\tilde{\boldsymbol{\delta}}^{(k)} =
\sum_{i=- \infty}^{\infty} \delta [n - k -iN]
\]
Such a sequence is called a \emph{pulse train}. Note that
here we are abandoning mathematical rigor, since the norm of
each of these basis vectors is infinite; yet the
\emph{pulse train}, if handled with care, can be a useful tool in formal
derivations.
\subsection{Infinite Sequences}\label{InfSeqSpaceDef}\index{infinite-length signal}
%Finally, this is where
%%we have been heading to
%a better way to express this all along. For
In the case of
infinite sequences, whose ``natural'' Euclidean space
would appear to be $\mathbb{C}^\infty$, the situation is
rather delicate. While the sum of two sequences can be
defined in the usual way, by extending the sum for
$\mathbb{C}^N$ to $\mathbb{C}^\infty$, care must be taken
when evaluating the inner product. We have already pointed out
that the formula:
\begin{equation}
\bigl\langle x[n], y[n] \bigr\rangle =
\sum_{n = -\infty}^{\infty} x^*[n] y[n]
\end{equation}
can diverge even for simple constant sequences such as
$x[n] = y[n] = 1$.
A way out of this impasse is to restrict
ourselves to $\ell_2(\mathbb{Z})$, the space of \emph{square
summable sequences}, for which
\begin{equation}\label{eq:mb.30}
\| x \|^2 = \sum_{n \in \mathbb{Z}} \bigl|x[n] \bigr|^2 < \infty
\end{equation}
This is the space of choice for all the theoretical
derivations involving infinite sequences. Note that these
sequences are often called ``of finite energy'', since the
square norm corresponds to the definition of energy as
given in~(\ref{signalEnergy}).
The canonical basis for $\ell_2 (\mathbb{Z})$ is simply the set
$ \bigl\{ \boldsymbol{\delta}^{(k)} \bigr\}_{k \in \mathbb{Z}}$;
in signal form:
\begin{equation}
\boldsymbol{\delta}^{(k)} = \delta[n-k], \qquad \quad n,k \in \mathbb{Z}
\end{equation}
This is an infinite set, and actually an infinite set of
linearly independent vectors, since
\begin{equation}\label{eq:mb.33}
\delta [n - k] = \sum_{l \in \mathbb{Z} / k} \alpha_l \delta [n - l ]
\end{equation}
has no solution for any $k$. Note that, for an arbitrary
signal $x[n]$ the analysis formula gives
\[
\alpha_k = \bigl\langle \boldsymbol{\delta}^{(k)}, \mathbf{x} \bigr\rangle =
\bigl\langle \delta[n-k], x[n] \bigr\rangle = x[k]
\]
so that the reconstruction formula becomes
\[
x[n] = \sum_{k=-\infty}^{\infty} \alpha_k
\boldsymbol{\delta}^{(k)} = \sum_{k=-\infty}^{\infty} x[k]
\, \delta[n-k]
\]
which is the reproducing formula~(\ref{reproForm}). The
Fourier basis for $\ell_2
(\mathbb{Z})$ will be introduced and
discussed at length in the next Chapter.
%\vspace{1em}
As a last remark, note that the space of \emph{all}
finite-support signals, which is clearly a subset of $\ell_2
(\mathbb{Z})$, does \emph{not} form a Hilbert space.
Clearly, the space is closed under addition and scalar
multiplication, and the canonical inner product is well
behaved since all sequences have only a finite number of
nonzero values. However, the space is not complete; to %see
clarify
this, consider the following family of signals:
\[
y_k[n] = \left \{ \!
\begin{array}{ll}
1/n & |n| < k \\
0 & \mbox{otherwise}
\end{array}
\right.
\]
For $k$ growing to infinity, the sequence of signals
converges as $y_k[n] \rightarrow y[n] = 1/n$ for all $n$;
while $y[n]$ is indeed in $\ell_2
(\mathbb{Z})$, since
\[
\sum_{n=0}^{\infty}\frac{1}{n^2} = \frac{\pi^2}{6}
\]
$y[n]$ is clearly \emph{not} a finite-support signal.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\sectionsn{Further Reading}
\input{t/fur3}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\sectionsn{Exercises}
\begin{exercise}{Elementary operators}
An \emph{operator} $\mathcal{H}$ is a transformation of a
given signal and is indicated by the notation
\[
y[n] = \mathcal{H} \bigl\{ x[n] \bigr\}
\]
For instance, the delay operator $\mathcal{D}$ is indicated as
\[
\mathcal{D} \bigl\{ x[n] \bigr\} = x[n-1]
\]
and the one-step difference operator is indicated as
\begin{equation}\label{diffop}
\mathcal{V} \bigl\{ x[n] \bigr\}
= x[n]- \mathcal{D} \bigl\{ x[n] \bigr\} = x[n] - x[n-1]
\end{equation}
A \emph{linear} operator is one for which the following holds:
\[
\left\{ \!
\begin{array}{l} \!
\mathcal{H} \bigl\{\alpha x[n] \bigr\} = \alpha
\mathcal{H} \bigl\{ x[n] \bigr\} \\
\mathcal{H} \bigl\{ x[n] + y[n] \bigr\}
= \mathcal{H} \bigl\{ x[n] \bigl\} + \mathcal{H} \bigl\{ y[n] \bigr\}
\end{array}
\right.
\]
\begin{enumerate}
\item Show that the delay operator $\mathcal{D}$ is linear.
\item Show that the differentiation operator $\mathcal{V}$ is linear.
\item Show that the squaring operator
$\mathcal{S} \bigl\{ x[n] \bigr\} = x^2[n]$ is \emph{not} linear.
\end{enumerate}
In $\mathbb{C}^N$, any linear operator on a vector
$\mathbf{x}$ can be expressed as a matrix-vector
multiplication for a suitable $N \times N$ matrix
$\mathbf{A}$. In $\mathbb{C}^N$, we define the delay
operator as the left {\em circular} shift of a vector:
\[
\mathcal{D} \bigl\{\mathbf{x} \bigr\}
= [\begin{matrix} x_{N-1} & x_0 & x_1 & \ldots & x_{N-2}
\end{matrix} ]^T
\]
Assume $N=4$ for convenience; it is easy to see that
\[
\mathcal{D} \bigl\{\mathbf{x} \bigr\} =
\begin{bmatrix}
0 & 0 & 0 & 1\\
1 & 0 & 0 & 0\\
0 & 1 & 0 & 0\\
0 & 0 & 1 & 0
\end{bmatrix} \mathbf{x} = \mathbf{Dx}
\]
so that $\mathbf{D}$ is the matrix associated to the delay operator.
\begin{enumerate}
\setcounter{enumi}{3}
\item Using the same definition for the one-step difference
operator as in (\ref{diffop}), write out the associated
matrix for the operator in $\mathbb{C}^4$.
\item Consider the following matrix:
\[
\mathbf{A} = \begin{bmatrix}
1 & 0 & 0 & 0\\
1 & 1 & 0 & 0\\
1 & 1 & 1 & 0\\
1 & 1 & 1 & 1
\end{bmatrix}
\]
Which operator do you think it is associated to? What does
the operator do?
\end{enumerate}
\end{exercise}
\begin{exercise}{Bases}
Let $\bigl\{\mathbf{x}^{(k)} \bigr\}_{k=0,\ldots,N-1}$
be a basis for a subspace $S$. Prove that any vector
$\mathbf{z}\in S$ is \emph{uniquely} represented
in this basis.\\
\emph{Hint: prove by contradiction}.
\end{exercise}
\begin{exercise}{Vector spaces and signals}
\begin{enumerate}
\item Show that the set of all ordered $n$-tuples $[a_1,a_2, \dots
,a_n]$ with the natural definition for the sum:
$$
[a_1,a_2, \ldots,a_n] + [b_1,b_2, \ldots , b_n]
= [a_1+b_1,a_2+b_2, \ldots ,a_n+b_n]$$
and
the multiplication by a scalar:
$$\alpha [a_1,a_2, \ldots,a_n]=[\alpha a_1,\alpha a_2, \ldots ,\alpha a_n]
$$
form a vector space. Give its dimension and find a basis.
\item Show that the set of signals of the form
$y(x)=a \cos(x) + b\sin(x)$
(for arbitrary $a$, $b$), with the usual addition and
multiplication by a scalar, form a vector space. Give its dimension
and find a basis.
\item Are the four diagonals of a cube orthogonal?
\item Express the discrete-time impulse $\delta[n]$ in terms of
the discrete-time unit step $u[n]$ and conversely.
\item Show that any function $f(t)$ can be written as the sum of
an odd and an even function, i.e.\ $f(t) = f_o(t) + f_e(t)$ where
$f_o(-t)=-f_o(t)$ and $f_e(-t)=f_e(t)$.
\end{enumerate}
\end{exercise}
\begin{exercise}{The Haar basis}
Consider the following change of basis matrix in
$\mathbb{C}^8$, with respect to the standard orthonormal
basis:
\[
\mathbf{H} =
\begin{bmatrix} %\left[ \begin{array}{cccccccc}
1 & -1 & 0 & 0 & 0 & 0 & 0 & 0\\
0 & 0 & 1 & -1 & 0 & 0 & 0 & 0\\
0 & 0 & 0 & 0 & 1 & -1 & 0 & 0\\
0 & 0 & 0 & 0 & 0 & 0 & 1 & -1\\
1 & 1 & -1 & -1 & 0 & 0 & 0 & 0\\
0 & 0 & 0 & 0 & 1 & 1 & -1 & -1\\
1 & 1 & 1 & 1 & -1 & -1 & -1 & -1 \\
1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\
\end{bmatrix} %{array} \right]
\]
Note the pattern in the first four rows, in the next two,
and in the last two.
\begin{enumerate}
\item What is an easy way to prove that the rows in
$\mathbf{H}$ do indeed form a basis?
\\
(\emph{Hint}: %it's enough
\itshape{it is sufficient to show that they are linearly independent,
% which is to say,\linebreak
i.e.\ that the matrix has full rank\dots{}})
\end{enumerate}
The basis described by $\mathbf{H}$ is called the \emph{Haar
basis} and it is one of the most celebrated cornerstones of
a branch of signal processing called wavelet analysis. To
get a feeling for its properties, consider the following set
of numerical experiments (you can use Matlab or any other
numerical package):
\begin{enumerate}
\setcounter{enumi}{2}
\item Verify that $\mathbf{H} \mathbf{H}^H$ is a diagonal
matrix, which means that the vectors are orthogonal.
\item Consider a constant signal
$ \{ \mathbf{x} =
[\begin{matrix} 1 & 1 & \ldots & 1 \end{matrix} ]$
and compute its coefficients in the Haar basis.
\item Consider an alternating signal
$\{\mathbf{x} = [\begin{matrix} +1 & -1& +1 & \ldots & +1 & -1
\end{matrix} ]$
and compute its coefficients in the Haar basis.
\end{enumerate}
\end{exercise}

Event Timeline

c4science · Help