Wednesday, February 24, 2010

FFT (Fast Fourier Transform) of time series -- promises and pitfalls towards trading



Fig 1. FFT transformed time series (EBAY) reconstructed with first three and twenty harmonics, respectively.

I see quite a few traders interested in advanced signal processing techniques. It is often instructive to see why they may or may not be useful. The concept behind fourier analysis is that any periodic signal can be broken down into a taylor series or sum of suitably scaled sine and cosine waveforms (even a square wave!). The key requirement is that the signals are periodic, which means that they repeat forwards and backwards to plus and minus infinity. Anyone who deals with financial series knows they are aperiodic (meaning they do not repeat indefinitely). The FFT, or fast fourier transform is an algorithm that essentially uses convolution techniques to efficiently find the magnitude and location of the tones that make up the signal of interest. We can often play with the FFT spectrum, by adding and removing successive tones (which is akin to selectively filtering particular tones that make up the signal), in order to obtain a smoothed version of the underlying signal.

In the posted example, I showed the effect of reconstructing the transformed waveform using only the first three tones (and cutting off all others), where we see a low passed version of the signal. The second example includes the first 20 tones, which begins to match the signal more closely, but is a smoothed representation of the signal, which is often a nice representation to isolate smoothed signal component from high frequency noise. Notice the terms tones and harmonics are practically synonymous for purposes of this discussion (a harmonic is more specifically a multiple of the fundamental tone); both represent the spectral frequency components that sum up to make the total waveform. The major problem that I wanted to illustrate with this simple example (among many), is the problem of 'wraparound effects.' As I mentioned earlier, one of the requirements for properly applying a fourier transform is that the signal is periodic or repeating, since the basis functions (sines and cosines) that are convolved are infinitely repeating functions.

With that requirement, the reconstructed waveform tries its best to match the beginning and endpoints for periodic repetition. The result is severe problems at the endpoints (left and right), which are often the points we are most concerned about. So it often pays to be cautious when hearing about applications of higher level signal processing techniques. There are several other requirements and limitations to applying FFT techniques, among them: requirement of 2^n samples, fsample must be greater than or equal to twice the max bandwidth of sampled signal (nyquist criterion), limited spectral tone bin resolution; ignoring any of these issues can cause severe reconstruction errors.

17 comments:

  1. Interesting. I've bever been a fan of FFT for trading purposes due to some of the reasons you mentioned (you also provided a couple of new arguments). But, if I remember correctly, I think I've read something about market micro-structure analysis based on the spectrum generated when the price jumps between bid and ask. I think the basic idea was to use this for high-frequency trading (or market making?) and that this analysis would provide predictions on when the bid/ask range moves. This as an alternative to using price patterns. Don't know if this makes any sense though...

    ReplyDelete
  2. hugin,

    It's likely that they were using Wavelets, rather than FFT for the spectral analysis, as Wavelets have some benefits towards capturing localized information (including spikes). That being said, my guess is they found some type of correlation between jumps and direction shortly there-after. I could see this as a potential tool and have read similar papers in the past, but don't see any reason FFT would be a favorable tool to exploit it.

    ReplyDelete
  3. Wavelets are probably a better alternative. It might actually be what was in the paper - my memory might be playing tricks with me.

    ReplyDelete
  4. I had the idea of using time-series analysis for trading while doing some research into black holes at Harvard last summer. There I used a Lomb-scargle method and various filtering techniques to find periods in x-ray intensities. I was thinking about using the same method but applied to share price. i was wondering if you could recommend me any literature on the topic or names of any firms which currently use similar methods?

    Many Thanks,
    Joseph Fenton
    J.M.C.Fenton@Warwick.ac.uk

    ReplyDelete
  5. Joseph,

    I'm not sure of any firms that use the methods offhand, but most of the well known literature (books at least) in this area is produced by John F. Ehlers, an expert in DSP applications that translated many of those ideas to financial time series.


    Many of my blogs cover some of the pitfalls as well. Namely that financial time series are both non-stationary and aperiodic. Good Luck.

    P.S. If you don't want your email public send me another pm, and I'll delete your post.
    I don't have control over which parts get published.

    IT

    ReplyDelete
  6. This comment has been removed by a blog administrator.

    ReplyDelete
  7. hey,
    I am an undergraduate student from Indian Institute of Technology Bombay , India.
    I currently working on how to use DSP in Trading. Could you please refer me some material , book , journal etc.
    looking forward to your reply.
    Thanking You

    Regards,
    Shubham

    --------------------------------------
    Shubham,

    I edited your letter to omit your email.
    Much of the published work that is related to DSP in book format can be attributed to the author John Ehlers.
    http://www.mesasoftware.com/index.htm

    IT

    ReplyDelete
  8. Overfitting seems to be an obvious problem. You can theoretically completely decompose the time series up to that point, but how robust will that be for new data?

    Personally, I think the problem with FFT is that it incoporates all past data in the decomposition, which assumes that all past data comes from a fundamentally periodic generator. In times of noise trading, this might be true, but at least some price movements are driven by fundamental news which I don't think is necessarily "periodic".

    ReplyDelete
  9. Hi,

    FFTmaybe not be suitable when wee need to reconstruct the orignal time series. for instance when we try o predict. However, it can still be a good technique to understand the risk of taking a buy/sell position. Another application of the spectrum could be to quantify the option price.
    Do you agree? In this case, can you point me to some refference in this respect?

    Thank you

    ReplyDelete
  10. Hi Anon,
    1) Not suitable for reconstruction as the filtered signal loses information. However, it also reduces the effect of noise, which can be a positive aspect for prediction purposes.

    There are several references on use of FT for option pricing. You can google numerous references to this.
    ex.
    www.math.nyu.edu/research/carrp/papers/pdf/fftpres.pdf
    http://www.maxmatsuda.com/papers.htm

    IT

    ReplyDelete
  11. thank you very much for your article

    it was exactly what I was looking for,
    understanding what is the greatest pitfall of fft in the markets

    ReplyDelete
  12. hi
    would i be able to model post-event market disturbance using fft?
    (where event is earnings release, news etc)

    thank you
    r

    ReplyDelete
  13. Thinking about an electric signal, there is often a DC offset, and I wonder if could make some problems on FFT of stock prices. Did you try to evaluate an average price of 100 bars (for example), and doing FFT of close_price(t)-average_price of the latest 100 bars, and after FFT reconstruct prices adding average_price?
    What kind of tools or libraries did you use for FFT (matlab, python, etc)?
    Thanks for your attention

    ReplyDelete
  14. I wonder if FFT performed on the latest 100 closing price minus the average of the latest 100 days of a stock (so a FFT of a signal crossing above and below 0) could get better results when reconstructed and summed up with its average, in terms of better accuracy of the latest bar.
    Did anybody tried that?

    ReplyDelete
  15. Hi beppone,

    You could try to remove DC offset (or mean of response), however, the resulting series will not be necessarily stationary, nor is the variance of the data likely to remain stable.

    I used Python for these particular studies.

    IT

    ReplyDelete
  16. Hi
    Could I use this technique to analyze volumes or equity turnover off exchanges?

    Thanks
    Josh

    ReplyDelete
  17. Josh,
    It could be used for any time series, but don't forget to take pitfalls into consideration.
    IT

    ReplyDelete