1
00:00:00,012 --> 00:00:04,233
Let's discuss interpolation.
We are given the sequence, xn.

2
00:00:04,233 --> 00:00:08,279
We would like to derive a continuous time
function, x of t.

3
00:00:08,279 --> 00:00:11,380
That process is done through
interpolation.

4
00:00:11,380 --> 00:00:16,283
So, given a sequence, surely the simple
thing to do is to put a staircase

5
00:00:16,283 --> 00:00:19,855
function.
So we start with x at the origin, x zero.

6
00:00:19,855 --> 00:00:25,752
And we simply continue, x1.
Continue, x2, we continue, and so on, and

7
00:00:25,752 --> 00:00:33,555
that will be the staircase function.
From these samples that's called piecewise

8
00:00:33,555 --> 00:00:40,530
constant interpolation, and the formula
will be x of t is equal to xn, for.

9
00:00:40,531 --> 00:00:48,536
N smaller or equal to T, smaller to N plus
1.

10
00:00:48,536 --> 00:00:54,156
Module 6.2..
Interpolation.

11
00:00:54,156 --> 00:00:56,842
...-tion.
The overview is that we're going to look

12
00:00:56,842 --> 00:01:00,912
first at polynomial interpolation.
You're given a bunch of points, and you

13
00:01:00,912 --> 00:01:04,560
would like to fit the curve that goes
through the points, and that's a

14
00:01:04,560 --> 00:01:08,963
well-known problem of interpolation.
Then we'll look at local interpolators,

15
00:01:08,963 --> 00:01:13,443
which are short functions that do also an
interpolation job[UNKNOWN], and last but

16
00:01:13,443 --> 00:01:16,814
not least, we will look at...
(End of transcription.) Sinc

17
00:01:16,814 --> 00:01:19,977
interpolation.
Is the sinc which is a function we have

18
00:01:19,977 --> 00:01:24,667
seen now several times in this class is a
very important interpolator because it

19
00:01:24,667 --> 00:01:28,271
will generate an output that will be
strictly band limited.

20
00:01:28,271 --> 00:01:31,096
Therefore the output will live on the
subspace.

21
00:01:31,096 --> 00:01:35,867
The subspace of band limited functions.
This subspace we will see is critical for

22
00:01:35,867 --> 00:01:39,512
sampling results.
The interpolation question is very

23
00:01:39,512 --> 00:01:42,051
elementary.
You have a sequence xn.

24
00:01:42,051 --> 00:01:46,275
You want to generate x of t.
And you would like to fill the gaps

25
00:01:46,275 --> 00:01:49,721
between the samples.
How should we best do this.

26
00:01:49,721 --> 00:01:54,577
So here is an example.
We have five blue samples, indicated by

27
00:01:54,577 --> 00:01:58,652
the sticks.
They are equally spaced in time and we fit

28
00:01:58,652 --> 00:02:02,120
the red curve smoothly through the
samples.

29
00:02:02,120 --> 00:02:07,601
Note that it is exact as a sample values
and this is smooths In between.

30
00:02:07,601 --> 00:02:13,817
So the requirements are, we have to decide
on t s, the spacing between the samples in

31
00:02:13,817 --> 00:02:18,579
the continuous time function.
We have to make sure that x at the

32
00:02:18,579 --> 00:02:22,275
location n times t s is equal to sample
values x n.

33
00:02:22,275 --> 00:02:27,096
And we would like, in general, that x t is
a small Smooth function.

34
00:02:27,096 --> 00:02:30,875
We'll see more precisely what we mean by a
smooth function.

35
00:02:30,875 --> 00:02:34,558
Let us discuss the issue of smoothness in
physical terms.

36
00:02:34,558 --> 00:02:37,485
As soon x of t shows the location of an
object.

37
00:02:37,485 --> 00:02:41,076
If there is a jump it would mean there is
infinite speed.

38
00:02:41,076 --> 00:02:45,582
If there is second order discontinuity it
means there would be infinite

39
00:02:45,582 --> 00:02:49,434
acceleration.
In general, we would like interpolators to

40
00:02:49,434 --> 00:02:53,499
be infinitely differentiable.
So they make also physical sense.

41
00:02:53,499 --> 00:02:57,056
A natural solution for this is polynomial
interpolation.

42
00:02:57,056 --> 00:03:01,731
So how to do polynomial interpolation?
Well, if you have n points, there is a

43
00:03:01,731 --> 00:03:05,948
polynomial of degree n minus 1 that can go
through these end points.

44
00:03:05,948 --> 00:03:09,893
For example give me two points, I can draw
Straight line.

45
00:03:09,893 --> 00:03:13,578
Give me three points, I can draw a
parabola, etc.

46
00:03:13,578 --> 00:03:17,842
So we have p of t, which is an n minus 1
degree polynomial.

47
00:03:17,842 --> 00:03:21,368
And we simply fit the polynomial to the
sample.

48
00:03:21,368 --> 00:03:25,337
So p of zero has to be equal to x zero.
P of t s x 1, etc.

49
00:03:25,337 --> 00:03:31,565
Up to be of n minus 1 times T s.
Introduce an interval symmetric around the

50
00:03:31,565 --> 00:03:35,673
origin.
So call it i n from minus capital n to n.

51
00:03:35,673 --> 00:03:40,844
Set t s equal to 1.
We can always rescale the axis to achieve

52
00:03:40,844 --> 00:03:44,599
an a t s.
And then we want to fit P of minus n to

53
00:03:44,599 --> 00:03:50,619
the sample x of minus n,etcetera.
P of 0 to the sample x 0 up to p n to the

54
00:03:50,619 --> 00:03:55,371
sample x n.
The natural solution to this interpolation

55
00:03:55,371 --> 00:03:59,228
problem is given by Lagrange
interpolation.

56
00:03:59,228 --> 00:04:04,769
Take p n the space of degree 2 n
polynomials over the interval i n.

57
00:04:04,769 --> 00:04:11,802
A basis for p n is the family of.
To n plus 1 Lagrange polynomials, given by

58
00:04:11,802 --> 00:04:16,230
this formula.
Let us just do a small example.

59
00:04:16,230 --> 00:04:21,732
Namely m is equal to 1.
So let's write the formula again.

60
00:04:21,732 --> 00:04:28,207
L n of t is this product.
With k going from minus n to capital n.

61
00:04:28,207 --> 00:04:46,716
Pick capital N is equal to 1 so we have 3
polynomials, L minus 1, L0 and L1.

62
00:04:46,717 --> 00:04:56,764
Let us calculate L zero of one.
So L zero one of T is this product where K

63
00:04:56,764 --> 00:05:03,654
cannot be equal to zero of T minus K over
minus K.

64
00:05:03,654 --> 00:05:10,614
This is equal to, To t plus 1 times t
minus 1 divided by minus 1 so that's 1

65
00:05:10,614 --> 00:05:15,773
minus t squared.
We can plot this and sure enough it's a

66
00:05:15,773 --> 00:05:22,373
parabola and it is equal to 1 at the
origin and equal to 0 at minus 1 and also

67
00:05:22,373 --> 00:05:24,306
to 0 at.
That plus 1.

68
00:05:24,306 --> 00:05:31,800
For completeness, you can calculate L1 of
1, it's T squared plus T over 2, and L

69
00:05:31,800 --> 00:05:36,384
minus 1 of 1, which is equal to T squared
minus T.

70
00:05:36,385 --> 00:05:40,452
Over 2.
Let's plot the next bigger example.

71
00:05:40,452 --> 00:05:46,788
This is capital N is equal to 2.
So we have 5 Lagrange interpolators.

72
00:05:46,788 --> 00:05:53,290
The first one is L minus 2, 2 of T, it is
1 minus 2 0 1, minus 1 0 1 and 2, the

73
00:05:53,290 --> 00:05:59,670
second one in blue is L minus 1, it's
equal to 1 minus 1, 0 at the other

74
00:05:59,670 --> 00:06:04,267
integers.
L 0 of 2, which is symmetric around the

75
00:06:04,267 --> 00:06:10,001
origin, where it's equal to 1.
L one of two, which is a black curve.

76
00:06:10,001 --> 00:06:13,791
And finally l two of two, which is a light
blue curve.

77
00:06:13,791 --> 00:06:19,215
The important thing is that these
polynomials are one at their index, m, and

78
00:06:19,215 --> 00:06:25,451
they're zero at the other integers.
Each one has exactly these Characteristic.

79
00:06:25,451 --> 00:06:32,596
So now we have a formula p of t can be
written as, as a linear combination n

80
00:06:32,596 --> 00:06:39,784
length from minus n to n of xn.
The samples ends are respective[UNKNOWN]

81
00:06:39,784 --> 00:06:43,726
of index n.
Let us summarize what has been achieved,

82
00:06:43,726 --> 00:06:49,477
the Lagrange interpolation is what we were
looking for, it's a unique solution to the

83
00:06:49,477 --> 00:06:54,904
interpolation problem it satisfies pn is
equal xn because of the interpolation

84
00:06:54,904 --> 00:06:58,244
property of Lagrange Boolean.
Polynomial.

85
00:06:58,244 --> 00:07:03,890
Let us return to our problem of
interpolating 5 samples, between minus 2

86
00:07:03,890 --> 00:07:07,934
and plus 2.
We can now do this by writing the solution

87
00:07:07,934 --> 00:07:13,700
as a linear combination of Lagrange
interpolators weighted by the sample

88
00:07:13,700 --> 00:07:17,676
values.
Let's do this now.

89
00:07:17,676 --> 00:07:32,020
First lagrange interpolator centered at
minus 2, then at minus 1, at the origin,

90
00:07:32,020 --> 00:07:37,554
at 1, at plus 2.
Who, sum together we find the red curve

91
00:07:37,554 --> 00:07:41,836
that we have seen before.
The key property is polynomial

92
00:07:41,836 --> 00:07:45,426
interpretation is that it's maximally
smooth.

93
00:07:45,426 --> 00:07:51,642
We can take infinitely many derivatives.
The drawkback is that the interpolation

94
00:07:51,642 --> 00:07:57,132
bricks, each piece we add that depends on
N, and each piece actually looks

95
00:07:57,132 --> 00:08:01,851
different, for example in the Lagrange
interpolation case.

96
00:08:01,851 --> 00:08:05,876
Let's look at some other interpolation
possibilities.

97
00:08:05,876 --> 00:08:11,624
So as always, we have to decide on the
spacing between the samples, that capital

98
00:08:11,624 --> 00:08:16,931
T s; we need to make sure that outside
location n t s, the x of t is equal to the

99
00:08:16,931 --> 00:08:21,452
samples I extend...
(End of transcription.) We would like x of

100
00:08:21,452 --> 00:08:26,773
t to have a certain smoothness.
Maybe not infinitely differentiable, as we

101
00:08:26,773 --> 00:08:30,698
can see with polynomials, but at least
some smoothness.

102
00:08:30,698 --> 00:08:34,642
The first example is piecewise constant
interpolation.

103
00:08:34,642 --> 00:08:39,436
So take a sample at the origin, for
example, and put a continuous time

104
00:08:39,436 --> 00:08:43,826
function at such value.
Between minus a house and plus a house,

105
00:08:43,826 --> 00:08:45,606
etc.
Around all the sample.

106
00:08:45,606 --> 00:08:50,262
So it's a staircase function that has the
correct value at the samples, and

107
00:08:50,262 --> 00:08:53,511
it's[UNKNOWN] but of course it is not
continuous.

108
00:08:53,511 --> 00:08:55,676
It has discontinuous.
Points.

109
00:08:55,676 --> 00:09:00,326
What are the characteristics of this zeros
order interpolation?

110
00:09:00,326 --> 00:09:05,201
So x of t is given by this formula.
You take the index t plus one half.

111
00:09:05,201 --> 00:09:11,003
And the 4 function that indicates which
sample you use for the piece-wise constant

112
00:09:11,003 --> 00:09:14,857
interpolation.
So x of t is simply written as a linear

113
00:09:14,857 --> 00:09:17,768
combination of.
X n rect of t minus n.

114
00:09:17,768 --> 00:09:24,053
So the interpolation kernel is this rect
function, sometimes called a zero-order

115
00:09:24,053 --> 00:09:27,623
hold.
The interpolator has a short support of

116
00:09:27,623 --> 00:09:31,407
length 1.
However, the interpolation is not even

117
00:09:31,407 --> 00:09:35,340
continuous.
We start with the same five samples as

118
00:09:35,340 --> 00:09:39,181
usual.
We put the first box function around minus

119
00:09:39,181 --> 00:09:44,600
2.
Some minus one, at zero reaching, at one,

120
00:09:44,600 --> 00:09:53,714
at two and the sum is this[UNKNOWN]
constant function with discontinuous

121
00:09:53,714 --> 00:09:59,932
points at half integers.
The next simplest interpolation is

122
00:09:59,932 --> 00:10:06,117
first-order or piecewise linear.
You simply draw a straight line between

123
00:10:06,117 --> 00:10:09,956
the sample.
This is the so-called connect the dots

124
00:10:09,956 --> 00:10:13,663
strategy.
X of t is now the linear combination of an

125
00:10:13,663 --> 00:10:19,559
interpolation kernel i1, shifted to the
location of the samples and weighted by

126
00:10:19,559 --> 00:10:23,770
the samples xn.
This interpolation kernel is also called

127
00:10:23,770 --> 00:10:29,773
the hat function or the triangle function
because it's simply 1 minus the absolute

128
00:10:29,773 --> 00:10:35,452
value of t on the interval minus 1 to 1.
So support now is of length 2, so it's

129
00:10:35,452 --> 00:10:39,124
longer than the previous interpolation
kernel.

130
00:10:39,124 --> 00:10:44,786
And the interpolation is now continuous,
even though the derivative is not.

131
00:10:44,786 --> 00:10:50,174
We can see this interplation on our usual
five sample discrete sequence.

132
00:10:50,174 --> 00:10:57,605
So we have a hat functino at minus 2.
Minus 1, at 0, at 1, at plus 2, the sum is

133
00:10:57,605 --> 00:11:07,789
this red function, which is piecewise
linear and continuous by construction.

134
00:11:07,790 --> 00:11:13,149
So we have seen i 0 and i 1, so probably
there is higher order interpolation

135
00:11:13,149 --> 00:11:16,663
exists.
One that is interesting is third-order

136
00:11:16,663 --> 00:11:22,081
interpolation, so x of t's linear
combination of i 3 in the shifted version,

137
00:11:22,081 --> 00:11:27,046
the interpolation kernel.
These put together from 2 cubic

138
00:11:27,046 --> 00:11:34,022
polynomials the support is of length 4 and
this one is continuous up to second

139
00:11:34,022 --> 00:11:38,954
derivative.
So we can do our usual construction with

140
00:11:38,954 --> 00:11:44,581
our 5 samples, the cubic interpolator at
minus 2, minus 1, 0.

141
00:11:44,582 --> 00:11:54,611
One, two, and the sum, which is this very
nice smooth red function.

142
00:11:54,611 --> 00:11:58,918
So we have seen now several local
interpolation schemes.

143
00:11:58,918 --> 00:12:02,796
They all work the same way.
You have the kernel, ic.

144
00:12:02,796 --> 00:12:07,707
It is moved to the location of the sample.
Weighted by the sample.

145
00:12:07,707 --> 00:12:13,782
And that's how you interpolate x of t.
The requirement is that the interpolation

146
00:12:13,782 --> 00:12:17,426
kernel at zero is equal to 1, and it's
equal to 0.

147
00:12:17,426 --> 00:12:22,062
At T being a non zero integer.
So it's the interpolation property we had

148
00:12:22,062 --> 00:12:25,295
seen for log on.
We have seen it of course for the box

149
00:12:25,295 --> 00:12:29,634
function, or the square.
We have seen it for the hat function or

150
00:12:29,634 --> 00:12:35,637
the triangle and it was also the case for
the cubic interpolation just before Let's

151
00:12:35,637 --> 00:12:39,372
look at these three interpolation kernels
again.

152
00:12:39,372 --> 00:12:46,030
So first, the box or rectangle function.
Second, the triangle function.

153
00:12:46,030 --> 00:12:51,991
Third, the cubic interpolator.
You can see they become larger and

154
00:12:51,991 --> 00:12:55,282
smoother.
The key properties of these local

155
00:12:55,282 --> 00:13:00,209
interpolators are the following.
It's the same interpolation function

156
00:13:00,209 --> 00:13:03,769
independently of N, and independently of
location.

157
00:13:03,769 --> 00:13:06,983
This was not the case of lack of
interpolation.

158
00:13:06,983 --> 00:13:11,666
Another advantage is the short support of
the interpolation kernel.

159
00:13:11,666 --> 00:13:17,473
The drawback is the lack of smoothness.
There is a remarkable result that links

160
00:13:17,473 --> 00:13:22,823
the sink interpolation scheme with the
Lagrange interpolation scheme.

161
00:13:22,823 --> 00:13:27,688
Namely, if you take[INAUDIBLE]
interpolator of order capital N.

162
00:13:27,688 --> 00:13:32,329
And you take the[INAUDIBLE] indexed one as
n goes to infinity.

163
00:13:32,329 --> 00:13:37,958
Then this tends to think of t minus m.
So, in the limit, local and global

164
00:13:37,958 --> 00:13:44,861
actually are the same interpolation keys.
So we have the same interpolation formula

165
00:13:44,861 --> 00:13:50,487
as a limit of like[INAUDIBLE]
interpolation, namely x of t is equal to

166
00:13:50,487 --> 00:13:54,165
the sum of xn sinc of t minus nTs divided
by Ts.

167
00:13:54,165 --> 00:13:59,657
This is very elegant and very[INAUDIBLE].
Powerful formula.

168
00:13:59,657 --> 00:14:07,820
Let us look at sinc interpolation at work.
So we'll have a sinc kernel centered on

169
00:14:07,820 --> 00:14:12,421
every sample.
So the first one at the origin.

170
00:14:12,421 --> 00:14:14,762
Then at plus 1.
Plus 2.

171
00:14:14,763 --> 00:14:21,374
3,4,5, etcetera you see the some of them
now as a red curve, very smooth, very

172
00:14:21,374 --> 00:14:25,309
nice.
So we have now the interpolated version

173
00:14:25,309 --> 00:14:30,429
through the samples.
And this is the sinc interpolation of a

174
00:14:30,429 --> 00:14:35,852
discreet time sequence.
Is a proof that the Legrange interpolator

175
00:14:35,852 --> 00:14:40,844
goes to the sinc function as n goes to
infinity is rather technical.

176
00:14:40,844 --> 00:14:45,726
It is given in the book.
So please look it up if you're interested.

177
00:14:45,726 --> 00:14:51,312
The intuition is that both think of t
minus n and l n at infinity of t share the

178
00:14:51,312 --> 00:14:56,646
same set of infinite number of zeros.
Which is given here in the last two

179
00:14:56,646 --> 00:15:01,298
formulas of, Of the slide.
We can explore this equivalence between

180
00:15:01,298 --> 00:15:05,230
the sync function and the licointerpolator
numerically.

181
00:15:05,230 --> 00:15:10,317
So let's start with the sync function here
in green centered at the origin.

182
00:15:10,317 --> 00:15:15,571
Then a licointerpolator of order 100 and
you can see it's a good fit around the

183
00:15:15,571 --> 00:15:18,820
origin.
Not so good toward the end of interval.

184
00:15:18,820 --> 00:15:21,973
L200, it's a better fit, still not
perfect.

185
00:15:21,974 --> 00:15:30,767
L 300 even better and you can see where it
is going and we know or we can prove that

186
00:15:30,767 --> 00:15:36,392
in the limit, these two functions will be
the same.