the Fourier transform is one of the most
important algorithms in signal
processing and perhaps the most
important algorithm in time frequency
based analyses but the Fourier transform
is actually not this weird complex
sophisticated algorithm in fact the
Fourier transform is fairly
straightforward to understand and even
to implement now in fact there's really
only kind of 2.5 things that you need to
know in order to understand not only how
the Fourier transform works but how to
implement it yourself in MATLAB the
first thing you need to know is about
sine waves and this we covered in the
previous lecture the kind of
one-point-five a thing that you need to
know is about complex numbers and
complex sine waves but I think we can
kind of skip over this for now I think
you can still understand the Fourier
transform without really having a good
grasp of the importance of complex
numbers and we will get back to that
point later and the second thing that
you need to know to understand the
Fourier transform is the dot product and
that is the focus of this lecture the
dot product is important not only for
the Fourier transform but also is the
the basis of foundation for many other
algorithms and analysis techniques for
example convolution and convolution is
one of the main methods that we will use
for time frequency decomposition and
just a foreshadow a little bit where
this is going we will learn about this
more in the in the next lecture but the
the way that the Fourier transform works
re-write the discrete-time fourier
transform is basically by comparing your
signal your EEG data to sine waves of
different frequencies and the way that
we implement this comparison between
these two time series is via the dot
product so that's what we need the dot
product for in the Fourier transform so
just so you can see where this is going
so before I tell you about the the dot
product and how its computed and how to
think about it
we need to learn a little bit about
vectors so there are two different ways
of thinking about vectors or
conceptualizing vectors there's a more
algebraic interpretation and there's a
more geometric interpretation these are
both just differ slightly different ways
of thinking about the same thing and you
will learn that sometimes in some
situations it's more useful to think
about vectors in a more algebraic sense
and sometimes it's more useful to think
about them in a more geometric sense so
it's good to appreciate both
interpretations and in an algebraic
sense a vector is just a collection of
numbers it's just a bunch of numbers
that are kind of organized into an array
and so here we have a vector one to it
so this is just a collection of two
numbers or two elements so this is a
first element and the second element and
these are often referred to as
dimensions so this would be the first
dimension and the second dimension and
so this is a two dimensional vector but
it's really just a collection of numbers
just an ordered collection of numbers
okay so we can also think about a vector
in a more geometric sense and here we
can think about a vector as as an
address or a location a coordinate of a
point in a in some space and the number
of dimensions of that space correspond
to the number of dimensions or the
number of elements in the vector and so
here we have a nice Cartesian plane you
can imagine this is the x axis and the y
axis and now the vector 1 2 can also be
represented as a as a coordinate that's
defined by 1 over on this axis and 2 up
on this axis and we can take this even
one step further and think about this
coordinate as reflecting the endpoint of
a line that goes from the origin to that
point this is a little bit of a physics
interpretation as well that we have a a
vector with a particular magnitude and a
particular direction or an orientation
or an angle we will see when when we
learn about complex numbers and
extracting information power and phase
information out of the result of Fourier
transform and from complex wavelet
convolution that this interpretation is
is very useful this interpretation
becomes very powerful way to think about
time frequency based analyses
nonetheless these two interpretations of
a vector are really just two different
ways of thinking about the same thing
of course vectors are not limited to two
dimensions we can also have a three
dimensional vector for example and so
now here is three numbers and here is a
coordinate in a three dimensional space
so we can call these the x axis the y
axis and z axis but these are just
arbitrary labels but the point is that
this collection of numbers can also be
represented as a coordinate in a three
dimensional space and we can also think
about that coordinate as being the end
point of a line going from the origin to
that point so you can probably imagine
that vectors are not limited to one two
or three dimensions vectors can have any
number of dimensions although they have
to be integer dimensions but of course
after three dimensions it gets very
difficult to conceptualize and certainly
to draw what it would look like to be a
coordinate in a hundred and fifty
dimensional space nonetheless the the
concept still holds the concept is still
valid interpretation is still useful and
in fact later on an EEG data analysis
you will learn that it's sometimes
useful to think about EEG data in terms
of in terms of vectors either the sort
of algebraic interpretation or the
geometric interpretation for example if
you look at a topographical map the
activity at different electrodes at a
single time point or in a single
frequency band
if you have 64 electrodes it's so you
have data at 64 points you can think of
those 64 values as being in in a vector
so I have a 64 dimensional vector that
is a representation of the topographical
map of activity and you can also this
gets a little bit wacky but try to think
about this you can also try to imagine a
64 dimensional space where the O the
combination of all of the voltage values
at all the different electrodes is one
coordinate in that 64 dimensional space
okay I know it's a it's fun to think
about and but it actually is a useful
representation particularly when doing
more sophisticated or more advanced
analyses trying to compare the
relationships between different
topographical maps at different time
points or different frequency bands okay
so now we know something about vectors
and now we are ready to to learn about
the dot product the dot product is
really just a way of comparing two
vectors or trying to find a mapping
between two vectors so here we have two
vectors these are for element vectors or
for dimensional vectors and what we want
is to what the dot product is going to
give us is a single number that reflects
the relationship between these two
vectors okay so the dot products oh and
and similar to how we can think about
vectors either in an algebraic sense or
in a geometric sense we can also think
about the dot product in an algebraic
sense or in a geometric sense and in
different situations it will be more
useful to conceptualize the dot product
in an algebraic way and in other
situations it will be more useful to
conceptualize the dot product in a
geometric way so this is the the
algebraic interpretation of the dot
product in a way of thinking about the
that product so computing the dot
product is very straightforward it
involves just multiplying each element
in the two vectors point wise and then
summing them up so to compute the dot
product between these two vectors we
just multiply 1 times 1 plus 2 times 4
plus 4 times 3 plus 5 times 7 and that
simplifies to 56 so now this is one
single number that tells us something
about the relationship between these two
vectors needless to say in order for the
dot product to be defined between these
two vectors the two vectors have to have
the same number of elements so if this
one had a 10 over here then you could
not compute the dot product between
these two vectors because you would you
would have nothing in this vector to
multiply against the last number in this
in this vector okay so what is 56 mean
it can without knowing the units of this
without having other vectors to to
relate this value to it can be a little
bit difficult to interpret this number
on its own but this number can be very
useful when interpreted relative to the
dot product with other vectors and so
here we have two pairs of vectors these
are each 2 element vectors or two
dimensional vectors and you can see that
these two pairs of vectors are almost
exactly the same the only difference is
that this 4 has a negative sign in front
of it and this is a positive 4 and so
their dot products here work out to
minus 7 + 9 + + + 9 so you might be
wondering why this is and why are these
numbers similar in magnitude but totally
opposite in sign so what does that mean
and how do we interpret this difference
between the dot product where the first
vector is identical and the second
vector is very similar that it's just
flipped on
access that's just a negative sign here
okay so to understand this this is where
the geometric interpretation of the dot
product becomes useful so now of course
I chose these this example to contain
two-dimensional vectors on purpose so we
can represent these three distinct
vectors as as lines in a two dimensional
space and so here's the vector one two a
yellow and a vector and the red vector
and the blue vector and so now you can
see that the geometric difference
between these two pairs of vectors so
yellow to blue versus yellow to red is
something related to the angle so from
yellow to blue this is a very acute
angle they're very close to each other
so that gets a positive number and the
the yellow to the red vector they have
an obtuse angle so it's greater than 90
degrees there these vectors are pointing
very far apart from each other and now
the dot product is is negative and so
there is in fact a non-trivial
relationship between the sign of the dot
product and the angle of the angle
between the two vectors and that looks
something like this so when there is an
acute angle between the two vectors so
an angle less than 90 degrees the dot
product is going to be greater than 0
when the dot product is is exactly 90
degrees when there's a right angle
between the two vectors the dot product
is going to be exactly zero and when the
dot product are sorry when the angle
between the two vectors is greater than
90 degrees then the dot product is is
negative it's going to be less than zero
and so this also from this figure we can
also see the geometric interpretation of
the dot product and which you can think
about when the way to think about a dot
products in this geometric sense is that
you want to find the projection of one
vector onto the other vector
and the way you do this is by kind of
drawing a line from the end of one
vector down to the other vector such
that that line forms a right angle with
the with the second vector another way
that people have thought about this or I
explain this is if you imagine that that
you know this is this is the surface of
the earth and this is where in its
midday on the equator and so the Sun is
exactly up here and now the sun is
shining down and this vector could be a
wall or something and the shadow this
would be the shadow that's cast by the
Sun onto onto this surface so it comes
down exactly perpendicular such that the
projection here goes performs a right
angle with the second vector so and when
the angle between these two vectors is
less than 90 degrees then then the dot
product is positive its greater than
zero and now you can see that the when
the two vectors are have a 90 degree
angle between them the projection of the
first angle vectors onto the second
vector is exactly zero there is there is
no projection there is no nonzero
component of this vector that can be
projected onto this vector at least in
this perpendicular sense and this is why
the dot product is zero there is no
relationship between these two vectors
we can say that these two vectors are
orthogonal to each other I know when the
when the angle between the two vectors
is greater than 90 degrees in fact there
is no projection of this first vector
onto the second vector because it's sort
of bent backwards and so here what you
do is just imagine extending the second
vector out in into the opposite Dement
direction such that you actually can
define a a projection and this is why
that projection gets a negative sign
because we are going you know you can
think of it as as we're going backwards
or if we have to flip this vector
backwards in the negative
direction in order to define a
projection from the first vector down on
to the second vector so this gives us
the dot product less than zero or a
negative dot product so I hope that
gives you a geometric intuition for for
how to conceptualize dot products and
when the dot products are are negative
and positive and zero the geometric way
of computing dot products or defining
dot products is that it is the the
magnitudes of the two vectors so these
horse vertical bars indicate the the
magnitude of the length from zero to the
end point the length of that vector is
the magnitude times the cosine of the
angle between them I don't want to dwell
on this too much it is formally
equivalent to to do this algebraic
computation where we just sum all the
the element wise multiplication but just
to have it here for sort of more formal
reasons you can see that the when the
the angle between the two vectors is
ninety degrees and the cosine is going
to be zero and so then this whole
equation is zero and that's why you have
a zero dot product when the angle
between the two vectors is is ninety
degrees and again so just to reiterate
and foreshadow where this is going with
the dot product when we have these two
vectors when we are computing the
Fourier transform we have a eg signal
and we have the sine wave we can think
about these two time series as as two
vectors so the vector of EEG data the
vector of sine wave and we can think
about these as a collection of numbers
we can also think about these let's say
this is 640 time points we could also
think about these two vectors as two
lines in a 640 dimensional space and
what we want to do in the Fourier
transform is compute the mapping between
these
two vectors and so this is my
illustration of how just to remind you
that the sine wave is actually
discretized it's just a bunch of points
it is the same number of points as the
eg data of course because to compute the
dot product the number of elements and
the two vectors have to be the same and
then what happens in the Fourier
transform is that each each time point
or the data at each time point and the
eg data is multiplied by the value of
the sine wave at the corresponding time
point and then we sum up all of these
point wise multiplications and this is
how we get the frequency specific
information per frequency so that's just
to give you a bit of a taste of what's
to come and this idea the how this
algorithm works is something that will
be unpacked and developed in much more
detail in the next lecture