3.3 - Hilbert Space and approximation [21:40] 2nd edition

From EPFL's Digital Signal Processing course on Coursera, in its 2nd 2014 edition

Now that we have constructed Hilbert
spaces and ordinal

bases we can see some of their
distinguishing features.

One of them is norm conservation which is

called Parseval's theorem and is an
extension of Peter

[INAUDIBLE]

famous ordinality theorem to infinite
dimensions.

Then we will see the orthogonal projection
theorem.

This is a powerful method to take a vector
from

possibly an infinite dimensional space,
and project it onto a subspace.

Once we have this, we will consider

some examples of approximations and
othonormal basis.

Module 3.3 Hilbert Space and
approximation.

Your review of this sub module as
following:

first I'm going to talk about the norm
conservation, when

we have expansion into orthonormal basis,
and a

so-called equivalence formula, which is
known as Parseval's formula.

Then we talk about approximation by
projection, and we give an example.

Parseval's theorem has a very simple form.

It says that if you expand x in an
orthonormal basis, so we have a vector

in a Hilbert space, we expand it in an
orthonormal basis with this vector w.

Here, we are on the finite dimensional
case of dimension capital K.

Then, for orthonormal basis, the square
norm of x

is equal to the sum of squared
coefficients, okay?

This of course a generalization of
Pythagorean theorem, which says that if I

have the vector here, this is x, this

is, so length in an orthonormal basis or,
that would be alpha 0

in e 0, alpha with respect to

e1, then x square is equal to alpha

0 square plus alpha 1 square.
Okay?

Very old result, very useful result.
Let's actually verify it algebraically.

We start with the canonical basis, e0 and
e1, just as before.

We write x as a linear combination of e0
and e1, and we go to a new basis.

The new

basis is v0 and v1.
It' s an autonomal basis.

Okay.

You can verify that these guys are at the
right angle.

And this basis is given by v0 is cosine

theta sine theta v1 is minus sine theta
cosine theta.

You can see this here on the projections.

And so x in the new basis is equal to beta
0 v 0.

Vector 1,

V1.

What are the expressions of this, well we
know this because the

basis is orthonormal so the expansion
coefficients beta 0 is equal to

[UNKNOWN]

product between V0 and X beta 1 the inner
product between V1 and X.

Or in compact form.

We can just write these inner products as
row, column, scaler products.

OK, so the the zero is cosine theta.
Sin theta d one is

minus sin theta cos theta as we have seen.
And so we write this as R

times alpha where R is the rotation
matrix.

Okay?

A unitary matrix that corresponds to these
basis vectors.

Alright, and it's not hard to verify that
the rotation matrix times this transpose

is equal to identity, meaning it is equal
through transposition to its inverse.

So it's a unitary matrix, as we probably
well know by now.

Okay.
So let's look look at norm conservation.

So the square norm in the canonical basis
is just as we announced,

so x squared is equal to alpha 0 squared
plus alpha 1 squared.

The square norm in the rotated basis is
the same, but with respect to beta.

Okay.

So we are going to show that these two
things are the same.

Or, verify Parseval's formula.

Well, one way to write beta 0 squared plus
beta 1 squared

is to say it's a vector beta transpose
times beta, right, okay.

I'm just, so I'm making myself absolutely
clear It's

the scalar product of the vector beta,
okay, with itself.

Okay.

That's the thing here.

Now, of course, beta is equal to R times
alpha.

Beta transpose is R times alpha transpose.

You go to the extra step of reordering
here the products, so

the alpha transpose comes in front, R
transpose here times R times alpha.

This of course simplified to identity that
we know because R is a unitary matrix.

So this is equal to alpha transposed as
alpha.

And of course we verify what we set out to
do, okay.

Now we did this in two dimensions,

it's obvious that this will hold in n
dimensions for an arbitrary n.

It turns out it also tell it also holds
for infinite dimensional canonical basis.

Okay, so that's Parseval's formula, very
important formula in signal processing.

Okay, what it really means is that if you
have a vector X,

and you look at this vector in, you know,
this basis,

and you look at in some other basis, as we
just did, which is a rotation, because all

[UNKNOWN]

basis are essentially rotations of each
other and maybe

some symmetry, then the length of the
vector doesn't change.

Okay, so that's of course norm
conservational so means distance

conservation through these transforms or

through the expansion into orthonormal
basis.

Alright.

The next step we want to do is
approximation.

We had briefly mentioned this at the
beginning of this module.

So, we have a vector in R3 here.

And, the vector X should be represented in
a subspace spanned by e0 and e1.

Well, that's a subspace S of V.
Spanned by e0 e1,

now shown in red, and the approximation is
x hat.

It belongs to S, and it's the orthogonal
projection

x to the plane spanned by e0 and e1.

Okay?

And that orthonormal projection we'll
denote by x hat.

How can we do this?
It is very simple.

We take an orthonormal basis for the
subspace.

Okay, so remember we have the big space V.

WE have the subspace c.

So we take an orthonormal basis for the
subspace and

the orthogonal projection is simply going
to be given by.

X hat expanded in the ordinal basis that
spans the subspace, Okay?

So the set of vectors sk, is the
orthogonal basis for

s and here is the expansion form well in
this ordinal basis.

This orthogonal projection is the best
approximation.

Over S to the vector x.
And it's best in the l

2 sense, or, it will minimize the
quadratic norm of the error.

Okay.

So in a word, orthogonal projection has
minimum-norm error.

So.

Among all vectors y that belong to s, the
one that minimizes

the square of the difference here, so the
square norm of the

difference x minus y is this vector x hat
that we have

written out in terms of an ordinal basis
for the subspace s.

Very important property is that the error
x

minus x hat is orthogonal to the
approximation, okay?

So we'll see it in the next slide, but
this is an extremely important formula.

It's called the orthogonality principle.
It is used all over signal processing.

When we minimize quadratic error.
All right.

So let's see this very graphically; we
have

s a subspace, this guy is subspace, so V,
V is the ambient space

in this particle case R2 as is R1, it's a
one dimensional subspace.

Okay.

So we want to find the closest point to x.
So x is what we want to approximate.

We'd like to find the closest point
somewhere here in S.

Okay?

How do we do this?
It has to be closest in the 2

norm, so we create a circle around the tip
here of x, and we grow the circle.

Okay.

We are still not at s.

And at some point, we reach s.

This is cl-, either it is a closest one,
right?

Because the circles measure quadratic
distance.

And the first time we hit s, it is exactly
here.

Okay.
So we have x-hat in blue.

And we notice that x minus x-hat, the red
vector is orthogonal to the blue vector.

That's your

[INAUDIBLE]

principle we have seen on the previous
slide.

Let's look at a very concrete example.
It's polynomial approximation.

So we go back to our favorite interval, -1
to 1.

Okay, so we will get these guys, and for
this

interval, we define.
As subspace pn minus one to one

which are polynomials up to degree n minus
one on the interval minus one two,

okay?
So a basis for this is simply to take

as the successive monomials tk for k going
from zero to capital n minus one.

Okay, so a naive basis here.

Is really 1, t, t squared, t cubed,
etcetera.

Okay.

Now, these guys are not orthonormal to
each other.

Okay?

So this naive basis is not orthogonal.

Okay, which is self-evident, because, for
example, On the

interval -1 to 1.
Let's take this interval.

We have the first element.

That's this guy.
Okay.

The second guy, he's orthogonal, because
the first one was symmetric, the second

one is antisymmetric.
But the third guy is a quadratic function.

And it's not properly scaled.

I apologize.
But the quadratic function,

of course, is also symmetric.
So for example, the inner product between

1 and t square on the interval minus 1 to
1 is not equal to 0.

Okay?

Please check this more explicitly if

you like, but it's fairly geometrically
evident.

Okay, now we're are going to try to
approximate

something that does not live on the
polynomial space.

So that would be for

example trigonometric functions.

So take x, what we are going to
approximate as

sin t over minus the interval minus one to
one.

And we would like to approximate it on p
3.

So up to polynomials of a third degree

Okay, so the way to do it is, we build an
orthonormal basis from the naive basis.

We project x over the orthonormal basis.

We compute the approximation error.
Okay?

So same thing as usual.
So S.

Here is this P3 space.

Our sin is somewhere out there, and we
want to compute this.

To do this, we first construct an ordinal
basis for the sub spaces.

Okay.

We can compare this to the

naive approximation, which would be Taylor
approximation.

It's well known, very useful, but it's not
optimal, as we will see in just a minute.

Okay, so from the naive basis, remember,
we have the naive basis, it's 1,

t, T square, t cube etc.

We can compute so that's a viral basis we
compute an orthogonal basis.

There is a procedure to do this which is
called the Gram-Schmidt algorithm, okay.

You explain in the appendix of this
lecture, we

are not going to do it in the main
lecture.

And it's a recursive procedure where you
take the first one You

normalize it.
That's fine.

You take the second one, and you make sure
it's ordinal to the first one.

You normalize it, and you keep going.

And the result of this is that you get
ordinal null

vectors, u 0, which is just a scaled
version of 1.

The second one, these two ordinals, you
don't

have to change much except for the
scaling.

The third one is a transformation of
t-square.

T-square,

I mean, like this, more explicit,
t-square.

Into, you know, a second order point on u,
which

is constructed such that u2 is orthogonal
to u0 and u1.

And you can keep going like this.
It's a standard construction.

It's called Legendre polynomials.

And just from the name, you know this is

a 19th century construction, so it's
extremely well known.

And the appendix gives the details.
Okay, so now we have an

ordinal basis for the subspace.

And, let's just watch these Legendre's
polynomials, they're sort of cute,

so the first one remember, it's, 1 over
square root of 2.

So here we go.
That's 0.7 something.

It's the black line.

The second one is proportional to t, but
it has been scaled.

The third

one, which is quadratic, has been moved
about.

So now it is actually orthogonal to

It's automatically, the yellow color is
automatically

orthogonal to the red curve because one

is symmetrics the other one is
anti-symmetric.

But the shift that was added if we go back
here, let me just show you if I

shift here, this shift makes sure that the
inner product between the yellow curve and

the black curve is zero.
Okay?

And it's a fourth, is a third degree
polynomial, is the green guy.

It is antisymmetric, so it will be
automatically orthogonal to the black one.

The yellow one, but it has to be adjusted
so that is orthogonal to the red one.

And we can keep going.

Okay, so that's a four story guy.
Four order polynomial, and so on.

So Legendre polynomials go off to
infinity, but

we'll just look at a few of them.

Okay?

Here's a phase one.

And it's a very cute picture.

And this set of polynomials on this
interval

-1 to 1, okay, they're important on this
interval.

It's defined in such, it's constructed
actually

in such a way that the inner product

of two of these functions is equal to
delta i minus j.

So it's equal to zero when i is different
from.

j, and it's equal to one when, i is equal
to j, okay?

It's not self-evident when you look at
the, at the functions

except for the symmetries that I pointed
out, a minute ago.

Alright.

So now we can compute

our expansion coefficients.
Remember, we want to write the formula

where x hat is going to be some sum of
alpha-k.

u k we call these guys here, and k goes
from 0 to capital K minus 1.

So that's the orthogonal projection onto
the subspace spanned by the u k.

Alright, so we have to take the integrals
between -1,

1.

Of the function, these polynomials, we
have just defined

[UNKNOWN]

polynomials and the function we want to
approximate sine t.

Okay.

So sin is of course an odd function as we
know

as so alpha zero is going to be
automatically equal to zero.

Alpha one is going to be different from
zero,

because both u one and sine are odd
functions.

So that's what you get if you

do the integral, 0.73 something.

And the third coefficient, alpha two, is
also

equal to zero, because this character here
is.

Symmetric, and this one is antisymmetric,
so it's automatically equal to 0.

Okay, so what do we get?
So, when we do the orthogonal projection

on these three basis vectors,

so, u0, u1, u2, we get an approximation,
which is

simply alpha 1, u1 And it's given by this
formula.

If we do Taylor series, then the first
order approximation of

Taylor series simply to take sin t equal
to t, okay.

And so we're going to compare these two
approximates, they

look very similar but one has been scaled
a little

bit, okay.
Alright.

So now we see that the approximation of
sine, which is the blue curve, the smooth

blue curve here, t is the red curve, and
green is simply a scaled version.

Doesn't look like a big deal.

It's, you know, 10% smaller, but you can
immediately see that it's

actually hugging the blue curve more
closely over the interval -1 to 1,

right?

So we are approximating this over this
interval.

If we change the interval So, our
approximation would look different.

Okay?

But over this interval, as we can see

here, we plugged the absolute value of the
difference.

The red one is sin t minus t.

Okay, it goes off quite a bit at the end
intervals here.

It's very nice in the region around zero
region, okay.

And we see that the

green approximation which is sin t minus
our projection onto

the subspace of the legorn-, the legendre
polynomials of orders zero

one and two That error is overall, it is
smaller.

Never goes goes off to these values, okay.

Sometimes it's bigger, but overall, it
actually turns out to be smaller, okay?

So, to compare this numerically, we can
compute the norm of

sine t minus alpha 1 t, and it's 0.0337 In
Taylor

serie, it's almost three times bigger.
It's 0.08.

Necessarily we have to be as good or

better than Taylor series because it's a
theorem.

It's the orthogonal

projection theorem we find the minimum
norm approximation.

Okay?

And with this, we have Showing on a very
practical

example how to do orthogonal approximation
using an orthogonal basis.

Now, this was all a lot of work.

We defined Hilbert spaces, we had a lot of
definitions, and so on.

So why do we do all this?
It's a great question.

So, first is at both finite-length and
periodic signals live in C N.

So we can use all of linear algebra and

all the geometry of linear algebra to do
this.

And

Infinite-length signals, that we like for
general signal processing live in

a more general Hilbert space, which is
small l2 of Z.

Okay so we have a common geometric frame
work for

both finite lengths, periodic signals and
infinite length sequences, okay.

So we have one way to think about the
whole bunch of different problems, okay.

Then we'll see that the expansion into
orthogonal

bases is very central to signal
processing.

So em, we can use different bases.

As different observation tools for
signals.

We're going to see something called the
Short

Time Fourier Transform, to be defined in
Module 4.

And the Short Time Fourier Transform as
the second half says, is

something like a Fourier transform, but
it's a very particular way to look

at signals.
It's very popular.

For doing speech analysis and the like.
Okay?

And when we do subspace projections, we
will

see that we can do filtering, which will

be explained, of course, in detail, in
this

class, and we can do, for example, image
compression.

Okay.

So the notions we have seen, one was to
build bases, that's important.

These are like our

tools to look at signals.

Okay, and another one was subspace
projection which was

something that will come a lot when we do
approximation.

And in particular when we do compression.

Okay, let me just finish this properly
here.

We have the origin, we have a sub space s,
we have

x and we have the orthogonal projection
and we have the orthogonality principle.