Let's discuss interpolation.
We are given the sequence, xn.
We would like to derive a continuous time
function, x of t.
That process is done through
interpolation.
So, given a sequence, surely the simple
thing to do is to put a staircase
function.
So we start with x at the origin, x zero.
And we simply continue, x1.
Continue, x2, we continue, and so on, and
that will be the staircase function.
From these samples that's called piecewise
constant interpolation, and the formula
will be x of t is equal to xn, for.
N smaller or equal to T, smaller to N plus
1.
Module 6.2..
Interpolation.
...-tion.
The overview is that we're going to look
first at polynomial interpolation.
You're given a bunch of points, and you
would like to fit the curve that goes
through the points, and that's a
well-known problem of interpolation.
Then we'll look at local interpolators,
which are short functions that do also an
interpolation job[UNKNOWN], and last but
not least, we will look at...
(End of transcription.) Sinc
interpolation.
Is the sinc which is a function we have
seen now several times in this class is a
very important interpolator because it
will generate an output that will be
strictly band limited.
Therefore the output will live on the
subspace.
The subspace of band limited functions.
This subspace we will see is critical for
sampling results.
The interpolation question is very
elementary.
You have a sequence xn.
You want to generate x of t.
And you would like to fill the gaps
between the samples.
How should we best do this.
So here is an example.
We have five blue samples, indicated by
the sticks.
They are equally spaced in time and we fit
the red curve smoothly through the
samples.
Note that it is exact as a sample values
and this is smooths In between.
So the requirements are, we have to decide
on t s, the spacing between the samples in
the continuous time function.
We have to make sure that x at the
location n times t s is equal to sample
values x n.
And we would like, in general, that x t is
a small Smooth function.
We'll see more precisely what we mean by a
smooth function.
Let us discuss the issue of smoothness in
physical terms.
As soon x of t shows the location of an
object.
If there is a jump it would mean there is
infinite speed.
If there is second order discontinuity it
means there would be infinite
acceleration.
In general, we would like interpolators to
be infinitely differentiable.
So they make also physical sense.
A natural solution for this is polynomial
interpolation.
So how to do polynomial interpolation?
Well, if you have n points, there is a
polynomial of degree n minus 1 that can go
through these end points.
For example give me two points, I can draw
Straight line.
Give me three points, I can draw a
parabola, etc.
So we have p of t, which is an n minus 1
degree polynomial.
And we simply fit the polynomial to the
sample.
So p of zero has to be equal to x zero.
P of t s x 1, etc.
Up to be of n minus 1 times T s.
Introduce an interval symmetric around the
origin.
So call it i n from minus capital n to n.
Set t s equal to 1.
We can always rescale the axis to achieve
an a t s.
And then we want to fit P of minus n to
the sample x of minus n,etcetera.
P of 0 to the sample x 0 up to p n to the
sample x n.
The natural solution to this interpolation
problem is given by Lagrange
interpolation.
Take p n the space of degree 2 n
polynomials over the interval i n.
A basis for p n is the family of.
To n plus 1 Lagrange polynomials, given by
this formula.
Let us just do a small example.
Namely m is equal to 1.
So let's write the formula again.
L n of t is this product.
With k going from minus n to capital n.
Pick capital N is equal to 1 so we have 3
polynomials, L minus 1, L0 and L1.
Let us calculate L zero of one.
So L zero one of T is this product where K
cannot be equal to zero of T minus K over
minus K.
This is equal to, To t plus 1 times t
minus 1 divided by minus 1 so that's 1
minus t squared.
We can plot this and sure enough it's a
parabola and it is equal to 1 at the
origin and equal to 0 at minus 1 and also
to 0 at.
That plus 1.
For completeness, you can calculate L1 of
1, it's T squared plus T over 2, and L
minus 1 of 1, which is equal to T squared
minus T.
Over 2.
Let's plot the next bigger example.
This is capital N is equal to 2.
So we have 5 Lagrange interpolators.
The first one is L minus 2, 2 of T, it is
1 minus 2 0 1, minus 1 0 1 and 2, the
second one in blue is L minus 1, it's
equal to 1 minus 1, 0 at the other
integers.
L 0 of 2, which is symmetric around the
origin, where it's equal to 1.
L one of two, which is a black curve.
And finally l two of two, which is a light
blue curve.
The important thing is that these
polynomials are one at their index, m, and
they're zero at the other integers.
Each one has exactly these Characteristic.
So now we have a formula p of t can be
written as, as a linear combination n
length from minus n to n of xn.
The samples ends are respective[UNKNOWN]
of index n.
Let us summarize what has been achieved,
the Lagrange interpolation is what we were
looking for, it's a unique solution to the
interpolation problem it satisfies pn is
equal xn because of the interpolation
property of Lagrange Boolean.
Polynomial.
Let us return to our problem of
interpolating 5 samples, between minus 2
and plus 2.
We can now do this by writing the solution
as a linear combination of Lagrange
interpolators weighted by the sample
values.
Let's do this now.
First lagrange interpolator centered at
minus 2, then at minus 1, at the origin,
at 1, at plus 2.
Who, sum together we find the red curve
that we have seen before.
The key property is polynomial
interpretation is that it's maximally
smooth.
We can take infinitely many derivatives.
The drawkback is that the interpolation
bricks, each piece we add that depends on
N, and each piece actually looks
different, for example in the Lagrange
interpolation case.
Let's look at some other interpolation
possibilities.
So as always, we have to decide on the
spacing between the samples, that capital
T s; we need to make sure that outside
location n t s, the x of t is equal to the
samples I extend...
(End of transcription.) We would like x of
t to have a certain smoothness.
Maybe not infinitely differentiable, as we
can see with polynomials, but at least
some smoothness.
The first example is piecewise constant
interpolation.
So take a sample at the origin, for
example, and put a continuous time
function at such value.
Between minus a house and plus a house,
etc.
Around all the sample.
So it's a staircase function that has the
correct value at the samples, and
it's[UNKNOWN] but of course it is not
continuous.
It has discontinuous.
Points.
What are the characteristics of this zeros
order interpolation?
So x of t is given by this formula.
You take the index t plus one half.
And the 4 function that indicates which
sample you use for the piece-wise constant
interpolation.
So x of t is simply written as a linear
combination of.
X n rect of t minus n.
So the interpolation kernel is this rect
function, sometimes called a zero-order
hold.
The interpolator has a short support of
length 1.
However, the interpolation is not even
continuous.
We start with the same five samples as
usual.
We put the first box function around minus
2.
Some minus one, at zero reaching, at one,
at two and the sum is this[UNKNOWN]
constant function with discontinuous
points at half integers.
The next simplest interpolation is
first-order or piecewise linear.
You simply draw a straight line between
the sample.
This is the so-called connect the dots
strategy.
X of t is now the linear combination of an
interpolation kernel i1, shifted to the
location of the samples and weighted by
the samples xn.
This interpolation kernel is also called
the hat function or the triangle function
because it's simply 1 minus the absolute
value of t on the interval minus 1 to 1.
So support now is of length 2, so it's
longer than the previous interpolation
kernel.
And the interpolation is now continuous,
even though the derivative is not.
We can see this interplation on our usual
five sample discrete sequence.
So we have a hat functino at minus 2.
Minus 1, at 0, at 1, at plus 2, the sum is
this red function, which is piecewise
linear and continuous by construction.
So we have seen i 0 and i 1, so probably
there is higher order interpolation
exists.
One that is interesting is third-order
interpolation, so x of t's linear
combination of i 3 in the shifted version,
the interpolation kernel.
These put together from 2 cubic
polynomials the support is of length 4 and
this one is continuous up to second
derivative.
So we can do our usual construction with
our 5 samples, the cubic interpolator at
minus 2, minus 1, 0.
One, two, and the sum, which is this very
nice smooth red function.
So we have seen now several local
interpolation schemes.
They all work the same way.
You have the kernel, ic.
It is moved to the location of the sample.
Weighted by the sample.
And that's how you interpolate x of t.
The requirement is that the interpolation
kernel at zero is equal to 1, and it's
equal to 0.
At T being a non zero integer.
So it's the interpolation property we had
seen for log on.
We have seen it of course for the box
function, or the square.
We have seen it for the hat function or
the triangle and it was also the case for
the cubic interpolation just before Let's
look at these three interpolation kernels
again.
So first, the box or rectangle function.
Second, the triangle function.
Third, the cubic interpolator.
You can see they become larger and
smoother.
The key properties of these local
interpolators are the following.
It's the same interpolation function
independently of N, and independently of
location.
This was not the case of lack of
interpolation.
Another advantage is the short support of
the interpolation kernel.
The drawback is the lack of smoothness.
There is a remarkable result that links
the sink interpolation scheme with the
Lagrange interpolation scheme.
Namely, if you take[INAUDIBLE]
interpolator of order capital N.
And you take the[INAUDIBLE] indexed one as
n goes to infinity.
Then this tends to think of t minus m.
So, in the limit, local and global
actually are the same interpolation keys.
So we have the same interpolation formula
as a limit of like[INAUDIBLE]
interpolation, namely x of t is equal to
the sum of xn sinc of t minus nTs divided
by Ts.
This is very elegant and very[INAUDIBLE].
Powerful formula.
Let us look at sinc interpolation at work.
So we'll have a sinc kernel centered on
every sample.
So the first one at the origin.
Then at plus 1.
Plus 2.
3,4,5, etcetera you see the some of them
now as a red curve, very smooth, very
nice.
So we have now the interpolated version
through the samples.
And this is the sinc interpolation of a
discreet time sequence.
Is a proof that the Legrange interpolator
goes to the sinc function as n goes to
infinity is rather technical.
It is given in the book.
So please look it up if you're interested.
The intuition is that both think of t
minus n and l n at infinity of t share the
same set of infinite number of zeros.
Which is given here in the last two
formulas of, Of the slide.
We can explore this equivalence between
the sync function and the licointerpolator
numerically.
So let's start with the sync function here
in green centered at the origin.
Then a licointerpolator of order 100 and
you can see it's a good fit around the
origin.
Not so good toward the end of interval.
L200, it's a better fit, still not
perfect.
L 300 even better and you can see where it
is going and we know or we can prove that
in the limit, these two functions will be
the same.