Okay, good morning. Can we start? You're ready? Okay. Before we consider algorithms for defect

interpolation as we have motivated it last Monday, we will summarize a few basic properties

of the Fourier transform that you should be aware of and that you should have heard in

the context of other lectures like systems and signals or lectures like that or basic

mathematics lectures.

So the Fourier transform is defined as a basis transform in terms of linear algebra.

You take here the Nth roots, unit roots and you build up a new function by a linear combination

of unit roots using your original signal.

For those of you who still have no good feeling what it is actually doing, always replace

the e to the power of minus i by the cosine and sine functions and write it down and then

you mentally build up the correlation with the Fourier series that all signals, periodic

signals can be represented by a linear combination of sine and cosine functions and the Fourier

transform is nothing else but representing the signal in terms of its frequencies. And

that's also why we call the original signal to sit within the spatial domain. If we talk

about images, if we talk about speech signals, time signals, we talk about the time domain.

So that's the spatial domain in image processing and this here is the frequency domain where

we transform the signal using the Fourier transform. For the Fourier transform, you

have to know the complexity of the Fourier transform is quadratic. It's a linear mapping.

It's nothing else but a matrix vector multiplication. If you look at this, this is the inner product

of the unit roots multiplied here in the 1D case with the 1D signal f0, f1 up to fn-1.

That's just an inner product written in terms of a sum. Then you can do this for all the

x's and you get a matrix vector multiplication. This is known to have the basic complexity

of n square. We can reduce the complexity by using the fast Fourier transform. Also,

this is something you should be aware of. We bring the complexity down to n log n using

the idea of the fast Fourier transform with a butterfly operation that you might have heard

in other lectures. These things are not that much important for

us in this context. If you do not remember this exactly, this is not a disaster. If you

implement the algorithms, it's always better to use state of the art techniques and efficient

techniques. If you know about MATLAB and we are using MATLAB within the exercises, you

are not required to know that much about the Fourier transform because there is a library

function that does it all for you. Now let's talk about a few basic properties.

We use the Fourier series idea to show that the discrete sampling of a continuous function

should be done in a way that the sampling frequency is greater than twice the maximum

frequencies that shows up in the signal. What do you have to keep in mind if you have a

function? Let's say x1, x2 and for instance you have a function like this. We know that

this periodic function can be rewritten by a superposition of cosine

sine functions and we know that these coefficients here, they define the signal and if this sum

here is finite, if this sum here is not infinite but finite, we can represent the whole continuous

signal by using just the a case and b case that we have to know. If the sum is infinite

like in this case where we have this discontinuity, then all the higher frequencies show up in

the signal. If we want to sample a function, let's say a discrete function and we want

to sample it, that means we just take the function values at discrete positions on the

x1 axis, then the answer is we need a sampling frequencies that is twice as much as the maximum

frequency that shows up within the signal. So if a signal is band limited or frequency

limited, that means for a certain frequency all the a case and b case are zero or if we

transform is zero for sigma larger than b, then we know that we can compute out of this

boundary frequency here the frequency of our sampling. That's very fast repetition of what

you should learn within other lectures. So if a function is band limited, no infinitely

high frequencies within the signal, we know how to sample the signal and this will play

an important role later on for defect interpolation as we will see in a few minutes. Hello.