Okay, so you might say this was a lot of effort on a very small sized DFT.
So let's see where this has a real impact in practice.
So in image processing, if you have a digital camera,
you take large images, 1,000 by 1,000 pixels or something like this.
And out of these large images, small blocks are derived.
Okay, so we take a large image.
Okay, let's say 1024 by 1024 pixels to make it simple.
And then you divide it into small blocks here.
And the small blocks are of size 8 by 8, okay?
On that 8 by 8 block we take a transform called the discrete cosine transform.
[INAUDIBLE] transform, discrete cosine transform.
And a DCT is essentially a real version of a DFT.
I don't want to get into the trigonometric mess of defining the DCT in detail.
We could do this in a supplementary lecture.
For now let's just assume it's a real version of the DFT.
And it has a fast algorithm that is very close to a DFT algorithm.
So it's a little bit more complicated, little details, phase shifts and so on.
But to a first view, it is like a real version of
a discrete Fourier transform, okay?
And if it takes a direct transform, well, 8 by 8 is 64.
So there is a matrix of size 64 by 64 that multiplies
a vector where we have the pixels from the 8 by 8 block.
So 64 squared is 4,000 and something, 4,096.
And for every block you have to take this transform.
Okay, and each multiplication has to be computed with fixed point multiplication.
It's expensive, takes time or hardware.
Okay, now there is a first trick,
that this transform is a so-called separable transform.
So you can take your eight by eight block,
okay let me try to make an approximation of an eight by eight block.
