Re: Discrete Deconvolution

harrisrj@xxxxxxx wrote:

Hello, all.

I have a dilemma. I'm analyzing some time signals for periodicities,
and I was wondering about a seemingly basic method of doing it. I hope
you'll forgive my ignorance, as my specialty is physics and not signal
processing :P

So, we have a time-series that is the product of a source signal and a
window function :

c(t_i) = w(t_i)s(t_i)

where t_i represents the i_th time bin, c is the measured signal, w is
a window function, and s is the actual source signal. I know the FFT
of c(t_i) = c(\omega_i) , and the FFT of the window function,
w(\omega_i). However, I would really like to know the FFT of s,
s(\omega_i).

I hear about deconvolution from image analysis in astronomy and other
places, but am unfamiliar with it in time-series analysis. I know it's
an ill-posed mathematical problem, but is there a way to extract
information about s(\omega_i) by using some sort of deconvolution
method? Thanks.

Do you no longer have the original time series? If you _have_ s(t_i) just take it's FFT. If you don't, then take the inverse FFT of c(t_i) and divide it by the inverse FFT of w(t_i) point by point, taking the fact that w(t_i) probably has some points equal to zero.

But this is a bad idea for several reasons.

In all but some very rare cases the FFT of a time series is an approximation of some other Fourier transform that you'd like to take but can't. The FFT, by itself, is just a really fast way of finding the Fourier series of a periodic waveform in discrete time, who's period is equal to the number of points you're feeding into the FFT. That's all.

The FFT can be used as an approximation of the Fourier transform of a signal in sampled time with an infinite number of points, which is in turn an approximation of a signal in continuous time that extends into infinity. Like all approximations, however, the FFT has its problems when it's used in this way.

The biggest problem is that while _you_ think you're taking the Fourier transform of a signal that happens to be of finite extent, the FFT thinks that it's taking the transform of a signal that repeats, that is that s(t_N) = s(t_0) for an N-point FFT. Usually this is a whopping big discontinuity, which makes the algorithm report lots of really high-frequency content which simply isn't there in the real signal.

This big problem is solved by windowing, as a way to get the algorithm to cough up an approximate Fourier transform that has some hope of being close. I can almost guarantee you that if you take away the windowing you'll take away any hope of having an accurate representation of your original process.

But you can find this out yourself: Pick an N, and generate a cosine wave that has a frequency of 10.5/N -- that is, it starts at 1 at t_0, and goes to nearly -1 at t_{N-1}. Now take a FFT of it -- does it look like a clean spike, balanced between bins 10 and 11? Now window it, and do another FFT -- any better?

Perhaps if you tell us what you want to learn by all this we can help you find the right algorithm.

--

Tim Wescott
Wescott Design Services
http://www.wescottdesign.com

Posting from Google? See http://cfaj.freeshell.org/google/

"Applied Control Theory for Embedded Systems" came out in April.
See details at http://www.wescottdesign.com/actfes/actfes.html
.

Relevant Pages

  • Re: Are harmonics real?
    ... Harmonics in a signal are as real as those mathematics, ... < case of the Fourier transform that's pretty darn real -- you can sum up ... related signals, though not all. ... < The FFT case is a bit problematical, because the FFT is only exact if you ...
    (comp.dsp)
  • Re: Are harmonics real?
    ... Harmonics in a signal are as real as those mathematics, and in the < case of the Fourier transform that's pretty darn real -- you can sum up < all the energy in a signal in your choice of real time or the Fourier < frequency domain, and you get exactly the same number. ... related signals, though not all. ... < The FFT case is a bit problematical, because the FFT is only exact if you < happen to be dealing with a periodic and sampled signal. ...
    (comp.dsp)
  • Re: Analyzing fundamental frequencies from musical signals
    ... This is about analyzing fine detail in pitch and pitch changes ... As you found, zero-padding and using a long fft, although a very ... Plot that phase difference. ... accurate and reliable on real audio signals. ...
    (comp.dsp)
  • Re: Secure passwords?
    ... >> noise using FFT integration. ... An FFT is an FFT is an FFT is an FFT! ... As an index of how commonplace an EE problem extracting signals from ... metallic-deposition-layer glass used for emsec shielding where visibility ...
    (alt.computer.security)
  • Re: Oversampling and the FFT
    ... I suggested we sample just above Nyquist and perform our 1024 point FFT. ... regardless of the window function or sample rate. ... Also the phase of a sharp filter may change ... signals near the Nyquist frequency of a given sampling rate than ...
    (comp.dsp)