Instructor (Brad Osgood):Is the screen fading and yes, Happy Halloween to everybody. Only one noble soul here came dressed as a Viking. All right. All right. I’m glad to see that sort of pioneer spirit is still with us, as ridiculous as it looks. All right. Okay. Let me call your attention to the information on the board. Mid-term exam is today. There are three sessions, from 2:00 to 3:30 and from 4:00 to 5:30 are both in building 380, room 380W. That’s the basement of the math corner, and from 6:00 to 7:30 is here. Okay. We will provide you with the exam, with a formula sheet, which you already have seen as has been posted on the course website for some time, and blue books. All right. Any questions. It’s an open book, open notes. You can bring your stuff with you, but as I say, don’t bring these stacks of signals and systems book as I’ve seen in the past. You’re only going to waste your time. Any questions about anything? I’m somehow not surprised to see a thin crowd out there today.

It’s a shame because, actually, today, I’m gonna be talking about sampling and interpolation, which is my favorite topic in the course. It’s really too bad that no one is going to be here to hear it. But I’ll persevere somehow. All right. So no other questions about the exam or anything else on anybody’s mind? All right. So let me remind you, again, the topic today, and we’ll pick it up again next time, is sampling and interpolation. There’s a lot to say and, as with many things, we can’t say it all, so I want to get the main ideas across and the main phenomena’s that are associated with it. Our approach to it is gonna be an application of what we talked about last time with the Shaw function so I want to remind you of that. So last time we introduced this train of delta functions, sometimes also called the Dirac comb or the Dirac train or a pulse train or an impulse train or all sorts of things. We introduced the Shaw function of spacing P some from – I’ll put the variable in there, so some of delta functions evenly spaced, P apart. So K from minus infinity to infinity and delta X minus K P. All right. And it has several important properties that I will list.

So the picture is a bunch of evenly spaced delta function all up and down the line. So it’s usually indicated something like this, P 2 P and so on minus P minus 2 P also and so on. All right. There’s three very important – and we introduced this in the context of an important physical problem and quite an interesting physical problem that of studying X-ray diffraction. All right. The mathematical properties that allowed us to analyze that problem so effectively, are the same mathematical properties that we’re gonna use today in a quite different setting, and I want to recall those for you. The three important properties – one is the sampling property, we used each one of these, but now I want to single them out. That is if I take a function and multiple it by the Shaw function, it samples the function at the points K P. So F of X times a Shaw function is the sum of F of K P delta X minus KP against [inaudible] infinity. I’ll get out of the way in just a second here. All right. That sampling property to the Shaw function falls from the sampling property of the delta functions. If you multiple the shifted delta by a function, it pulls out the value at the point times the delta function. You can read that well enough here. K times P. So that’s the sampling property. Allied with that, sort of the flip side of that, is the periodici, the periodizing property. And that has to do with convulsion that if I involve a function with the Shaw function of spacing P, I get a periodic function of period P. That is this is the sum of shifted versions of F, K going minus infinity to infinity, F of X minus K P. All right. So that gives you a periodic function of period P. I’m not worried about here of questions about conversions and things like that, I’m just worried about the formal properties and how they work.

They are, in some sense, flip sides of each other and we’ll see that very strongly today because convulsion and multiplication are sort of swapped back and forth by taking the Fourier Transform of the Inverse Fourier Transform for you. Okay. So in fact, there’s actually sort of two sides of the same coin. The final property of the Shaw function, the remarkable property that falls from this [inaudible] formula, the fact about the integers is the Fourier Transform property. That is the Fourier Transform of a Shaw Function spacing P is a Shaw function with reciprocal spacing with an extra factor of one over P out in front. Okay. That’s a very deep fact. Let me just say because I’m actually gonna use the corresponding formula for the Inverse Fourier Transform, so Inverse Fourier Transform formula is the same. I’ll just write it down. I won’t derive it separately. The Inverse Fourier Transform of the Shaw function of spacing P is the same thing, one over P – Shaw function spacing one over P. All right. These three properties were the basis for the mathematical analysis of X-ray – the fractions we talked about last time, and they’re gonna serve us also today in quite a different context. So here is the set up for the sampling and interpolation problem. In fact, let me call it the interpolation problem. Set up for the interpolation problem. It is not one problem, but rather it’s a whole category general problems which have been considered in different contexts, different ways since time and memorial. Okay. All right. The problem here is – and what we’re actually gonna solve in a quite remarkable way is the exact interpolation of values of a function from a discrete set of measurements or a discrete set of samples. So we’re gonna consider – this is what we’ll do. We’ll be able to interpolate all values of a signal or a function from a discrete set of samples. All right. We won’t be able to do it in this generality, that is, we’re gonna have to make certain assumptions that are gonna allow us to solve it, but even under fairly general assumptions, it’s surprising that you can do this at all, and it’s ridiculous to expect to be able to do it at worse somehow. To ask us a general question and to expect an answer for it is really maybe asking too much, but in fact, by employing the techniques that we developed, we can actually get an answer for this in fairly great generality and that’s extremely important practically. All right. Here’s the set up. Here’s the thing to keep in mind. Let me formulate this question again, fairly generally and then we’ll get to the assumptions that we have to make in order to be able to solve it in a reasonable way. All right. So imagine you have a process evolving time say, it doesn’t have to be time, but that’s the easiest way to think about it.

A process evolving in time. All right. And you make a set of measurements at equal intervals – some fraction of a second. Time intervals. Equal space actually turns out to be important in this context. All right. So you have a bunch of measurements. T not, Y not, T 1, Y 1, T 2, Y 2 and so on. All right. So you can think of this as a bunch of points, and I want to formulate the question really in two ways. So here’s T not, T 1, T 2 and so on. And here’s the corresponding points somehow in the plain, or just plotting them, T 3. Now, you might ask – fit a curve to those points or what is equivalent – interpolate the values at intermediate points based on the measurements that you make. There’s really two equivalent ways of formulating, so you might ask, one fit a curve to the points, fit a curve to the data or you might ask interpolate values of the function of the process, whatever it is, the function at intermediate points based on the sample values, based on the points you measure based on the measurements. All right. Those are reasonable – they are questions that are natural to ask and you can imagine all sorts of context for this. And there’s many ways of doing it. All right. As a matter of fact, if you’re doing 263, you’d probably talk about lease squares, approximations to a set of data.

We actually don’t track the data, but you find somehow the line that best fits the data. But you can imagine drawing a curve like this, you can imagine doing it with straight lines, straight line – I was going to say straight line interpolation, but I’m mixing the two aspects of the problem. But something like this. You could do this or you can imagine fitting it with a polynomial or some other kind of curve where you might go up, you might go down, you might go up again somehow, but you want to actually track the values exactly. Okay. But there again, there’s not a unique solution for this. There’s many ways of doing it depending on the particular problem. Now, and again, it’s almost silly to prefer – well, you may have a reason for preferring one over the other, but you better have an extra argument to justify one choice over another. There’s many ways of doing this. Many possibilities. All right. And the question is how would you choose one over the other or choose any at all for that matter. Why would you expect to be able to do this? Well, you might want to refine, if it’s possible, you might want to refine your options or narrow your options by making more measurements. All right. If possible, you might make more measurements to suggest a better fit or better interpolation or more accurate interpolation. A better fit or more accurate interpolation. Let me make sure you know what I mean here when I say interpolation, all right, and what you’re actually getting. If you write down an explicit function or set of functions that tracks this data – and what I mean by interpolation is that you can find the valuate intermediate points, the reported value of the intermediate points, by plugging into your formula. All right. So you write down a formula for the straight line that goes from here to here, that means you can find every point on that straight line. You have a formula for that.

Why question the straight line from here to here and from here to here or if you have a polynomial that somehow does this or maybe does a piece wise things and maybe goes that then you can find the value at any intermediate point by plugging into that formula. That’s what I mean by interpolation. All right. So all values are computable by knowing only these discrete values, and it’s an approximation. You don’t know whether that’s doing a good job or not doing a good job, but you’re making a guess and you’re making what you hope is a reasonable guess. All right. But that’s why I’m saying curve fitting and interpolation or equivalent sort of thing. One is a geometric way of looking at it by drawing a curve, the other is an analytic way of formulating it by actually trying to write down a formula for the function that’s doing the interpolation, and then plug into that formula and seeing how well it matches. All right. So again, what I mean by this is maybe you can make more measurements and then compare those measurements to your formula. All right. See if it’s working. Now, maybe you can do that, maybe you can’t. What is the enemy in this or what is causing uncertainty? Well, again, if this level of generality there’s more uncertainty than there is certainty. I mean, you know, you have a discrete set of values, who knows what the function is doing in between, but don’t stop at saying that. Try to say something a little bit more positive. That is, the thing that is causing you difficulty, the uncertainty in the values, in the extreme case, are the oscillations. How fast the function is changing from one value to the other. The more rapidly the function might be changing, the less certainty you have about interpolating the values in between from the measured values. All right. So the more bends the function takes, the more rapid bends or the more corners a function has, the more uncertainty you have in your interpolations – in your current fitting or your interpolation. Same thing. The problem here in interpolation, in uncertainty is the more rapid the bends are, the more uncertain you are in your interpolation, the more jagged somehow the process is between sample points, the less certain you are about how to interpolate between the sample points. All right. So you somehow want to quantify the jaggedness or the bends in the process – in the function. Now, we are pretty sophisticated in questions like that. We want to regulate, maybe even get rid, but at least regulate understand quantify somehow. We want to regulate – let me put it this way – how rapidly the function, the signal is bending or oscillating – I don’t quite know the right way of saying it or the right word for this, but I hope you know what I mean – oscillating – all right – between sample values. That’s gonna be an extra assumption, all right, between sample measurements, between sample values. All right. Now, this is gonna take the form of an assumption, but the question is what should the nature of the assumption be? All right. Now, as I say, we’ve actually gotten quite sophisticated in this sort of thing. For us, we think in terms of not just the function given in the time domain, but we also think of the function in the frequency domain. We think in terms of its Fourier Transform. The Fourier Transform in representing the function in terms of its frequency components tells us something about how fast the function is oscillating.

If it has high frequencies, high frequencies are just as Fourier Transform high frequencies are associated with rapid oscillations, low frequencies with smaller oscillations, less rapid oscillations. And so if we want to make an assumption that’s gonna eliminate rapid oscillations, we might make that assumption in the frequency domain, that is, it should be an assumption on the Fourier Transform. So this is governed by – this is a spectral property so it’s governed by the Fourier Transform. All right. That is an assumption on how rapidly the function is oscillating, is an assumption on the Fourier Transform, that’s one way of saying this a little bit more precisely. All right. Now, go right to – past the simplest assumption you can make along these lines. It takes a little experience to know this is the simplest assumption, but the idea is you want to eliminate all of – one way to think about this is you want to eliminate all frequencies beyond a certain point. All right. So that’s one possibility. You’re trying to analyze this. Maybe this one is good idea. Maybe there’s other ones that are good ideas. I’ll give you a clue. This turns out to be a good idea. One possibility is to eliminate, that is to assume, is to eliminate all frequencies beyond a certain point that is by an assumption. All right. Now, we’ve seen that many times. If this is what you want to get to, then make that a definition. Concentrate your attention for the interpolation problem on functions which satisfy a property like this. We are ready for an importation definition. The enemy – the problem is rapid oscillation between those measured values. Our approach to that problem to resolve that uncertainty is to say I’m gonna regulate how rapidly the function is allowed to oscillate.

And I’m gonna phrase that as an assumption on the Fourier Transform of the function, all right, because the assumption on the Fourier Transform is an assumption on the frequency components. If you eliminate high frequencies you feel like you’re eliminating rapid oscillations, and I’m gonna state that as a definition. So you state a function, F of T, is band limited. If it’s Fourier Transform, is identically zero outside sum, band of frequencies. That is F of S – the Fourier Transform is identically zero for S greater or equal to P over 2. I’m gonna write it like that. All right. You’ll see why in a little bit. For some P. And then, the smaller such P is called the bandwidth. The smallest such P for which this is true the bandwidth. All right. So the picture is – but the Fourier Transform is identically zero outside finite interval. And I’m working with real functions here, so the Fourier Transform is symmetric so that’s why I have absolute values. You can give the definition more generally, but this is the most natural setting for it. So here’s the picture. He’s zero, here’s P over 2, here’s minus P over 2 and whatever the Fourier Transform does in between, and it can’t do that exactly, because it’s supposed to be symmetric – it’s zero outside of there. All right. This is the Fourier Transform. All right. So that is supposed to capture the idea that you are eliminating the size of the frequencies, you are limiting, in the time domain, the oscillation of the function by making this assumption in the frequency domain. Okay. Now, what I want to do is I want to show you that for band limited signals you can save the interpolation problem exactly. It’s remarkable. For band limited signals, you can solve interpolation problem exactly. You get a formula for F of T for all T for all T. In terms of values of F at a discrete set of points. T – let me just call them T of C K sample values. All right. You can fit that curve exactly. That is to say, if you know the process comes from a function which is band limited, you can write down a formula for the function. All right.

Now, in the notes, there’s a different sort of discussion of this. I’m gonna go right for the kill. All right. I’m gonna show you how this works and it’s nothing short of remarkable. It’s almost obscene the way this thing works, I think. It’s the most remarkable – I think it’s the most remarkable argument in the whole subject practically, and as I say, it’s one of my favorite arguments because it’s just obscene and it makes me feel cheap and dirty. It’s great. The notes has a discussion of this, but it goes a little bit farther. I’m not gonna go through that. That is in terms of trigger metric functions, why you expect something like this to occur, why you might expect something like this to occur in different circumstances. We’ll circle back and talk about some of these things, but for right now, I want to go, as I say, right for the kill. I’m gonna show you how this works. I’m gonna give you the argument. – and in evolves exactly – the periodizing property of the Shaw function and the sampling property of the Shaw function and the Fourier Transform part of the Shaw function. Those three properties come into this in a very essential way. All right. Again, here’s the pictures of the frequency. I’m just gonna do this. All right. And there’s no way of saying of it other than I’m going right for the kill. Just enjoy the ride. All right. Enjoy the experience because it’s amazing to see this thing unfold. All right. So here’s the picture of the frequency domain again. The pictures like this. So I’m assuming the signal is band limited so that means Fourier Transform only is non-zero between minus P over 2 and it might have some zeros in here, okay, all right, I’m not saying it doesn’t have any zeros in between, but I’m saying that for sure, it’s identically zero outside this interval. All right. Now, I’m gonna use the Shaw function with spacing P to periodize this, all right, by convulsion. That is, I look at – let me draw the picture for you. I look at the Fourier Transform of F convolved with a Shaw function of spacing P. All right.

So what is the picture? The picture is here’s the Fourier Transform minus P over 2 to P to over 2. I’m gonna make it a little bit more condensed here. Minus P over 2 to P over 2. All right. Here’s the Shaw function with spacing P. There’s a delta function there. This is P over 2. The next delta function is a P. The delta function over here is a minus P and so on and so on. All right. Here’s zero. All right. Now, what does it do when you convolve the Shaw function with this, it shifts it by P and adds it all up. All right. So the picture of the convolution of the Fourier Transform with the Shaw function looks something like this. Here’s zero, here’s minus P over 2, P over 2, it shifts the whole thing over to P down to minus P and so on. So you get just a bunch of repeating patterns of the thing. But there’s no overlap because the Fourier Transform is zero outside of the interval for minus P over 2 to P over 2, so if you shift it by P, there is no overlap when you convolve. All right. Now you say, brilliant, you have done something and you have undone something. This takes a PhD? Yeah.

Student:[Inaudible]

Instructor (Brad Osgood):Where? No, this should not be convolution, it should be multiplication. I’m multiplying by a function which is one on the interval from minus P over 2 to P over 2 and zero outside that interval. So that gets back the original Fourier Transform. All right. The original Fourier Transform is here and it’s only there. All right. It’s only there. When you convolve it, you get a bunch of repeating patterns. You add them all up. But you cut those off. All right. Cut those off. And that leaves you with this, which is the original Fourier Transform. This is the whole ballgame. All right. The most important equation here is exactly this equation. I’ll write it down again. The Fourier Transform F is the cutoff of the P Fourier Transform.

All right. And you say great. You’ve done something, you’ve undone something. You know, you got a PhD for this; this is why they call you Professor? Now, take the Inverse Fourier Transform. It looks like you haven’t done anything, but actually, you’ve done something extremely significant because by taking the Inverse Fourier Transform, it swaps multiplication and convulsion. This is a picture in the frequency domain. What is happening in the time domain? So take the Inverse Fourier Transform. Well, on the left-hand side the Fourier Transform of the Fourier Transform is just F, so F is equal to the Inverse Fourier Transform or the Fourier Transform. Right? That’s fine. Now, take the Fourier Transform, that gives you back the original function because I’m taking the Inverse Fourier Transform and the Fourier Transform. Right. The Inverse Fourier Transform of the right-hand side, again, it swaps, let’s do this a little bit at a time here. It swaps convolution and multiplication. That is to say it takes multiplication back to convolution. This is the Inverse Fourier Transform or the rectangle function; convolve with the Inverse Fourier Transform of this. Follow along.

Enjoy the ride. Enjoy the ride. All right. All right. Let’s look at this part here. Well, I’ll write it out a little bit. One step at a time. The Inverse Fourier Transform of the rect function is a scaled sinc function. The Inverse Fourier Transform of the rect function of spacing P is sinc P T. If you don’t believe me, figure it out yourself. All right. The Inverse Fourier Transform of this, again, is gonna swap convolution and multiplication. The Inverse Fourier Transform of involved with the Shaw function is gonna be the Inverse Fourier Transform of the Fourier Transform. What the heck. Too many Fs of the Fourier Transform of F times the Inverse Fourier Transform of the Shaw function times. Okay. I don’t know if we stated the convulsion theory – I don’t know if I stated it, I’m sure it’s in the notes, we stated the convolution theorem in terms of the Fourier Transform, same thing holds in terms of the Inverse Fourier Transform. Okay. Swap convolution and multiplication. All right. Now, once again, the Inverse Fourier Transform of the Fourier Transform is just the function. The Inverse Fourier Transform of the Shaw function of spacing P is a Shaw function of spacing one over P. So this is F of T times one over P times the Shaw function of spacing one over P times FT. I guess I’m using T as my variable here. Okay. Now, I could combine all the formulas at once here, but let me not do that. Let me take this one step further. Now, remember now, we’re gonna use the sampling property of the Shaw function. We used the periodizing property of the Shaw function in the frequency domain. When we periodize the Fourier Transform. Now, in the time domain, I’m gonna use the sampling property of the Shaw function.

All right. If I multiple F and T times this, now remember, I’ll take this out one more step before I don’t know remember what it is, one over P, that’s a constant that just comes out in front of the whole thing. It’s one over P times F of T times the sum of deltas minus infinity to infinity spaced one over P apart, T minus K over P. All right. Now, I use the shifting property of the delta function so it’s this Fourier Transform function, P times time P T convolve with this sum of deltas. All right. So I’ll take this out one more. The P cancels with a one over P, so this is sum K equals minus infinity to infinity. These are constants. F of K over P times a sinc function, the scaled sinc function convolved with delta T minus K over P. All right. And now you use the shifting property of the delta function and write this as the sum of the sample values and it is the sum from K [inaudible] minus infinity to infinity, F of K over P times the sinc of P, T minus K over P. Which is actually the way I prefer to write this, but many people write it like this – they multiple by through by P. Some from K equals minus infinity to infinity, F of K over P sinc of P T minus K. We’re done. We’re done. We found a formula for the function at all values of T in terms of its sample values. I’ll write it down. This was a long chain of equalities here. We have shown that F of T is equal to the sum from minus infinity to infinity, F of K over P sinc of P – I’ll write it like this, T minus K over P. We have interpolated all of the values of the function, at all values of T, in terms of sample values, evenly spaced points. All right. So my T Ks, in the way I originally formulated the problem, are one over P, two over P, three over P, minus one over P, minus two over P, minus three over P and so on and so on. If you know all these discrete values, then you can interpolate all the values of the function in terms of those. I think it’s the most remarkable formula in the whole subject. So again, the assumption was – I want to go through this one more time to make sure you have this. This is called the sampling theorem, the sampling formula, sometimes called the Shannon sampling formula, sometimes call the Whitaker sampling formula. It’s associated with a lot of names. Unfortunately, my name is not associated with this formula as you can tell how much I love it. All right. So again, the assumption is that if the Fourier Transform of F is zero, for S greater than or equal to P over two than you have this formula for the function, sum from minus infinity to infinity, F of K over P, sinc P times T minus K over P. All right.

Now, for me, the sampling formula is identical with the proof of the sampling formula. All right. And that’s important because I think next time we’re gonna talk about – I don’t think I’m gonna push this into this time – we’ll talk about when things go wrong, as well as when things go right, but for me, I never think of this formula alone in isolation without the miracle equation that makes it work. All right. So this is all depending on the fact that if you periodize the Fourier Transform and then cutoff, you get the Fourier Transform back. But this is the rectangle function of spacing of with P times the Fourier Transform of F convolved with the Shaw function of the spacing of T. All right. It followed, although I tried to stretch it out for dramatic purposes, it follows immediately, lightening fast, just very mechanically by applying the Fourier Transform from this formula. This is what’s essential. All right. And so for me, and I’m serious about this, the sampling formula, this formula, is identical with the proof of the sampling formula. All right. To understand this formula is to understand this formula. They are the same. Okay. They are the same. It’s a consequence of the Fourier Transform swapping convolution and multiplication and writing this down. It’s a simple, but exceedingly cunning idea. Why do something like that? You know. It seems like you’re not gonna do anything. You’re periodizing and then cutting off and you get back the original function. It’s like proving one is equal to one. What is the big deal? You know. But the fact is that the reason why something non trivial happens is because of this remarkable fact that the Fourier Transform is going back and forth between the two domains, swaps convolution and multiplication. You have a combination of both of them in fact. You have convolution and multiplication in the frequency domain, you take the Inverse Fourier Transform, you have convolution and multiplication in the time domain, but the roles are swapped. All right. That’s why periodizing in the frequency domain turned into sampling in the time domain. All right. Because of this formula and because of the way the Fourier Transform swaps convolution and multiplication. All right. I’ll tell you what. Since it’s been my habit to keep people late in class, I think instead, today, we’ll get out early. I want to more about the consequences of this remarkable formula next time, including, sad to say, when things go wrong, but when things go wrong, they can all be explained by when this formula is not correct, when something is not right with this formula. All right. Okay. That’s it for today. I’ll see everybody later at various times and –

[End of Audio]

Duration: 43 minutes