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 | ||||||||||||||||||||||
a | -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:
This method probably produces better results when the signal frequencies are high compared to the base value set period. For example the second and third graphical examples at the beginning of the text show the same signal. Yet it worked for the first of them and not for the second just because the first has a higher frequency.
Typically, one would use the sum of the square of the sinusoids amplitudes and not the sum of the absolute value of the amplitudes. This makes the method more suitable for analytical solutions. Yet I got better guess results using the absolute values... If the square of the amplitudes was used it would be a "least energy" algorithm. Since the absolute value of the amplitudes is used it should maybe be called a "least disorder" algorithm.
What if this method is applied to 2D, 3D... signals? That is for example photographs and digitalized solid objects. It will probably produce interesting results in some cases and awful mismatches in other cases. Just like for 1D signals.
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.