Minh Vu Blog

TheFourierTransformAndItsApplications-Lecture27



Lecture 27 TheFourierTransformAndItsApplications-Lecture27
50 min
Topics: Higher Dimensional Fourier Transforms- Review, Fourier Transforms Of Seperable Functions (Ex: 2-D Rect), Result: Formula For Fourier Transform Of A Seperable Function, Example: 2-D Gaussian, Radial Functions, Proof That The Fourier Transform Of A Radial Function Is Also Radial, Convolution In Higher Dimensions

http://www.youtube.com/watch?v=8Snl2iMqCx4


Instructor (Brad Osgood):Hello. I hate it when I do that. All right. Here's some information on the final exam. Some of this you know. Some of this you don't know. What you do know or what you should know is that it's on Thursday the 13th from 8:30 to 11:30 in the morning. The new information is the location for it. The Dinklespiel Auditorium. I'm not sure if I spelled Dinklespiel correctly, but that's where it's going to be. I'll post that to the website, and I'll announce it many times.

It'll be open notes, open book as before. I will post last year's final exam. Maybe I'll do that today, actually, so you get a chance to look at that. I will also provide you with a formula sheet. Same one as we had for the midterm. It was a comprehensive formula sheet. You can also print that off, of course. We'll talk more about the exam and the mechanic of it in due course, but we already have a location established for it. Any questions or comments on that?

All right. So today, we're going to continue our discussion of the higher dimensions. We're going to continue our trip in the outer reaches and talk about getting to know your higher-dimensional Fourier transform. The main point that I started to make last time, and I want to repeat, is that you already know your higher-dimensional Fourier transform because you know your one-dimensional Fourier transform so well.

The point [inaudible] getting to know your higher-dimensional Fourier transform. As I said, you know it. You have to convince yourself of that. There are differences, and I'll highlight some of them a little bit today but even more so next time. Again, the point of using the notation that we've used and the approach that we're using is to make the higher-dimensional transform look as much like the one-dimensional transform as possible.

The formula's carried over. We'll start to see some of those today. The ideas carry over. There's no reason to think of it as a completely different subject. Let me remember the definition here. I'm going to remind you of the definition and the elements that earn interest. So you have a spacial variable and a frequency variable and then a function and a transform from one domain to the other domain. So I usually write the spacial variable like this.

We have the frequency variable. I call it xi one through xi N. Same dimension. We have a scaler value function which could be real or complex. But it's not vector value, so it's a real value function or a complex value function. Its Fourier transform is a function of the frequency variable. It's defined by this integral, which we tried to make look as much like the one-dimensional case as possible. You integrate all [inaudible] space, E to the two pi I, minus two pi I, X dot xi, F of X, DX. I'm even making it look as much like the one-dimensional case as possible. I still couldn't fit it all on one line.

Let me write it over here again. The Fourier transform of F at xi – I'm just going to rewrite it – is the integral over all space, E to the minus two pi I, X dot xi, F of X, DX. The new future here is the dot product. You take the dot product of the two vectors, X and xi. That gives you a scaler. You take the complex exponential and apply it to that. Writing it this way makes it look as much like the one-dimensional case as you can make it look.

We'll even see that the formulas look similar, and even the approach to proving the similars is also very similar. Now, I do want to follow a similar path to what we did in the one-dimensional case. That is, looking at specific transforms and specific functions. I'll do less of that, and then also looking at general formulas, versions of the shift theorem and the stretch theorem and so on. I'll do many not quite as much of that as I did in the one-dimensional case where we saw it in more detail. There, actually, it's in the general formulas that you start to see a few differences that start to crop up between the one-dimensional case and the higher-dimensional cases.

This is where some of the interest is, but let's do a couple of simple examples first, of computations. There's an important class of functions for which you can computer a higher-dimensional transform by computing a series of lower-dimensional transforms. There's a class of examples for which you can compute a higher-dimensional transform via one-dimensional transforms. Maybe I should just say lower-dimensional transforms. Typically one-dimensional transforms.

What I'm taking here are what are sometimes called separable functions. I don't think there's a uniform term to describe them, but let me give you and example here. These are separable functions. They come up often enough that there's enough example of them. They come up often enough in applications that it's worthwhile just calling to attention to them.

The easiest and important example is like the two-dimensional – let's just do this in two-dimensions, but you can do the same thing in higher-dimensions. Let's work in 2D. One of the most basic examples and important examples is the two-dimensional rec function. So I'll call that pi of the rectangle function of X1, X2. The graph would look like the two-dimensional version of the graph of a one-dimensional rectangle function. That is to say – let's see if I can draw a picture of this thing here. So here's the X1, X2 plane. It's a box. It's a box. This is one of those IQ tests. Can you draw this box. The answer obviously is no.

This is a function which is one over a rectangular region in the plane. Very good. Perfect. That's fine, Mr. Osgood. Now try doing this basket for us. It's supposed to be equal to one over this box in the plane. It's equal to zero outside the box. Let me try to draw perspective here.

So here's the X1, X2 plane. Here's the box that goes from minus one-half to plus one-half in the two different directions. The two-dimensional rectangle function is one over that box and zero outside the box. You can decide, depending on your religion, what you want to do on the boundary. It's equal to one if X1 in absolute value is less than one half, and X2 is less than one half. It's equal to zero otherwise.

That's fine. You could write down the formula and definition that way, and that generalizes the one-dimensional rectangle function. That's a really pathetic drawing, isn't it? What's maybe not so obvious is that the two-dimensional rectangle function can be written as a product of one-dimensional functions. That's the point I want to make.

So you can write the two-dimensional rectangle function as a product of two one-dimensional rectangle functions. In fact, it's easy to write, and I will let you convince yourself of this, that it's just the rectangle function of the one variable, X1, times the corresponding ordinary rectangle function of the variable X2. So this is one between X1. If X1 is between a half and a half and zero otherwise, and this function is one if X2 is between minus one half and a half and zero otherwise. If you take the product of those two functions, that describes exactly this condition. It's equal to one if both variables, X1 and X2, are between minus a half and a half. It's equal to zero if either one is outside that interval. If either X1 or X2 is outside the interval from minus one half to one-half.

Not all functions can be decomposed this way, but when you can decompose a function this way, then it's easy to compute the Fourier transform. It's something to watch for. Again, it happens often enough, and it's worth calling attention to it as an important special case because now you have a Fourier transform of F at xi one, xi two. It's equal to by definition – so I'll write it out in coordinates – the interval from minus infinity to infinity. E to the minus two pi I, X1, xi one plus X2, xi 2 times pi, X1, X2, DX1 and DX2. That's just the definition of the Fourier transform. It take the entire, damn board.

That's only two dimensions. Now you can split the variables up. You can write this as – let me combine two steps here. Complex exponential, the exponential function being what it is, you can split up that inner product in the exponent to be minus two pi I, X1 times xi one times E to the minus two pi I, X2 times xi two. Then, as I just pointed out, a two-dimensional rectangle function can be written as a product of two one-dimensional rectangle functions. DX1, DX2. Now you sort of look ahead a little bit and see what happens. Things decouple.

The X1s and X2s are independent. That is, you can write this as a product of two integrals which are, then, just one-dimensional Fourier transforms. So this is equal to the integral from minus infinity to infinity, E to the minus two pi I, X1 times xi 1, times pi of X1, DX1 times the integral from minus infinity to infinity, E to the minus two pi I, X2 times xi two, pi of X2, DX2. We've done this many times going the other way. We've done this many times in a variety of circumstances, taking the product of two integrals and converting them to a single double integral here. I'm going the other way around.

I'm taking the double integral and because the variables are decoupled, I can write that as a product of two single integrals. Now you just [inaudible]. This is the Fourier transform of the rectangle function, but you have to pay attention to what the variables are named. That is, it's the product of – so what do you get for the first one? You get the sync function of xi one because I'm taking the Fourier transform with respect to X1 and the dual variable here is called xi one. Then the second integral, it's a Fourier transform of the rectangle function again.

But the dual variable, the variable I'm integrating, is X2, and dual variable in the frequency domain is xi two. So it's just the product of [inaudible] functions. Sync xi one times sync xi two. Are there other tongue twisters we can try?

You can look at the notes for a picture of that. You get a nice picture of the product of two sync functions. We were able to do this because we were able to rely on our one-dimensional knowledge to get a two-dimensional result because the function was separable. That happens often enough that, as I say, it's worth pointing out. In general, what is the situation?

In general, if you can write a function of N variables, and you can't always do this. I want to emphasize this. You can't always do this, but in some cases, you can. If you can write it as a product of functions of one variable or functions of a lower dimension, say F1 times X1 times F2 times X2 for some functions. I'm not saying there's a procedure for doing this, and I'm not saying it's always possible. It's not always possible, and there's not always procedure to do it. You can.

Then the Fourier transform of the function of several variables can be written as the product of the Fourier transforms of the functions of one variable. So if you can do that, then you can write – and I won't derive this – the Fourier transform of the big function at the big frequency variable is the product of the Fourier transforms of the little functions at the single frequency variables, Fourier transform of F1, Fourier transform of F2, xi two times xi N.

There are various combinations of this. Maybe you can write it as a function of one variable times a function of two variables, if F is a function of three variables, say. X1, X2 and X3, maybe you can decompose it as the product of a function of two variables times the product of a function of one variable or whatever. I'm not saying that there's any blanket thing that's going to work or that you might expect to happen, but it is the sort of thing to look for.

That's what I mean by separable functions. Let me give you another example, actually, that will lead to another important class of functions. We'll handle it one way, and we can also handle it another way. So another example – really, I'm just going to do most of these examples in two dimensions because I don't have the patience or the strength to write anything out in higher dimensions. Another example is the 2D Gaussian. The 2D Gaussian, I call it G. Say G of X1, X2 would be E to the minus pi, X1 squared plus X2 squared.

Again, if you drew the graph of that as a surface in space, and I think the graph is drawn, you'd see a two-dimensional bell-shaped curve or surface. Now, that's also a separable function because – in fact, it's a product of two one-dimensional Gaussians just because of the property of the exponential function. Exponentials being what they are, you can write this as E to the minus pi times X1 squared times E to the minus pi times X2 squared. So it's a product of two one-dimensional Gaussians. We'll call it G1 of X2. G2 of X2, although it's really the same function in both cases where G1 is E to the minus pi one X squared. G2 is E to the minus pi two X squared.

So the Fourier transform of the two-dimensional function is the product of the Fourier transform of a one-dimensional function. So the Fourier transform of G and xi one, xi two is the Fourier transform of G1 at xi one. The Fourier transform of G two at xi two. We know what happens if I take the Fourier transform of a Gaussian. You get it back. That's the remarkable property of the Gaussian. That's equal to E to the minus pi xi one times E to the minus pi xi two squared.

That's fine. Now, actually, the nice thing is – so that uses a separability. Now you can recombine these. You can leave it like that. That's a perfectly fine answer, but a finer answer is to recombine. That is, write this as E to the minus pi xi one squared plus xi two squared. Again, exponentials being what they are, and you're back to where you started. That is the Fourier transform of two-dimensional Gaussian is another two-dimensional Gaussian.

So F of G, xi one, xi two, is equal to E to the minus [inaudible] itself. Xi one squared plus xi two squared. It's nice.

So our one-dimensional knowledge and expertise, in this case, lends itself to understanding a higher-dimensional phenomenon. You could do the same thing in higher dimensions. You could have a higher-dimensional Gaussian. You should be able to imagine instances where you want to consider higher-dimensional Gaussians. If you think of a Gaussian, the bell-shaped curve describing a set of measurements, then instead of taking one measurement, you're taking many measurements. They can be distributed normally, so distributed according to a higher-dimensional Gaussian. That's okay. You want to know the higher-dimensional Fourier transform of a higher-dimensional Gaussian.

Of course, you have higher-dimensional versions of the central limit theorem and all that stuff. It all carries though, and it all carries through pretty much the same because you can make the higher-dimensional case look like the one-dimensional case. You're not seeing any new phenomenon. They're the same sort of things that come up at higher dimensions have already come up at one dimension. That's the power of this approach.

Now, one reason why I wanted to do the Gaussian is because not only is the gaussian separable, the gaussian actually has another property that is an illustration of another important class of functions that come up a lot in applications. So consequently, there's a lot of special things you can say about them as far as the Fourier transform goes. Namely, the gaussian is radial. So the gaussian is also an example of a radial function.

Now by that, I mean if you introduce polar coordinates, there's some circular symmetry to the gaussian. So if you introduce polar coordinates, that is R equals the square root of X squared plus Y squared, or R squared is equal to X squared plus Y squared. Theta is equal to R10 of Y over X. Going the other way, X equals – let me use X1 and X2. Let me be consistent here.

X1 squared plus X2 squared – sorry, I'll get out of the way in just a second. X2 divided by X1 – let me write it over here. So I'm introducing polar coordinates in the X1, X2 plane. So X1 is equal to R, cosine of theta. X2 is equal to R sine theta. Then of course, the gaussian is just E to the minus pi R squared. It depends only on R, the radial distance from the origin.

E to the minus pi, X1 squared plus X2 squared is E to the minus pi R squared. That's what you mean when you say it's a radial function. If it depends only on R. This depends on R squared, but this depends on the distance from the origin, not X1 and X2, independently, so to speak, but on X1 squared plus X2 squared.

So it depends only on R, not on X1 and X2 independently, if you know what I mean. I’m sort of caught in a language here, independently. So to put quotes around that because from what I've said before, it's separable if it depends on X1 and X2 separately but not independently. Okay? Sorry for the clash of language. I don't know how else to say that.

So this is something that comes up really in two dimensions or in higher-dimensions that wouldn't come up in one dimension. In one dimension, you have only one variable. One variable's describing the position or the time or whatever. In space, it's a little bit different. You have a little bit more freedom. You have two degrees of freedom instead of one degree of freedom. So it makes sense to consider the class of functions that depend only on, say, the distance from the origin. Those are the radial functions. You don't see that in one dimension.

So radial functions, in general, depend on the distance R from some origin. You can fix the origin. You see many examples like this. They come up all the time in applications. The important thing is, as far as Fourier transforms are concerned, is that the Fourier transform of a radial function is also a radial function. That's what I wanted to show to you.

Let me write it over here. So I want to see – this is actually a little tricky. The Fourier transform of a radial function is also a radial function. Now, this is a little tricky. There are actually a lot of interesting things to say around these ideas. I don't think we're going to be able to get into this, but let me make a comment here. We're going to get a somewhat complicated formula for the Fourier transform of a radial function. So we'll get a formula for this. We'll convert the usual definition of a Fourier transform into a radial Fourier transform. They have another name. We call it Henkel transform.

In many applications, radial functions are a more natural way of describing the phenomenon. The problem is that the Fourier transform as its given, the definition of the Fourier transform, is a very cartesian thing. I'll say this more precisely when I actually write down the formula for it, but I just want to set the stage. I want to mention something we may not have a chance to talk about, but you should be aware of it.

So we're going to get a formula for this. It's going to be a bit more complicated. This causes all sorts of problems in applications because the Fourier transform itself is set up in sort of a cartesian form. It's sort of the definition involves an inner product, and the inner product somehow looks very cartesian. Consequently, the Discrete Fourier transform and the algorithms for evaluating the Discrete Fourier transform are also very cartesian in nature.

To implement a Discrete Fourier transform and the algorithms that go with it for two dimensions and higher dimensions, it requires that you put down a cartesian grid. In many cases, the functions your interested in don't fit naturally on our cartesian grid. They fit much more naturally on a polar grid. You don't have analogous formulas for the Discrete Fourier transform and for the FFT algorithm for polar grids, and it's a problem.

Where is it a problem? One big area where it's a problem is medical imaging where the way you take samples and the way you actually work with your functions is much more naturally described in polar coordinates than it is in cartesian coordinates. You want to do a lot of serious computation, but it's not set up for it. It's not set up for it because the formulas somehow, on the one hand, the [inaudible] algorithms, the efficient algorithms are all set up in the cartesian world for rectangular coordinates.

The phenomenon that you want to compute are much more naturally described in polar coordinates. That's a problem. It's a hack job to get around it, actually. I may not know the state of the art, but I believe that it has to be gotten around but not really dealt with, theoretically. There's no way of doing it other than hacking, to tell you the truth.

So now let me show you what the issue is here. So what I want to do – the only thing I can do is convert the formula for the Fourier transform into polar coordinates. So the formula for that, and I'm just going to do that in two dimensions. The formula for the Fourier transform is the interval from minus infinity to infinity, E to the minus two pi I, X1 times xi one plus X2 times xi 2. F of xi one, xi two. Sorry. X1, X2. I'll get it. DX one, DX two. So all I want to do is convert this to polar coordinates. That's all I want to do, but that's where complications come in. Some of this is straight forward.

We're assuming that F is a radial function, so I want to convert to polar coordinates in both planes, actually. Both the X1, X2 plane the xi one, xi two plane. So let me write X1 is equal to R cosine theta. X2 is equal to R sine theta for polar coordinates in the X1, X2 plane. But I also have the frequency plane, so let me introduce polar coordinate there. I got to call it something else, so I'll call it row, cosine of phi, and xi two is going to be row sine of phi. Same interpretation of polar coordinates, but instead of calling it R and theta, I'll call it row and phi.

As we will see, the Fourier transform of F, if F is a radial function meaning that it's a function of R, the Fourier transform of F will be a function of row. That's what we're going to see. So we'll see that if F is radial, a function of R, then the Fourier transform of F is a function of row. That's what it means to say that the Fourier transform of a radial function is again, a radial function. That's what it means.

So I'll just do this. So part of the conversion is easy. That is, F of X1, X2 is converted into F of R. So I'm assuming it's a radial function. So it needs the function of R, whatever the formula is. I know what happens to the area element. With DX1, DX2, the area element gets converted into RD, RD theta. That's the area element and polar coordinates in the X1, X2 plane.

It gets more complicated in converting the inner product. That's when I say it's very cartesian. That's what I mean when I say it's very cartesian. You have to convert the inner product. What is the inner product? It's X1, xi one, plus X2 times xi two. So I just write this out. It's R cosine theta times row cosine phi plus – that's X1 times xi one times X2 times xi two. It gives me R sine theta times row sine phi. So the R and the row factor out of both terms. That's R times row, cosine theta, cosine phi. Plus sine theta, sine phi.

If you remember your addition formulas for the cosine, and I'm sure we all do, that is R row times cosine of phi minus theta. So this is R row cosine of theta minus phi. What happens to the Fourier transform? I said it's complicated, the complications are about to come up. It's straight forward just to plug formulas in and convert mechanically from cartesian coordinates to polar coordinates. So I get the Fourier transform of F becomes what?

The Fourier transform becomes the integral – I only put the [inaudible] of integration in. So I'm going to have to describe the whole plane. So to describe the whole plane, theta's going from zero to two pi, and zero is going from zero to infinity. I'm going to integrate RD, theta DR. It doesn't matter. So what happens to the exponential?

It becomes E to the minus two pi I, R row, cosine of theta minus phi, times F of R, times R, D theta, DR. Do I have it all? I have it all. That's the formula for the Fourier transform. That's what you get mechanically converting the two-dimensional cartesian Fourier transform into polar coordinates. Now, you have to work with this a little bit more.

So there's something important to notice here. It's discussed in the notes, but I'm not going to prove it for you. Here's what you find. You find there's a fact that the integral from zero to two pi – I want to make sure I stay with my notes here. So there's an R integral and there's a theta integral. The only part the depends on – the F doesn't depend on theta. That's what it means to be radial, so it's this part here that'd depending on theta, but it doesn't just depend on theta alone. It also depends on phi, the angle in the other plane, the angle in the frequency plane.

But the fact is that this integral, E to the minus two pi I, R row, cosine of theta minus phi, D theta, actually is independent of phi. That's a fact that you can check if you look at the notes. I'm not going to verify that. Actually, it's not hard to verify, but it's one of these things you have to look at and know. If you didn't know that, your formula would become – you wouldn't be able to make any progress, as we're about to.

So to say that's independent of phi means that in fact, that integral is the same as if phi were not there. So in fact, the integral fro zero to two pi of E to the minus two pi I, R row, cosine of theta minus phi, D theta is equal to the integral from zero to two pi, E to the minus two pi I, R row, cosine of theta, D theta. I just leave the phi out. That's just grand. You see there's no F in there or anything. In some senses, it's just an ordinary integral. It's some function of theta integrated with respect to theta. There's no more phi in there.

The problem is, this is not an elementary integral. There's no formula for anti-derivatives that's going to allow you to evaluate this integral in closed form. You don't have a closed-form expression for this. So what do you do if you're a mathematical jerk at a point like this when you don't have a closed-form expression? You define your way out of trouble. You say, well, that just defines a new function. That's what that does. In fact, that's what's done. It's what pisses engineers off.

So define – and I'll give you the general definition. Let me write it down here. I have to copy it from my notes because I don't know it off the top of my head by any means. One over two pi. This is the integral that comes up – let me write it down, and then I'll say something about it.

E to the minus IA, cosine of theta, D theta. A is a real number, here. You can see that what I have here is a version of that. I have two pi R row and so on. This is called – then the integral that I have, so we have – what do we have? We have two pi times [inaudible] of two pi R times row. That's what we're dealing with here, with this integral. J-not is called the zeroth order bessel function of the first kind.

Be very afraid. There are several terms that ought to make you afraid. Zeroth order. That would suggest that there's more than one order, like first, second, third, fourth, and first kind would suggest that there's more than one kind. All that's true. There are bessel functions of many orders and many kinds. They always come up – bessel functions always come up in the context of radial functions. Any time you're dealing with radial – and be aware of this. If you're dealing with problems that have circular symmetry, chances are you're going to come across bessel functions. The other reason for that is often there are partial differential equations involved that are describing the phenomenon.

Often, one does a separation of variables that assumes the solution is a product of an angular function and a radial function. Very often, the radial function or the angular function has solutions which are bessel functions. Equations are of a certain type, and the solutions are bessel functions.

So if you were a British student in the early part of the 20th century, you would learn all about bessel functions of eery order and every kind because that's what all British students had to learn for the competitive exams they had to take. There is a famous book by G.N. Watson called, A Treatise on the Bessel Function, which runs something like 800 pages or something like that.

The publisher wanted Watson to do a second addition of that book, but he didn't have it in him to do a second edition. There was a second printing, and I think the second printing says something like, since the publication of the first edition, my interest in the bessel function has waned. One might expect, right? But what can I say? These are special functions of mathematical physics, as they're called, they just come in the applications. Now they're all hard wired into mathematics and hard wired into Matlab and things like that so that you can draw graphs of these things. You can compute with them and so on. You don't have to have, somehow, the same kind of intimate knowledge that was the terror of British students' lives in the early part of the 20th century, but they still do come up.

So now, what is the consequence of this for us? So now we conclude the Fourier transform of F of R, a radial function, is – I will call it. And we see that it's going to be a function only of row, not of phi because the phi is gone. F of row is the integral – I'm going to write it down here. I have to be careful. Two pi times the integral from zero to infinity of F of R times [inaudible] of two pi R row, DR. No phi. The phi is not in there because of that fact.

This integral is independent of phi. I skated over that, but that is sort of the whole ball game. That says the Fourier transform of a radial function is also radial. I didn't do anything here except substitute the formula – substitute the definition of J-not for what our inner integral was when I was computing the Fourier transform. I converted the Fourier transform into polar coordinates.

This, too, has a name. Question?

Student:[Inaudible] for the DR? Instructor:

Oh, thank you. RDR. Thank you. Polar area. RDR. Now, in fact, this has a name. They call the zeroth order Henkel transformation.

So again, you can be a little afraid here because this is a zeroth order Henkel transform. You can believe there are higher-order Henkel transforms. I'm sorry to break it to you, but there are. We don't have to deal with it. So for us, the zeroth order Henkel transform is nothing other than the Fourier transform of a radial function.

The headline from this calculation is that the Fourier transform of a radial function is another radial function. That's important. I don't tell you this for the fun of it. This comes up in all sorts of different applications just because radial functions come up in all sorts of different applications. It's the kind of thing you have to know. You don't have to be intimately familiar with bessel functions and all the rest of that jazz anymore, but you do have to know these sorts of things. The basic fact you should walk away with is that radial functions go to radial functions under Fourier transforms.

Also, the thing to be aware of is that this can cause some complications on the computational side of things because some algorithms and some computations are set up in cartesian form, and they don't convert so easily into polar form. So that causes problems. Full stop, something new, something different. We're going to have – I'm not going to go through the same hit parade of Fourier transforms in the higher-dimensional case like I did in the one-dimensional case because the point is that what you know in one dimensions carries over to higher dimensions. I do want to go over how the theorems look because there, I want you to see how both things look similar and how things look different.

We don’t have much time today, so I don't want to get caught in the middle of something. Let me say a little bit about what happens to convolution and maybe the shift theorem. I may have to say the shift theorem and certainly the stretch theorem is where something very interesting happens that doesn't happen in one dimension. But let me mention convolution because here's something where it looks exactly the same as the one-dimensional case. So let me at least record that fact.

What is the definition of convolution of two functions? The definition of convolution of two functions can be made to look exactly the same as the one-dimensional case if you write it in terms of vectors. F convolved with G, at X is equal to the integral over RN of F of Y, G of X minus Y, DY. That's the same looking formula. Remember, F and G are scaler-value functions. So that's the ordinary product. There's nothing special there.

Now, you would not want to write this out in coordinates. You are much happier writing this out in vector form. Think about writing this down in the two-dimensional case. You would write F convolved with G of X1, X2 is equal to the integral from minus infinity to infinity of F of Y1, Y2 times G of Y1 minus X1, Y2 minus X2, DY1, DY2. That's what you would write out in the two-dimensional case. You certainly wouldn't want to write out the three-dimensional case. You wouldn't want to do that. Nobody would.

It's so many variables, so much space, so much pencil lead, but that's what it is. It's much easier to write out the definition in vector form. Now, here's something else you would not do. I tried to scare you off this, anyway. There's a whole file-and-drag way of life. The whole flip-and-drag religion of trying to visualize convolution. Flip this, drag that, screw you.

You would not flip and drag these higher-dimensional functions. Nobody in their right mind would try to flip G, drag F or do anything else when the graphs of these things are surfaces. The only case you could do it would be functions of two variables where you could visualize the graph as surfaces in R3 in three dimensions. Then you might think, I'll flip this, drag that, move it over the whole plane. I'll add it all up, and I can do that. That's worth my time.

Forget it. There's no way you could do anything like that in higher dimensions, but it is true that the standard interpretations that we have of convolution still hold. All the operations and all the interpretations of convolutions hold because the form is the same. The form is the same. It can be viewed as a smoothing operation. Maybe searing out the good properties of one function are inherited by the convolution. Just don't flip and drag. All formulas, properties, interpretations continue to apply.

That's good news. In particular, the Fourier transform property still applies. The so-called convolution theorem still applies. The Fourier transform of a convolution of two functions is the Fourier transform of F times the Fourier transform G. The Fourier transform of the product of two functions is the convolution of the Fourier transforms. All right? So the basis of signal processing is still with us.

Signal processing in higher dimensions amounts to, in many cases, taking the convolution of two functions in the spacial domain corresponds to taking the product of two functions in the frequency domain. To do filtering – now, one of the places this comes up, and you have a problem on this, actually, is images. We talked about this last time. What is an image? You can think of an image as a function of two variables, X1, X2, where the value, F of X1, X2, corresponds to the intensity.

Think about black-and-white images. [Inaudible] from zero to one. How do you do filtering, how do you do signal processing on images? Most often, you do it by some sort of multiplication in the frequency domain. The spectrum of the image times some thing, some mask, some filter that you are cooking up. You take the product in the frequency domain. That corresponds to convolution in the spacial domain. That's not the only way it comes up, but that's a typical way it comes up. The fact is, again, that convolution corresponds to multiplication if you take the Fourier transform. Same thing holds. I'm not going to prove it. It's the same proof, the same argument, as before.

You could've discovered higher-dimensional convolution the same way we discovered one-dimensional convolution by asking is there an operation, is there a way of combining two functions which corresponds to the Fourier transforms multiplied? That's what we did in one dimension. You could do the same thing in higher dimensions. Same thing because we've made everything look, in the higher-dimensional case, as much as possible like the one-dimensional case.

So it goes through. It's very powerful. All that hard-won intuition, all those formulas are going to go through. We'll quit for today. Next time, I am going to go through where things are a little bit different. I want to go through the shift theorem, and in particular, the stretch theorem. I love the higher-dimensional stretch theorem because it's new phenomenon that come up but actually have very important physical applications and physical implications. So we'll do that next time.

[End of Audio]

Duration: 51 minutes

Source: http://see.stanford.edu/materials/lsoftaee261/transcripts/TheFourierTransformAndItsApplications-Lecture27.html


Responses

0 Respones to "TheFourierTransformAndItsApplications-Lecture27"

 

Recent Comments

Home - About - Utility - Softs - Flash - Mobile - Camera - Laptop - Forum = Links

Popular Posts

Return to top of page Copyright © 2010 | Platinum Theme Converted into Blogger Template by HackTutors