fourier transformation with missing values

Question

i have a time discrete signal that may contain many missing values. and i want to do a fourier transformation on it.

what can i do to handle them properly?

following diagram may show the case

signalpresence  x  x  x  x  x  x  x              x  x  x  x  x  x  x              x  x  x  x  x  x  x              
timesteps       ^  ^  ^  ^  ^  ^  ^  ^  ^  ^  ^  ^  ^  ^  ^  ^  ^  ^  ^  ^  ^  ^  ^  ^  ^  ^  ^  ^  ^  ^  ^  ^  ^

the missing values are periodically since they came from the frame gap of an image sensor that row frequency is higher than the actual image height.

setting the missing values to zero distorts the output.

is there a library that handles time/value pairs?

(of course it has to be fast, too :-) )

Ganister

see scicomp.stackexchange.com/questions/593/…. There are some good links in the answers to software that may help. – Exactly

Every output value of a Fourier transform depends on every input value, so no matter what you do to "fill in" the missing values, the output will be distorted in some way - you can't just do a "partial transform" to get correct values for some outputs and not others. As @JasonB suggests, there are various ways to "fill in" those values to make the results more or less useful, but the "best" solution is going to depend a lot on your exact problem domain and what you are trying to achieve... – Biodegradable

Answer 1

This is actually non-trivial to solve, as it's a question of how to best educated guess about the missing data. A frequency domain optimized method of interpolation is given by the Lomb-Scargle algorithm, which is available in MATLAB via the plomb function

More info:

• Martin H. Trauth: Data Voids and Spectral Analysis: Don’t Be Afraid Of Gaps!
• C. Munteanu et. al: Effect of data gaps: comparison of different spectral analysis methods

Hydrant

Answer 2

One thing you could do is determine how the solution can vary by taking the fourier transform of all-zero-except-a-missing-value-set-to-1 vectors. Each of those will give you a vector along which the output can vary, without breaking the constraints set by the non-missing values. You can scale them and add them into the FFT you get from the vector resulting from just replacing the missing values with 0s.

Each of the missing value FFTs will give a linearly independent vector. I think they'll each be sine waves, because the FFT is almost its own inverse. Your solution vector can then have those sine waves added to it without breaking the constraints set by the known input. That is to say, the solution will be of the form:

FFT(dataWithZeroesForMissing)
+ c1*FFT(dataWithAllZeroesExceptOneMissingValueSetToOne1)
+ c2*FFT(dataWithAllZeroesExceptOneMissingValueSetToOne2)
+ ...

Your goal is to pick the "best" c1, c2, etc. What exactly that means depends on the use case. My best guess is "minimize the sum of squares of the result".

Turgescent

I have the same problem, I think it would be an interresting idea but I guess minimizing the sum squares is more or less equivalent to linear interpolate or at least it will provide a smooth signal the signal and it will tend to minimize the high frequencies. However it migth be the best solution for low frequency (when period is greater than the length of signal lose) An other solution would could to concatenate the part of signal while removing the difference between the two parts, I think it could be the most unbiaised method for high frequencies but clearly bad for low frequencies. – Michaelis