7
$\begingroup$

I am reading the book Fundamentals of Music Processing by M.Muller and I am close to understanding the idea behind the decomposition of a signal into basic frequencies, and would appreciate some help bridging a big gap in my understanding.

Fourier transformation of a continuous function $f(t)$ for some frequency $ω$ is defined in terms of a sinusoid of this frequency that "best matches" the signal. Crucially this involves picking the best phase shift $φ_ω$ that brings the sinusoid as close as possible to the signal $f(t)$, as the figure below indicates (case b is much better than a) effect of phase shift on closeness of fit

Mathematically the book quantifies the similarity of the signal and the sinusoid taking the integral of their inner product, which includes the phase angle as an optimization parameter as such

$$d_ω := \max_{φ \in [0,1)} \int_t f(t) \cos(2\pi(ωt-φ))dt \tag 1$$

Everything up to this point is clear, but when he proceeds to give the definition of the Fourier transform, we somehow lose the optimization after we switch to complex numbers, polar coordinates and the Euler formula, and the equivalent equation that defines the transformation for some $ω$ becomes

$$\hat{f}(ω) = \int_t f(t) e^{-2\pi iωt}dt \tag 2$$

So exactly how did we lose the optimization, and how the complex number calculated by this integral ensures that the best phase shift $φ$ is selected?

I am a computer programmer with some mathematical inclination, so I would appreciate a qualitative explanation if possible. I am not interested in exact proofs

$\endgroup$
9
  • 2
    $\begingroup$ I'm a little confused by the term $2 \pi \omega$. Usually, we write frequency in either Hertz ($f$) or radians per second ($\omega$) with the conversion: $\omega = 2\pi f$. Does the book relate $d_\omega$ to $\hat{f}(\omega)$ at all? I suspect it's something like $d_\omega = | \hat{f}(\omega)|$. $\endgroup$
    – Peter K.
    Oct 31 '21 at 17:53
  • 1
    $\begingroup$ sorry this book uses $ω$ symbol for frequency, rather confusingly $\endgroup$
    – nikos
    Oct 31 '21 at 18:01
  • 1
    $\begingroup$ Maybe helpful: dsp.stackexchange.com/questions/76549/… $\endgroup$
    – S.H.W
    Nov 1 '21 at 0:45
  • 1
    $\begingroup$ @Nayuki, this part of the video shows how using sine and cosine TOGETHER transforms the problem of the angle selection into one of amplitude selection to have a good match: youtu.be/hgTEL7BfA90?t=414 -- however it still begs the question how Fourier transform "optimizes" the amplitude coefficients? $\endgroup$
    – nikos
    Nov 1 '21 at 7:48
  • 3
    $\begingroup$ Describing the phase as an "optimization parameter" is entirely unnecessary and in my opinion needless complicated. The phase can easily be calculated directly without any optimization at all $\endgroup$
    – Hilmar
    Nov 1 '21 at 7:53
13
$\begingroup$

Bottom Line of the Qualitative Explanation: The Fourier Transform is a correlation of our arbitrary signal $x(t)$ with all frequencies, with each frequency given as a complex exponential: $e^{j\omega t}$ (this is a rotating phasor of magnitude $1$ and angle $\omega t$). This holds for $x(t)$ as being real as in the OP's case or complex. The general form for a correlation computation (that we see in so many places in signal processing: matched filter receiver, Viterbi decoding, and yes the Fourier Transform!) is the integration of a complex conjugate product (or sum of products in discrete signals), and such a computation will beautifully have minimum noise in the presence of white stationary noise. This is explained in more detail below with my hope of providing a more intuitive understanding. Such a correlation will maximize the estimate of frequency and phase for each $\omega$ in the presence of white noise (but may not necessarily provide an optimum estimate in the presence of other noise types).

Details: I actually find the Fourier Transform described with sines and cosines much more cumbersome and the expression with the exponentials quite intuitive once the mystery of the form $e^{j\omega t}$ is resolved.

Here are a few main take-aways:

First and foremost, it may not be apparent that the expression $Ke^{j\phi}$ is just a complex phasor with real magnitude $K$ and real angle $\phi$. So $Ke^{j\phi} = K\angle\phi$.

Next, and also important, consider a single Fourier frequency tone as a single rotating phasor, not a sinusoid, rotating at a constant rate with a constant magnitude. This will actually make everything a lot easier in my opinion. Similar to a bicycle wheel rotating where the frequency is it's rate of rotation in cycles per second; we will also get signed frequency to denote the direction of rotation: If the phasor is rotating counter-clockwise; this is a positive frequency. If the phasor is rotating clockwise, this is a negative frequency. This is consistent with the definition of instantaneous frequency as the time derivative of phase: a change in phase versus a change in time.

Below is a plot demonstrating this where we see a phasor rotating counter-clockwise on a complex plane ("I" is the in-phase or real axis and "Q" is the quadrature or imaginary axis).

positive frequency

Now Euler's relationship between $\cos(\omega t)$, $\sin(\omega t)$ and $e^{j \omega t}$ should make a little more sense; for example we can now see how:

$$2\cos(\omega t) = e^{j\omega t} + e^{-j \omega t}$$

These are just two phasors rotating with equal rates and opposite phase (a positive and negative frequency) that are added together. When you add two phasors, the angles cancel, or graphically place on phasor on the end of the other as shown in green below. In either case the result is the cosine which is always real (oscillates back and forth along the real axis).

euler

The general formula for a correlation measure of two functions is the integration of the complex conjugate product:

$$corr = \int f_1(t)f_2^*(t)dt$$

Conjugation means invert the phase and is denoted by "*" as in $x^*(t)$ is the conjugate of $x(t)$)For example, the two phasors as shown above for the cosine are in a conjugate relationship. One phasor is the conjugate of the other.

The correlation operation shown above has the wonderful property that "like" signals will grow in the integration to relatively large quantities while noise will reduce significantly through averaging. To see how "like" signals grow: consider a signal that is rotating in phase (a constant frequency); if we multiply it by its complex conjugate we will de-rotate it back to the positive real axis, and thus keep growing along the real axis in the integration (since $e^{j\omega t}e^{-j \omega t} =1$. As another example consider a sequence: 1 -1 1 1 -1, if we multiply it with itself, all samples will become 1, and the sum (integration) will grow to 5. Similarly if each sample was complex and also had a phase angle, if we multiplied it by it's complex conjugate, we would get the same result of each product being 1 and the sum growing to 5. Any other sequences with the same magnitude on each sample but other arbitrary angles will not grow as large.

We do the same with the Fourier Transform:

$$F(\omega) = \int x(t)e^{-j \omega t}dt$$

For each single frequency $\omega$, resulting in a spinning phasor given by $e^{j \omega t}$, we multiply our arbitrary waveform x(t) by the complex conjugate $e^{-j \omega t}$, and integrate: we are correlating our waveform to each each single frequency given by $e^{j\omega t}$ and through that determining it's magnitude and phase within $x(t)$! As we repeat that sweeping through each $\omega$ of interest, we get the complete spectrum of all frequencies. This is the Fourier Transform.


The OP then went on to ask, and again in the comments why choosing the same $\omega$ will maximize the result for the given phase angle versus any other $\omega$. Consider the full relationship given by Euler as detailed in the plot below as a continuation to my attempts to make $e^{j\omega t}$ more intuitive:

Complex signals

So when we correlate to $e^{j \omega t}$, we are correlating to both the real and imaginary terms (cosine and sine), resulting in a complex result, whose angle will be the angle of that tone in $x(t)$!

$$F(\omega) = \int x(t)e^{-j \omega t}dt$$ $$= \int (x_i(t)+jx_q(t))(\cos (\omega t) + j\sin(\omega t)dt $$

If we multiply out the real and imaginary terms, we see how when a real tone is shifted by any phase angle ($cos(\omega_o t + \phi)$, correlating it with $e^{j\omega t}$ will have a maximum magnitude when $\omega = \omega_o$ for any $\phi$, and that the resulting complex output of the correlation (the real and imaginary terms above) will be at that same angle!

For the case of the OP's question where $x(t)$ is real the above reduces to:

$$F(\omega) = \int (\cos(\omega t - \phi))(\cos (\omega t) + j\sin(\omega t)dt $$

$$ = \int \cos(\omega t - \phi)\cos (\omega t) dt + j \int \cos(\omega t - \phi)\sin (\omega t) dt$$

I prefer to not resort to the sine and cosine representation even in my own head to make sense of what is going on, but to just consider $e^{j\omega_o t}$ on its own as a single spinning phasor. If our signal $x(t)$ was also just a single spinning phasor also at $e^{j\omega_o t}$, then when we do the complex conjugate product: $x(t)e^{-j\omega_o t} = e^{j\omega_o t}e^{-j\omega_o t} = e^{j0} = 1$!! I show this graphically in the link at the bottom, but with no added phase to $x(t)$ we rotated to the real axis $(1)$ at all samples, which we integrate over time period $T$ leading to the maximum result of $T$ with no imaginary term, so it is $T\angle 0$. If we then add a phase rotation to $x(t)$ to get $e^{j\omega_o t + \phi}$ The product becomes $x(t)e^{-j\omega_o t} = e^{j\omega_o t + \phi}e^{-j\omega_o t} = e^{j\phi} = 1\angle \phi$. This would also grow to the same magnitude $T$ but with the angle $\phi$ Thus our output is complex with real and imaginary terms, that we could also get to the long way (in our head) with sines and cosines. You can carry this same thing out to real signals ($x(t)= cos(\omega t+\phi)$ by doing what I did above with both positive and negative frequency tones ($e^{j\omega_o t + \phi}$ amd $e^{-(j\omega_o t + \phi)}$). I show this all graphically and intuitively in the link given below.

To then see further details in how the correlation process itself will maximize the SNR of the $e^{j\omega t}$ signal (this is true under the condition of white noise), please see my response in this post, which includes showing how the correlation falls off as we deviate slightly from $\omega_o$:

Derivation of the Optimal Matched Filter - Convolution vs. Correlation

$\endgroup$
5
  • 1
    $\begingroup$ Thank you for the detailed exposition. However I don't see how it accounts for the real phase difference shown in the figure included in the question. Where did the angle optimization go? Perhaps the Fourier transform is just defined with the exponential and doesn't really take the angle into account (in the sense it doesn't pick the BEST $φ$). How can you prove to me that the slightly different exponential $e^{-2jωt}$ (or any other variation of the exponent), will not give a BIGGER value for the integral for a fixed $ω$? $\endgroup$
    – nikos
    Nov 1 '21 at 7:18
  • $\begingroup$ @nikos- I'll add that to the bottom of my answer. So if you are asking specifically why choosing the same value for \omega results in maximizing the SNR of the result, I have some good plots that I hope clarify that. $\endgroup$ Nov 1 '21 at 13:05
  • $\begingroup$ The plots I mention are all in that other post-- I hope this kept it simple enough but if still not clear after you read that let me know! $\endgroup$ Nov 1 '21 at 13:20
  • $\begingroup$ Is this one of those contexts where it's customary to define $j \equiv \sqrt{-1} ~ ,$ rather than $i \equiv \sqrt{-1} ~ ?$ $\endgroup$
    – Nat
    Nov 1 '21 at 20:33
  • 1
    $\begingroup$ @Nat yes sorry that is because I am an electrical engineer and not a mathematician (we use i for current) $\endgroup$ Nov 1 '21 at 20:48
6
$\begingroup$

Because the best $\phi$ from your (1) can be found by solving $$\begin{aligned} f_i(\omega) = \int_t f(t) \cos(2\pi(\omega t))dt \\ f_q(\omega) = \int_t f(t) \sin(2\pi(\omega t))dt \end{aligned} \tag a$$

then recognizing that the optimal $\phi$ for your (1) is

$$\phi(\omega) = \tan^{-1}\frac{f_q}{f_i} \tag b$$

This leads directly to your (2) -- in fact, for baseband signals the use of the $e^{2\pi i \omega t}$ term ends up being more or less a shorthand for (a) (but it has deeper meaning if you're willing to embrace more than quick, qualitative answers).

I am not going to justify this mathematically, because you asked me not to. If you find this distressingly vague, then I suggest that you find a book that gives a formal treatment of the derivation of the Fourier transform, and struggle through it. A college signal processing text aimed at 2nd-year engineering students should give you a good balance between approachability and mathematical rigor. So should a good introductory book on differential equations (with somewhat more rigor, somewhat less practical application, and usually with groundwork laid for an even more rigorous treatment in 4th-year or grad school).

$\endgroup$
2
  • $\begingroup$ I suppose I am asking for the impossible :) Think of a simple optimization of a function of one variable $f(φ)$, it involves at least trying to find the effect of $φ$ in conjunction with numerical algorithms. How come going to complex coordinates is saving us of this effort? Otherwise operations research would be all done in the complex plane!? $\endgroup$
    – nikos
    Oct 31 '21 at 18:01
  • 2
    $\begingroup$ When you calculate your $\hat f (\omega)$ using (2), that's the same calculation as my (a) -- it's just that the sine part and the cosine part are both embedded into the result, as the imaginary and real parts, respectively. $\endgroup$
    – TimWescott
    Oct 31 '21 at 18:31
3
$\begingroup$

If you want to learn more, you must start with Fourier series. They are an essential prerequisite, and mathematically and conceptually much simpler than Fourier transforms. At least you can learn the basics of Fourier series, and some of the main technical background, in one year instead of multiple years!

Understanding Fourier transforms properly requires advanced undergraduate level specialised pure mathematics as a minimum, or up to Ph.D. level depending on how deep you really want to go.

(Some essential prerequisites would be classical mathematical analysis; Lebesgue integration and measure theory; Hilbert spaces; functional analysis. Indeed, rigorous Fourier analysis is one of the most important applications, and historical motivations, of these topics. Even for very talented students, this takes multiple years of full time study to master). Thus the below is subject to technical caveats, complications and deliberate oversimplifications. It is not even possible to define the Fourier transform properly in enough generality without the above background.

The Fourier transform is NOT about optimisation at all, in the sense you mean. We are NOT looking for the single phase which best approximates the signal. Such a statement would be wrong and misleading (although, I don't know what your book actually says, it may be that you are unintentionally rephrasing the book and changing the meaning way beyond what was intended. I would imagine it was intended to be a helpful illustration only).

The Fourier transform is about "decomposing" a signal $f(t)$ "exactly" into a combination of pure signals $e^{i \omega t}$, for "every" real number $\omega$.

(Note very carefully the quotation marks above, which denote some of the unavoidable oversimplifications! Some very hard theory is lurking behind there...)

The value $\hat{f}(\omega)$ (in general a complex number; it is much better to get used to complex exponentials ASAP, as sine and cosine are extremely cumbersome algebraically) tells you the exact amount of $e^{i \omega t}$ which is present in the signal $f(t)$. They must all be combined together linearly to give $f$.

The value $\hat{f}(\omega)$ is unrelated to any kind of optimisation in the sense you mean, and it exists for ALL real values $\omega$ (it may be zero for some values of course, but often is nonzero but decaying for many values).

(Well, OK, if you know about Hilbert spaces, orthogonal projections and least squares estimation, you will see that a kind of optimisation is happening there, but it would take us too far afield).

$\endgroup$
1
  • $\begingroup$ did I say I am a programmer seeking a simple explanation? :) Anyway, perhaps the "optimization" reference was misleading, you can read it as "best matching phase angle". I got a convincing exposition of it through the youtube video mentioned further up $\endgroup$
    – nikos
    Nov 2 '21 at 18:01
1
$\begingroup$

The crucial fact that makes this work is that we're considering functions in the $\mathcal{L}^2$ Hilbert space, and that the sinusoidals form an orthonormal basis of this space. As such, you can consider the linear functionals (I'm writing with domain $\Omega=[0,1]$) $$\begin{aligned} c, s &:\quad\mathcal{L}^2(\Omega) \to \mathbb{R} \\ c(f) &= 2\cdot\int_\Omega\!\mathrm{d}t\:f(t)\cdot\cos(2\cdot\pi\cdot t) \\ s(f) &= 2\cdot\int_\Omega\!\mathrm{d}t\:f(t)\cdot\sin(2\cdot\pi\cdot t) \end{aligned}$$ as equivalent representations of the sine and cosine functions themselves. (Cf. Riesz Representation theorem). Note that $$\begin{aligned} c(\cos) =& 1 & c(\sin) =& 0 \\ s(\cos) =& 0 & s(\sin) =& 1 \end{aligned}$$

Therefore, any linear combination of sine- and cosine components can be exactly analysed / broken down in the original components again by simply looking at the coefficients that drop out from application of $c$ and $s$.

To make it a full proof, you still need that every $L^2$ function actually has a linear combination of sinusoidals that converges to it, this is the completeness part of the definition of a Hilbert space.

$\endgroup$
0
$\begingroup$

I hope this helps nikos: Complex numbers are merely tools in a mathematicians tool box. in this case they are only another method for expressing "phase" or the evolution over time of an oscillatory signal usually expressed as a sine function (another tool). A Fourier transform is the summation of the phases and amplitudes from a defined place to another defined place. An example is a telescope lens: The lens performs a Fourier transform of the incident light passing thru the front surface of the lens to an image on the focal plane, each and every pixel on the image plane is the vector sum of all the incident light amplitudes and phases (path lengths) over the whole aperture. A piano with undamped strings will effectively respond and measure the frequency spectrum of a thunder clap, in other words a Fourier transform. There are even scalar Fourier transforms that do not require either phase or complex numbers, these are used to map the flow of heat in objects. I hope I have not been too qualitative?

$\endgroup$
0
$\begingroup$

I've always found that it's useful to keep in mine that $e^t$ is a helix of unit radius around the t axis. The sine and cosine functions represent the projection of that helix onto the real and imaginary planes. Multiplying by the helix thus gives you both the amplitude and phase of each frequency.

$\endgroup$
0
$\begingroup$

The phase doesnt have to be perfect. As long as there is a correlation in the pure frequency and the measured frequency, those effect will add up (either positively or negatively). If the frequencies are different, then their correlations will be almost random and cancel each other out over time.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.