signal analysis - Is there any algorithm to decompose a wave into a set of given frequencies?

I heard about Fast Fourier Transform can decompose any waves.

But it seems like it was hitting for "all frequencies", namely, n HAVE TO be from 0 to N-1!

What if I want to decompose the wave into the frequencies I want!?

Such as, for example, 5Hz, 14Hz, 37Hz, 42Hz, 59Hz, etc.!?

Is there any algorithm that could do the job!?

PS. My understanding of FFT is from Google, and the degree of understanding is VERY limited! So PLEASE forgive me for my lack of knowledge and any stupid comments!

Answer

If you have a mixed signal of various known frequencies, the Goertzel answer mentioned above will you correct values only if you have chosen a frame size which has a whole number of cycles for each frequency. Otherwise, if the frequencies are spread far enough apart you will get an approximation. In general, you need to work harder than that to get the correct values.

To simplify, this example will use two of your frequencies, and I'll keep it real (as in not complex).

First you have to construct a cosine (C) and sine (S) signal (vector) for each frequency the length of your frame. Then you want to find the best fit solution to:

$$ x = a_5 C_5 + b_5 S_5 + a_{14} C_{14} + b_{14} S_{14} $$

Where $x$ is your signal as a vector. The $C$s and $S$s are called basis vectors. Dot your signal with each of them:

$$ \begin{aligned} C_5 \cdot x &= a_5 C_5 \cdot C_5 + b_5 C_5 \cdot S_5 + a_{14} C_5 \cdot C_{14} + b_{14} C_5 \cdot S_{14} \\ S_5 \cdot x &= a_5 S_5 \cdot C_5 + b_5 S_5 \cdot S_5 + a_{14} S_5 \cdot C_{14} + b_{14} S_5 \cdot S_{14} \\ C_{14} \cdot x &= a_5 C_{14} \cdot C_5 + b_5 C_{14} \cdot S_5 + a_{14} C_{14} \cdot C_{14} + b_{14} C_{14} \cdot S_{14} \\ S_{14} \cdot x &= a_5 S_{14} \cdot C_5 + b_5 S_{14} \cdot S_5 + a_{14} S_{14} \cdot C_{14} + b_{14} S_{14} \cdot S_{14} \end{aligned} $$

These equations can be put into convenient matrix form:

$$ \begin{bmatrix} C_5 \cdot x \\ S_5 \cdot x \\ C_{14} \cdot x \\ S_{14} \cdot x \end{bmatrix} = \begin{bmatrix} C_5 \cdot C_5 & C_5 \cdot S_5 & C_5 \cdot C_{14} & C_5 \cdot S_{14} \\ S_5 \cdot C_5 & S_5 \cdot S_5 & S_5 \cdot C_{14} & S_5 \cdot S_{14} \\ C_{14} \cdot C_5 & C_{14} \cdot S_5 & C_{14} \cdot C_{14} & C_{14} \cdot S_{14} \\ S_{14} \cdot C_5 & S_{14} \cdot S_5 & S_{14} \cdot C_{14} & S_{14} \cdot S_{14} \end{bmatrix} \begin{bmatrix} a_5 \\ b_5 \\ a_{14} \\ b_{14} \end{bmatrix} $$

Then it is simply a matter of multiplying both sides with the inverse of the square matrix:

$$ \begin{bmatrix} a_5 \\ b_5 \\ a_{14} \\ b_{14} \end{bmatrix} = \begin{bmatrix} C_5 \cdot C_5 & C_5 \cdot S_5 & C_5 \cdot C_{14} & C_5 \cdot S_{14} \\ S_5 \cdot C_5 & S_5 \cdot S_5 & S_5 \cdot C_{14} & S_5 \cdot S_{14} \\ C_{14} \cdot C_5 & C_{14} \cdot S_5 & C_{14} \cdot C_{14} & C_{14} \cdot S_{14} \\ S_{14} \cdot C_5 & S_{14} \cdot S_5 & S_{14} \cdot C_{14} & S_{14} \cdot S_{14} \end{bmatrix}^{-1} \begin{bmatrix} C_5 \cdot x \\ S_5 \cdot x \\ C_{14} \cdot x \\ S_{14} \cdot x \end{bmatrix} $$

So, for each frequency you have an $a$ and $b$ value. Your 5Hz component will be $ a_5 C_5 + b_5 S_5 $.

You can use the following to convert that into a phase and amplitude.

$$ A \cos( \omega t + \phi ) = A \cos( \omega t ) \cos( \phi ) - A \sin( \omega t ) \sin( \phi ) $$

From there, match:

$$ a = A \cos( \phi ) $$ $$ b = -A \sin( \phi ) $$

Which leads to:

$$ A = \sqrt{ a^2 + b^2 } $$

$$ \phi = \operatorname{atan2}(-b,a) $$

This is how a DFT actually works. When you select basis vectors that are a whole number of cycles, the square matrix turns out to be a multiple of the identity matrix and thus the inverse is trivial.

The Goertzel gives you a method of calculating $C_n \cdot x$ and $S_n \cdot x$ on the fly.