Eric Brasseur Home    |    Links    |    Contact    |   
   



Numerical interpolation using Fourier Transform







A signal can be recorded by making successive measures of its intensity. A possible problem is one or more measure values are lost or impossible to achieve. These missing measures can be interpolated, guessed, using different mathematical methods. One such methods implies the Fourier Transform. Its basic principle is very simple : try out every possible values and keep the ones that yield the sinusoidal functions with globally the least amplitude.

This method produces often a smooth result, comparable to what a human brain would have done.

These are examples of correct guesses using this method:


In some cases tough the result is contradictory to what common sense would have suggested. So the choice of this technique depends on the type of signal involved. Furthermore this method involves heavy computer calculations while other methods need only a few simple computations.

This is an example of incorrect guess:


Here comes a numerical example. Say following set of measures. (It is a copy of the first graphical example above.) The sixth value is supposed to be unknown:

0 7 10 7 0 ? -10 -7

All values between -15 and +15 will now be tried out for that sixth value. The table bellow shows the 31 test sets. Right to them are the corresponding amplitudes of sinusoids, calculated by numerical Fourier Transform. At the rightmost is the sum of the absolute values of the amplitudes:

0 7 10 7 0 -15 -10 -7       FT->       1.00 11.45 2.00 1.96 1.00       sum->       17.42
0 7 10 7 0 -14 -10 -7       FT->       0.87 11.25 1.75 1.71 0.87       sum->       16.47
0 7 10 7 0 -13 -10 -7       FT->       0.75 11.06 1.50 1.46 0.75       sum->       15.53
0 7 10 7 0 -12 -10 -7       FT->       0.62 10.86 1.25 1.21 0.62       sum->       14.58
0 7 10 7 0 -11 -10 -7       FT->       0.50 10.68 1.00 0.96 0.50       sum->       13.65
0 7 10 7 0 -10 -10 -7       FT->       0.37 10.49 0.75 0.71 0.37       sum->       12.71
0 7 10 7 0 -9 -10 -7       FT->       0.25 10.30 0.50 0.46 0.25       sum->       11.78
0 7 10 7 0 -8 -10 -7       FT->       0.12 10.12 0.25 0.21 0.12       sum->       10.85
0 7 10 7 0 -7 -10 -7       FT->       0.00 9.94 0.00 0.05 0.00       sum->       10.00
0 7 10 7 0 -6 -10 -7       FT->       0.12 9.77 0.24 0.28 0.12       sum->       10.56
0 7 10 7 0 -5 -10 -7       FT->       0.25 9.60 0.49 0.53 0.25       sum->       11.14
0 7 10 7 0 -4 -10 -7       FT->       0.37 9.43 0.74 0.78 0.37       sum->       11.72
0 7 10 7 0 -3 -10 -7       FT->       0.50 9.26 0.99 1.03 0.50       sum->       12.31
0 7 10 7 0 -2 -10 -7       FT->       0.62 9.10 1.24 1.28 0.62       sum->       12.89
0 7 10 7 0 -1 -10 -7       FT->       0.75 8.95 1.49 1.53 0.75       sum->       13.49
0 7 10 7 0 0 -10 -7       FT->       0.87 8.79 1.74 1.78 0.87       sum->       14.09
0 7 10 7 0 1 -10 -7       FT->       1.00 8.65 1.99 2.03 1.00       sum->       14.69
0 7 10 7 0 2 -10 -7       FT->       1.12 8.50 2.24 2.28 1.12       sum->       15.29
0 7 10 7 0 3 -10 -7       FT->       1.25 8.37 2.49 2.53 1.25       sum->       15.91
0 7 10 7 0 4 -10 -7       FT->       1.37 8.23 2.74 2.78 1.37       sum->       16.52
0 7 10 7 0 5 -10 -7       FT->       1.50 8.11 2.99 3.03 1.50       sum->       17.15
0 7 10 7 0 6 -10 -7       FT->       1.62 7.98 3.24 3.28 1.62       sum->       17.78
0 7 10 7 0 7 -10 -7       FT->       1.75 7.87 3.49 3.53 1.75       sum->       18.41
0 7 10 7 0 8 -10 -7       FT->       1.87 7.76 3.74 3.78 1.87       sum->       19.05
0 7 10 7 0 9 -10 -7       FT->       2.00 7.66 3.99 4.03 2.00       sum->       19.70
0 7 10 7 0 10 -10 -7       FT->       2.12 7.56 4.24 4.28 2.12       sum->       20.35
0 7 10 7 0 11 -10 -7       FT->       2.25 7.47 4.49 4.53 2.25       sum->       21.01
0 7 10 7 0 12 -10 -7       FT->       2.37 7.39 4.74 4.78 2.37       sum->       21.68
0 7 10 7 0 13 -10 -7       FT->       2.50 7.32 4.99 5.03 2.50       sum->       22.36
0 7 10 7 0 14 -10 -7       FT->       2.62 7.25 5.24 5.28 2.62       sum->       23.04
0 7 10 7 0 15 -10 -7       FT->       2.75 7.20 5.49 5.53 2.75       sum->       23.74

The lowest sum of amplitudes is 10.00 so the corresponding set of sine waves is considered to have globally the least amplitude. The value tried out to get these sine waves is -7 so that's the answer. A value of -7 is the best guess for the sixth value, according to this method:

0 7 10 7 0 -7 -10 -7

Here we used "brute force" calculation. We tried out every value. Yet since the values of the sums follow a neat V-shaped curve, simple search algorithms can be used to find the correct guess using just a few trials. Newton algorithm should be fine. (We used only integer values. Floating point numbers can be used too. Provided a search and approximate algorithm is used like mentioned above.)

This is the graph of sum values versus sixth data values tried out:


Will the sums curve always follow a neat V shape? Indeed in above example the values set is very simple and regular. Will we get a neat V shape if the values set is random? Answer is yes. Let's try out following set. (The values were found by throwing a dice. One value is found by throwing the dice two times and subtracting the outcomes. Say first throw yields 3 and second throw yields 5, the value will be 3 - 5 = -2.)

2 1 -2 -3 -5 ? -4 -1

This is the graph of sums values we get, trying -15 to 15 for the unknown sixth value:


According to this graph the best sixth value is -4. (Please note in this case using this guess method makes little sense. All eight values are random. So the best way to guess an acceptable sixth value is to generate a purely random value the same way. By applying our less disorder guess method we made the signal a little less random. Anyway, we needed to do so just to show any set of values will generate a neat V-shaped sums curve with a sole and clear best answer.)

What if two values have to be guessed? Like in the graphical examples at the top of the page. Of course we can use the brute force algorithm and try out every combination of two values. This will make a lot of calculations yet we will get a best result. (At least one.) But will we get a neatly shaped graph with one clear best outcome, like above? Answer is yes. And this will be the case whatever amount of values have to be guessed.

Let's use again our set of random values and suppose the third and sixth value have to be guessed (we name them a and b):

2 1 a -3 -5 b -4 -1

Following table shows the sums results for every combination of a and b each between -10 and +10. The shade of blue shows the sum value. Darkest blue is for the lowest sum (the best result). The wighter the blue shade, the higher the sum.


b

-10 -9 -8 -7 -6 -5 -4 -3 -2 -1 0 1 2 3 4 5 6 7 8 9 10
10 14.3 13.8 13.4 13.0 12.6 12.3 12.0 11.8 11.6 11.4 11.2 11.3 11.5 11.6 11.8 11.9 12.1 12.6 13.0 13.5 14.0
9 13.7 13.2 12.7 12.3 12.0 11.6 11.4 11.1 10.9 10.7 10.6 10.4 10.6 10.7 10.9 11.1 11.5 12.0 12.4 12.9 13.4
8 13.0 12.5 12.0 11.6 11.3 10.9 10.7 10.4 10.2 10.1 9.9 9.8 9.7 9.9 10.1 10.5 11.0 11.4 11.9 12.4 12.8
7 12.4 11.9 11.4 11.0 10.6 10.3 10.0 9.8 9.6 9.4 9.3 9.2 9.1 9.1 9.5 10.0 10.4 10.9 11.4 11.8 12.3
6 11.8 11.3 10.7 10.3 9.9 9.6 9.3 9.1 8.9 8.8 8.7 8.6 8.6 8.8 9.0 9.4 9.9 10.4 10.9 11.3 11.8
5 11.3 10.7 10.1 9.6 9.2 8.9 8.7 8.5 8.3 8.2 8.1 8.1 8.3 8.5 8.7 8.9 9.4 9.9 10.4 10.9 11.4
4 10.8 10.1 9.5 9.0 8.6 8.2 8.0 7.9 7.7 7.7 7.6 7.8 8.1 8.3 8.5 8.8 9.0 9.5 10.0 10.5 11.0
3 10.4 9.6 9.0 8.4 7.9 7.6 7.4 7.3 7.2 7.2 7.4 7.6 7.9 8.1 8.4 8.6 8.9 9.1 9.7 10.2 10.8
2 10.2 9.3 8.5 7.8 7.3 7.0 6.8 6.8 6.7 7.0 7.2 7.5 7.7 8.0 8.3 8.5 8.8 9.1 9.4 10.1 10.7
1 10.1 9.1 8.1 7.4 6.9 6.4 6.4 6.4 6.6 6.9 7.1 7.4 7.7 8.0 8.2 8.5 8.8 9.2 9.6 10.0 10.7
0 10.1 9.1 8.2 7.2 6.6 6.3 6.2 6.4 6.6 6.9 7.1 7.4 7.7 8.0 8.3 8.6 8.9 9.3 9.8 10.2 10.8
-1 10.3 9.3 8.4 7.5 6.7 6.3 6.4 6.5 6.7 7.0 7.2 7.5 7.8 8.1 8.4 8.8 9.1 9.6 10.0 10.5 11.1
-2 10.5 9.6 8.7 7.8 7.1 6.8 6.7 6.8 7.0 7.2 7.4 7.7 8.0 8.3 8.6 9.0 9.4 9.8 10.3 10.9 11.5
-3 10.7 9.9 9.0 8.2 7.7 7.4 7.2 7.2 7.3 7.5 7.7 7.9 8.2 8.5 8.9 9.3 9.7 10.2 10.7 11.3 11.9
-4 11.1 10.2 9.4 8.8 8.4 8.0 7.8 7.7 7.7 7.9 8.0 8.3 8.6 8.9 9.2 9.7 10.1 10.6 11.1 11.7 12.3
-5 11.4 10.6 10.0 9.5 9.1 8.7 8.5 8.3 8.3 8.3 8.5 8.7 9.0 9.3 9.7 10.1 10.5 11.0 11.6 12.1 12.7
-6 11.8 11.2 10.7 10.2 9.8 9.4 9.2 9.0 8.9 8.9 9.0 9.2 9.5 9.8 10.2 10.6 11.0 11.5 12.1 12.6 13.2
-7 12.4 11.9 11.4 10.9 10.5 10.2 9.9 9.7 9.6 9.6 9.7 9.8 10.1 10.4 10.7 11.1 11.6 12.1 12.6 13.1 13.7
-8 13.1 12.5 12.1 11.6 11.2 10.9 10.7 10.5 10.3 10.3 10.4 10.5 10.7 11.0 11.3 11.7 12.1 12.6 13.1 13.7 14.2
-9 13.8 13.3 12.8 12.4 12.0 11.7 11.4 11.2 11.1 11.1 11.1 11.2 11.4 11.7 12.0 12.3 12.8 13.2 13.7 14.3 14.8
-10 14.5 14.0 13.5 13.2 12.8 12.5 12.2 12.1 11.9 11.9 11.9 12.0 12.2 12.4 12.7 13.0 13.4 13.9 14.4 14.9 15.4

Best sum result is 6.2. For a = 0 and b = -4. So the method yields as its best guess following set of values:

2 1 0 -3 -5 -4 -4 -1

The sums draw a neat wok shape. With the lowest part of the "wok" at a height of 6.2. The fact we get a clean wok shape is unavoidable. We know indeed that, for whatever value of b, the values of a will draw a neat V-shaped line:


Reciprocally, for every value of a the values of b will draw a neat V-shaped line too:


The only way to get neat V-shaped lines both horizontally and vertically is to draw a global neat wok shape:


This reasoning keeps true whatever amount of values have to be guessed. So we know there will always be one sole best answer. And that answer will be easy to converge towards using simple algorithms. (For really large amounts of values to be guessed more than one best choice will be possible. But they will be adjacent. So if we find one of them we get them all.)

To end with, some more remarks:

Simple and unoptimized C++ programs source codes are available here: interp.zip. A more powerful program source will probably be added in a close future.

Thanks to Pascal Bourgeat and Didier Bizzarri for their help, data and inspiration.



Eric Brasseur  -  Novembre 25 2002
www.000webhost.com