Forecasting by frequency interpolation of time series

2025-01-18

The FITS algorithm propsed by Xu et.al in FITS: Modeling time series with 10k parameters, uses a neat trick from signal processing to forecasting.

The principle it exploits is: increasing the resolution in the frequency domain also increases the signal length in the time domain. In other words, longer time series provides a higher frequency resolution.

The algorithm extends the resolution of the power spectral density as follows:

1. De-mean the time series by subtracting the mean. This gets rid of the DC component (the dominant zero-frequency amplitude in the PSD).
2. Compute the real Fourier transform (rFFT) of the time series getting back a complex valued signal.
   1. The rFFT condenses the length of the time series N to N/2+1 complex numbers.
3. Learn the complex valued signal, the amplitude and phase, using a linear layer with complex type.
   1. The layer has input size F and output size F * length_ratio. Where, F is the length of the complex valued signal and length_ratio is (sequence_length + prediction_length) * sequence_length. Length ratio is therefore > 1 and F * length_ratio is larger than the original frequency resolution F.
4. Add back the mean to the predicted signal.
5. Compute the inverse rFFT to get the predicted time series, which is now longer than the original time series.

The method is fast, because the FFT is fast, It is also memory efficient, because working in the frequency domain and using complex valued paramaters reduces the number of parameters to learn. A major benefit is the model supervises both the forecasting horizon but also backcasting on the look-back window. One concern is that the method does not do a good job at capturing the local-linear trends in the time series but should do a good job at capturing the periodicity.