Fourier transform capabilities in reconstructing missing data

[Gedelian]

Hi,

I know this topic is more suited for Computing & Technology, but it has even more to do with general questions about Fourier transform capabilities. I have a question about sample restoration in Discrete Fourier Transform. Suppose we have a signal with the stack of frequencies from 1 Hz to 128 Hz, and the number of samples is twice the number of frequencies, i.e. 256. If for some reason half of the samples is lost, first half or last half (128 samples), can we restore completely those lost samples from the remaining half? Note that in this case the one who has to restore the signal doesn`t know what frequencies are in the signal, but does know the number of the missing samples. Can we find all the frequencies from that sparse signal? In this example, the frequencies are harmonics and all beginning at the same faze and with the same amplitude.

If we apply FFT algorithm on the time domain, I assume that the information about missing samples can be extracted from the frequency domain, because all sine waves have the same length in a time domain, and the only thing which happened is that frequencies are missing their fazes, for example, 1Hz is cut in half of its faze, 2Hz are missing a whole faze, and so on. Is it possible to use FFT to analyze the remaining samples, discover all the frequencies in a frequency domain, and use those frequencies to recreate a time domain and restore missing samples?

I ask this because I found a paper about recovering missing samples from oversampled band-limited signals. There is a statement in it which says that a band-limited oversampled signal is completely determined even if an arbitrary finite number of samples is lost. I understood this statement as described above. I just want to clarify this in the general sense of the matter, the possibility or feasibility of that kind of sample restoration.

And, if this method of sample restoration is possible, I have another question. Given the previous example, can a signal be restored if we continue to stack frequencies from 128Hz on, as f_n + 1Hz = f_n+1, n<256? Is there an algorithm that can find all the frequencies in a partial time domain, as I described here, even if there are greater number of frequencies than the number of remaining samples?

If it`s not absolutely necessary, please don`t insert math equations because all I see is [Math Processing Error], write them in text instead. Thank you.

 

[AlephZero]

The key words are "oversampled" and "bandwidth limited".

Without those restrictions, you can't reconstruct anything, because every data point (in the both the time domain and the frequency domain) is independent of all the other data points.

 

[Gedelian]

OK, my mistake. Let`s say that, in the same example, the stack of frequencies is still from 1 to 128 Hz, the max bandwidth is 256 Hz, and the signal is oversampled 2x, giving the total of 512 samples. If half of the samples are lost (first or last 256 samples), is it possible to restore the whole signal without losses? And if that same signal had additional frequency stacking like f<sub>n</sub> + 1Hz = f<sub>n+1</sub>, n<256, can all those frequencies be restored in their domain, and make an inverse FFT to recreate a complete time domain with all 512 original samples? And, if it`s possible, how it`s done?

Sorry for all those question marks, I hope to find the wright answers.

Thanks again.

 

[AlephZero]

If should be farily easy to see this won't work, without doing any math. If it did work, you could repeat it as may times as you want, and re-create an arbitrary amount of the original signal from just 256 samples.

If you are sampling at 512 samples/sec, your 256 samples cover 0.5 sec of data. When you do the FFT, you get frequencies of 0, 2, ... 512 Hz (or -256, -254, ... -2, 0, 2 ... 256 of you prefer). If the signal is bandwidth limited to 128 Hz, half of the amplitudes should be zero, but the calculated ampltides will NOT be zero, because the FFT is taking a finite length of data and assuming that is repeats as a periodic signal. That periodic signal will NOT be bandwidth limited to 128 Hz, because the two ends of the sample won't "match up" properly. It will only be limited to the Nyquist frequency of 256 Hz.

So, if you try to extend the 256 samples to 512, you have two problems. One is that half the 256 Fourier coefficients are "wrong" (they are nonzero but they should be zero). The other is that you don't have amplitudes for the frequencies of 1, 3, 5 ... 255 Hz. You could make some approximations to generate the missing Fourier data, but that won't re-create the missing data exactly.

There is an underlying "catch 22" here. A bandwidth limited (analog) signal must have nonzero amplitude for an infinite amount of time, so you can't represent its frequency content "exactly" from a finite number of samples. On the other hand, a signal with infinite bandwidth CAN be zero everywhere except for a finite time interval, but you can't represent it "exactly" with a finite number of frequencies so you need still need an "infinite" number of samples and an "infintely high" sampling rate.

Of course you can use techniques like this to change the sample rate and/or interpolate missing data approximately in a useful way, but that's not the same as regenerating the missing data exactly.