Fourier Stuff - Part 1

Are readers following the play here? Any questions? I'll make today's entry and then leave it for a week or so to (a) prepare for the next level of explanation and (b) give you a chance to ponder/absorb. :-)

Now I do hope that you are getting onto the idea that 'signal analysis' at E@H is trying to find some regular repeating signal in amongst alot of other stuff recorded at the receivers. So you could phrase it as either 'garbage elimination' or 'signal extraction' because of the mixture of signal with noise. If you knew precisely in advance exactly what the signal was then life would be a lot simpler ( in fact 'templates' are educated guesses at precisely that ). So to clean up an old Led Zeppelin studio track one has the big advantage of knowing what Led Zeppelin is supposed to sound like. Why? Because it's an artificial noise that we construct ( sorry to put it that way LZ ). So we need an efficient protocol to step through many, many natural ( non-man-made ) signal possibilities embedded within some track of data. Hence Fourier.

Sines and cosines. I sense trepidation and furrowing of brows. Relax. If you can cope with radian angle measure then you'll be OK for these guys. More ratios of two lengths, the idea being to represent the shorter sides of a triangle as a fraction of the longest side. Check out this diagram :

A circle is defined as that set of points being some fixed distance from a single designated 'center' point. I'm going to deal with a circle that has a non-zero radius ( r > 0.0, otherwise we're just talking of a single point ! ) then the ratios x/r and y/r are always going to be defined, as the denominator is never zero. Note that r is the length of the longest side, so both of those ratios will always be less than 1 in absolute size. Look at this triangle with a very small angle near the origin :

thus x is about the same as r, so x/r ~ 1.0 ( but slightly less because r > x ). While y/r is close to 0.0 . If THETA is zero then x/r = 1.0 and y/r = 0.0 exactly ( the triangle 'flattens' to two horizontal lines overlying each other and the x-axis ). Look at this triangle with nearly a right angle ( THETA that is ) closest to the origin :

This time x/r is about 0.0, and y/r is just less than 1. So if THETA is PI/2 ( = 90 degrees, remember ) then x/r = 0.0 and y/r = 1.0 exactly ( another 'flat' triangle of two vertical lines on the y-axis ). Try a triangle with THETA = PI/4 ( = 45 degrees, but I'm going to stop reminding you of these degree conversions soon ) and sorry about the white-out :

as x and y are equal here, x/r = y/r ~ 0.7071 ( = 1/SQRT[2] actually ). We can continue this assessment not just for angles b/w 0.0 to PI/2, but right around the circle. By convention we designate the positive x-axis as the zero direction for THETA, more positive THETA anti-clockwise and more negative THETA clockwise as discussed earlier. For any arbitrary THETA, outside of the 'first quadrant' you just look at the x and y co-ordinates to get the magnitude of sine and cosine :

However we remember to keep track of whether x and y are positive or negative. Thus as the cosine function is x/r the 'sign of the cosine' is whatever the sign of x is. Likewise as the sine function is y/r then the 'sign of the sine' is whatever the sign of y is. But r is always considered as positive as it's the distance from the origin [ with co-ordinates listed as (0,0), that is where the horizontal x-axis crosses over the vertical y-axis ]. The result is this :

and you will notice that I've been sneaking in the label 'cosine' or 'cos' to represent the ratio x/r, and the label 'sine' or 'sin' for the ratio y/r. They are 'pure' numbers without any units. Much like the PacMan diagram having a bigger circle, with the same given jaw angle then x, y and r all increase in proportion - by design really - so these ratios are constant.

Hence if you quote an angle, I can read back ( or calculate ) what the sine and cosine of the angle is. So that means sine and cosine are 'functions of the angle'. Clever punters will note that sine and cosine have the same common shape but sine is shifted ( PI/2 ) to the right with respect to the cosine. Indeed :

sin( THETA ) = cos( THETA - PI/2 )

which you could read as 'the sine of angle is whatever the cosine was 90 degrees ago' .... :-)

Shift either function by PI and you will get the negative of said function. However you can't make a sine from a cosine without the shift. Where sine is zero then cosine is ( minus ) one, and vice-versa. No amount of multiplying by a non-zero & non-infinite number will get you one from zero, or zero from one. For Fourier Stuff : however you express it, or hide it, mathematically you still effectively need both to cover all possible signal candidates. Well the good news is that we now having cyclic/rhythmic functions that neither fade away nor grow out of bounds - as far as the eye can see, because everything repeats when you go any multiple of 2 * PI ( complete laps around ) either side - to the left or right ! :-)

Often the angle is called the phase, and from the point of view of signal processing you could work with sines alone or cosines alone - remembering to shift appropriately, effectively masquerading one for the other by putting a +/- PI/2 as required inside the function brackets. Or you could use sines and cosines together, knowing that what one covers the other will catch. This would be perfectly fine. However there is a notation/number-system that helps to keep them together in the one 'package' very conveniently.

Which is the subject of the next installment : complex numbers.

[ they're not nearly as bad as the name suggests :-) ]

Cheers, Mike.

Complex numbers. It's an extension of the number types that you already know : counting or natural numbers = {1, 2, 3, 4, 5 ... } -> integers positive and negative {-3, -2, -1, 0, 1, 2, 3 } -> fractions {p/q where : p and q are integers, q non-zero } -> 'real' numbers. Think of real numbers as those expressible in decimal form, like 123.456, but that the digits on the right of the decimal point may go on forever.* There's an incredible history to this progression of number sets, each containing the previous set but adding some extra ones. Mainly to help solve newer problems.

What is the square root of minus one? That is, what number when multiplied by itself yields minus one ? None of the above sets contain that number, but for one reason or another we'd like to know. So we have invented a new single number which works for this problem : i

i ^2 = i * i = -1

i is like no other number you have met. It is not a combo of any before it, like p/q being built from p's and q's. Zero was like that when it was first invented. Engineers tend to call it j. All that matters is that it solves this equation :

x^2 + 1 = 0

What must 'x' be here ? => x is i . No more and no less.

But once you allow that, then great stuff happens. We crack open an entire class of problems. This is good, this is progress. :-)

Let's do the keep-multiplying-by-itself trick again, this time using i :

i , -1, -i , 1, i , -1, -i , 1, i , -1, -i , 1 ...

[ NB. -i * i = (-1) * i * i = (-1) * (i^2) = (-1) * (-1) = 1 ]

I'll return to this 'cycle' later, with a much better answer than 'stuffed if I know' too. As it's quite pivotal, please try to understand why it happens that way. Also I have snuck in a few other 'obvious' behaviours like :

1 * i = i

(- 1) * i = -i

or generally if x is any real number :

x * i = xi = ix

which gives me the answer to : what is the square root of minus 16? Answer :

4i * 4i = 4 * 4 * i * i = 16 * (i ^2) = -16

so 4i is the go for that one. Now some of you are probably thinking : this is a bit lame, you're just playing with symbols, Mike's slipped a cog or five, where does this lead us? ....etc. You'd not be alone there, in fact when first presented i was called ( fanfare ) The Pure Imaginary Number. Of itself, or plain multiples thereof, it doesn't really fly very far at all.

Hence the set of complex numbers. Now this is the real deal, and even includes all of the above number types as subset(s). But a complex number is not a single number. Each specific complex number is a pair of numbers, if you change any one of the pair then you have a new complex number. An ordered pair in fact.

x + y*i

here both x and y are real numbers. The 'x' by itself is the real part of the complex number, and the y ( the y by itself not the entire product with i ) is called the imaginary part. [ So, annoyingly, the imaginary part is actually a real number ... ie. the multiplier of the only imaginary number - which is i. It's not terribly important, but may depend upon the terminology of whom-so-ever teaches you .... ]

Now here arises a potentially very deceptive problem with the above notation. When I first learnt about complex numbers, it took me a good month or so to work this out on my own ( and wow, was I annoyed that it had not been pointed out to me ! ) The + symbol used here DOES NOT MEAN AN OPERATION OF ADDITION. In fact the + does not mean any operation in the sense that you are used to. It means, nor more or less, 'link the real part on the left with the imaginary part on the right' or 'I now marry this real guy to this imaginary girl'.

So if I have two bananas plus three apples what have I got? The best you can sensibly say is 'five fruit', but we won't do that. We'll simply accept that it is an irreducible phrase. So 'two bananas plus three apples' is just 'two bananas plus three apples'. I don't talk of either 'five banapples' or 'five appananas'. Again, it's an ordered pairing.

Now you could write a complex number this way :

y*i + x

Some do. It's not a hanging offense, as it is still clear which are the real and imaginary parts. Hint : the one with the i is the imaginary part.

The set of real numbers is the subset of complex ones by setting y to zero, the set of (pure) imaginary numbers likewise by setting x to zero. You can annotate and work with complex numbers entirely in a more formal ordered tuple format :

(x, y)

but it has to be clear from context that it is a complex number being represented, and who is who ( real first, imaginary second ). My personal preference is to use 'x + yi ' with the above important understandings of the meaning of the symbols. I suppose because I was taught that way. As we will be using i alot from now on, I'll try to always use magenta/boldface so we don't get confused and avoid maybe problems with font rendering with different browsers et al. To spot the difference b/w the '+' used as a 'linker' of complex number sub-parts versus ordinary/prior use, then you need to look either side and deduce from there. I won't be BBCoding that. Is it simply two real numbers on right and left, or do I have a real on one side and an imaginary on the other? As I mentioned before, alot of trouble one can have with maths is surmounting the notations.

Next time : are there operations to combine complex numbers together, and can you graph them? Don't you just love rhetorical questions? :-) :-) :-)

Cheers, Mike.

( edit ) * Well, they can do that on the left side too. However if you use decimals as a definition/representation then one has to be a tad careful and do things like : agree that 1.0 and 0.9999.... ( the 9's repeat infinitely ) are the same number ( one ). Side note : I say decimal, but generally what is/is-not a recurrent/repeating pattern in the representation does depend on the number base used. So 'one-third' in base ten is 0.333333..... ( recurring ) but 0.1 ( non recurring ) in base-3/ternary ! I mention this especially as one ought to distinguish the concept of a given number - 'one-third-ness' or 'divide-into-three-equal-parts-please' - from how you write it down. :-)

Operations on complex numbers. Look at these complex numbers :

z_1 = x_1 + iy_1

z_2 = x_2 + iy_2

Typically the letter 'z' is used in complex algebra. So 'z_1' means 'this symbol represents a complex number with the real and imaginary parts as per the right side of the equals'. Addition and subtraction are easy, just add/subtract the corresponding real and imaginary parts :

z_3 = z_1 + z_2 = (x_1 + x_2) + i(y_1 + y_2)

z_4 = z_1 - z_2 = (x_1 - x_2) + i(y_1 - y_2)

where I'll ( laboriously ) repeat the warning about the meaning of the operator symbols : reliance upon context to properly understand. The + here means 'add two complex numbers together' :

z_1 + z_2

The + here means 'add two real numbers together' :

x_1 + x_2

y_1 + y_2

The + here means 'link the real part on the left with the imaginary part on the right' :

(x_1 + x_2) + i(y_1 + y_2)

and thus for the '-' symbol. Which I can also use in the linking sense :

x_1 - iy_1 = x_1 + i(-y_1)

Multiplication and division are defined for complex numbers ie. z_1 * z_2 and z_1/z_2 but with the x + iy notation the results (a) look horrible (b) require a side track/loop of explanation and (c) we won't need for our purposes anyway. I will define these operations for you but only after we have a look at an equivalent notation for representing complex numbers. But for that we need to look at graphing complex numbers ( not functions of complex numbers, but the numbers themselves ).

here I've shown what looks to be the standard two-dimensional real Cartesian plane. It isn't. The vertical axis is imaginary numbers. A point in this Argand plane is a single complex number with a real horizontal co-ordinate and an imaginary vertical co-ordinate. You still get Pythagorus and sine/cosine though. Now the point P, representing a complex number z, can be indicated in two equivalent ways:

z = x + iy

OR

z = r * exp[i * THETA]

Whoa! What's this? Some chaps came up with the following identity, meaning 'we define the following to be so'* :

exp[i * THETA] = cos(THETA) + i * sin(THETA)

where exp[something] is 'e', the natural logarithm base ( about 2.718281828 ... ), raised to the power of 'something'. And because it is a 'sum', in the linking sense, of a real number and an imaginary one then 'exp[i * THETA]' is a complex number. Now there's a deep rabbit hole on this one, which I will avoid explaining. It's a rabbit warren in fact. For this thread of explanation please take it on trust that several things apply, such as the following ( non-exhaustive ) list:

exp[0] = 1

exp[-p] = 1 / exp[p]

exp[p] * exp[q] = exp[p+q]

exp[p] / exp[q] = exp[p-q]

this is true regardless of whether p and q are real, imaginary or complex ( remembering to think carefully about what the '+' operator means in specific cases ). It's a way of saying what I said earlier about the x^[5] power function ie. you can break down a product into additive factors or exponents**.

d/dx(exp[x]) = exp[x]

this means the derivative of the exponential function is the function itself. Indeed it is the only function for which this is true. Actually you can use this quality to derive all others about exp[x], say :

d/dx(exp[kx]) = k* exp[kx]

[ k being a constant with respect to the variable we are differentiating against -> x ]

As integration is the 'reverse' of differentiation then 'the integral of the natural exponential is the natural exponential' as well ( ignoring limits of integration, some constants .. ). Looking back at the graph you will see that :

Re(z) = r * cos(THETA)

Im(z) = r * sin(THETA)

where the notation 'Re(something)' means the 'real part of something', and 'Im(something)' means the 'imaginary part of something'. Now you could have guessed that from the graph as I am really re-stating what it means to be a sine or cosine function :

cos(THETA) = x/r

sin(THETA) = y/r

PLUS Pythagorus :

r^2 = x^2 + y^2

but in the context of the vertical axis measuring 'imaginary' lengths. So let

z_1 = r_1 * exp[i * THETA_1]

z_2 = r_2 * exp[i * THETA_2]

then :

z_1 * z_2 = r_1 * r_2 * exp[i * (THETA_1 + THETA_2)]

z_1 / z_2 = (r_1 / r_2) * exp[i * (THETA_1 - THETA_2)]

Generically r is called the magnitude of the complex number and THETA the phase. Multiplying two complex numbers means multiplying the magnitudes while adding phases. Dividing complex numbers means dividing one magnitude by the other, and subtracting phases. Note that I still need two real numbers to specify a single complex number, for either 'x + iy' or 'r * exp[i * THETA]', and I can swap from one to the other using trigonometry.

Next time : expressing rhythms using (co-)sinusoids, and a first look at Fourier

Cheers, Mike.

*Well, you could start with that and derive other stuff, or begin with the other stuff and come back to this. It's all consistent ... :-)

** Indeed the logarithm function is the answer to the question 'what is the exponent that I am using to represent a certain number as a power of a given base?' So

p = base_b^[q]

and

q = logarithm_to_base_b(p)

are really the same thing. It's a question of emphasis - which variable do you isolate on the left side with everything else on the right. Thus 'eight is two cubed' is an intellectually identical statement as 'three is the logarithm of eight to the base two'. Though to do that unambiguously you need a couple of pre-conditions ( or restrictive definitions ) on the functions - one-to-one and onto. You get inverse functions that way, returning you to the same number via jumping from domain to range and then back again - along the same 'link of assocation' ( one link of the totality that define the function ) between a given pair of numbers, each within the respective domain/range set. It's a reverse gear ....

I could spend a decade on the topic of limits. This posting has a plethora of useful asides that I'll only be indicating the 'stubs' of, and there is imprecision in the natural language description that mathematic symbology avoids. So I'm leaving out slabs of important but arcane criteria.

Now, I'm thinking of the following numbers :

1, 1/2, 1/3, 1/4, 1/5, 1/6 .....

the general term in this sequence is

1/n for n = 1, 2, 3, 4, 5, 6 ........

generally a sequence is a set that I have ordered, not necessarily by magnitude or any other arithmetic criteria ( it just happens to be decreasing in this example ), but by associating each element with one of the natural numbers. It doesn't even have to have a formula to prescribe each term. But there is a first element, a second element, a third element etc. I could put this in functional notation :

f(n) = 1/n

where n E N

'E' meaning 'element of' and 'N' is the set of natural numbers. The domain of 'f' is thus the natural numbers and we'll take the range to be the real numbers ( although I could give a narrower specification ). Now can you give me a ( real ) number which is definitely less than every one of those in that sequence? Sure you can. Say -1 or -3 or -0.5 or 0.0 to name but a few. Each of these chosen numbers is called a lower bound of the sequence, and I could form another set, which I'll call L, being the set of all lower bounds of the given sequence. So for L :

(a) each element within is less than each and every f(n), and

(b) I haven't missed any real numbers that could satisfy (a)

Does L have a greatest member ie. one that is more positive ( or less negative ) than all the other elements of L? Yep. A little thought shows this has to be 0.0, this now gets called the greatest lower bound or infimum. Furthermore, in this instance, 0.0 is stated as 'the limit of the sequence as n goes to infinity'.

We could flip/invert the sense of the problem by using this sequence :

g(n) = 1 - 1/n

or

0, 1/2, 2/3, 3/4, 4/5, 5/6 .....

Now here we have an increasing sequence of numbers, which has a set of upper bounds I'll call U

(a) each element within is greater than each and every g(n), and

(b) I haven't missed any real numbers that could satisfy (a)

with the least member of U being called the least upper bound or supremum. In fact it is only when we use real numbers, and not the rationals ( fractions made up from integers ), that we can always have either an infimum or supremum ( depending upon the sense of the bounds ) for any given bounded set*. We can say 'every set of real numbers bounded below has an infimum' and/or 'every set of real numbers bounded above has a supremum'. Now it is possible for some sets that the infimum and/or supremum is a member of the set ( take all the real numbers less than or equal to 2 ). The key point is that there is a number somewhere on the real line that has the infimum/supremum property for a given bounded set. If a set is bounded above and below then it will have both an infimum and a supremum, either/both/none of which may lie in the set itself.

We generally think of limits in the sense of some sequence of numbers that gets closer and closer to some fixed number like in the above examples, i.e the limit of the sequence, but without ever reaching it in the manner that some n E N ( finite ) could be quoted for which the sequence value equals the limit.

You could, say, have the sequence {3, 3, 3, 3, 3, 3, 3 ....} where the limit is obviously 3. There are also sequences that oscillate up and down but progressively less so as n increases, the limit ( if any ) then being the value that the terms progressively 'cuddle up' to. Fourier series can be like that due to the intrinsic oscillation character of the base sine/cosine functions. The f(n) and g(n) cases above are specific examples of a general theorem that a monotonically increasing/decreasing sequence with an upper/lower bound must approach a limit. A sequence may diverge - or not converge - because of oscillation alone and not because the terms are unbounded. Like {1, -1, 1, -1, 1, -1, 1 ... } where there is no single number one that all terms can be arbitrarily close to ( 1 and -1 are accumulation points because there are sub-sequences that converge to them ).

So as above, 0.0 is the limit for f(n) and 1.0 is the limit for g(n). You could probably think of some real life examples of this sort of thing, say the speed of light for a body with mass in a particle accelerator, or an aeroplane ( normally powered ) attempting to reach some maximum altitude, a vacuum pump evacuating a chamber and so on. Actually the ebb/flow of luck at the casino table has an oscillating character that tends to a limit in the long run -> you lose that is. If you want to make money from a casino then be either an investor in one or a government that taxes one ..... :-) :-)

In Fourier work we'll be looking at numbers like that - but where each number in the sequence is a sum of other numbers ( careful, this is where confusion sneaks in ). The sum itself has a number of terms as discussed ( which may even form a sequence themselves ..... ) and we will want to know what is the tendency of these sums as we add more terms into the sums. If you like think of a series as like the progressive total at the supermarket check-out, as you add in extra items through the beeping scanner into the total, it updates to reflect the current number of items. Here however we can have an effectively bottomless/infinite trolley to draw from! Try

S(N) = SUM[1,N](1/n) = 1/1 + 1/2 + 1/3 + 1/4 + ..... + 1/n + 1/(n+1) + .... + 1/N

I explain the notation here : S(N) means 'the sum to N terms', SUM[1,N] means 'start at 1 and go as far as N', (1/n) is the pattern of each term within the sum, and the far RHS shows this expanded. You could bung this in a code loop :

// Sum to N terms
sum = 0;
for(n = 1 ; n N terms will lie closer to the limit than your choice of EPS. Because your choice of EPS can be anything non-negative/non-zero, then it's a way of saying that a sum to any n > N terms can always be made arbitrarily close to the supposed limit simply my evaluating enough terms and summing them. As the tolerance level - 'how close am I to the limit?' - gets smaller then one has to go 'further along' in summing the series to make sure you lie closer to the limit than said tolerance level. Whew!! It works and is precise and unambiguous although an utter pain to perform on each and every occasion that might be applicable. What has happened is that some general theorems/results have been proved with the EPS method and you simply note that if a certain such theorem can be applied for a given scenario then you can confidently use the theorem's conclusions without the agony of winding/travelling along a detailed EPS assessment pathway**. Which is great! :-) ]

Next up in this whirlwind tour : a chat about what it really means to integrate a function OR how to sum a series using the real numbers as indices instead of the natural numbers OR why you hate calculus! :-) :-)

Cheers, Mike.

* This doesn't work for the rationals. Take all possible rational numbers which have the property that the result when each is squared is less than 2. There is no rational number which is the least upper bound of this set. That is : the square root of two is not rational - it is irrational, and the union of the rationals plus the irrationals gives the real numbers. The set of real numbers having the supremum/infimum property is their defining quality, without which we'd still be at Middle Ages Math. A chap by the name of Dedekind used an idea now called 'Dedekind cuts' to construct the real numbers from what is effectively the supremum/infimum property. I've got a great book by another famous mathematical chap called G.H. Hardy which outlines this approach.

** See! I can't help myself with pointing out the by-ways of this topic. There are other equivalent criteria for convergence like the one used by Cauchy : if the difference between terms in a sequence has a certain pattern as n -> infinity, then a sequence will converge. Or if one examines a thing called the limes superior - the limit of successive suprema of certain sub-sequences roughly meaning 'an eventual upper bound' - plus the limes inferior ( defined mutatis mutandis ) then convergence is guaranteed if the limes superior equals the limes inferior ( thus both equal to the sequence limit ). Another way of thinking about limits with an EPS tolerance is ( with A being the limit ) the set/interval (A - EPS, A + EPS) has an infinite number of members of the sequence within it, for any non-zero & positive EPSILON. Or : no matter how close you go to A with an EPS choice, you will always have a finite number of terms of the sequence outside of (A - EPS, A + EPS). The main reason for such alternate constructs is that it may be easier ( or well nigh impossible otherwise ) to show them as valid for certain examples.