PaperlayerView exact revision on arXiv

Source-linked AI summary

FEDformer: Frequency Enhanced Decomposed Transformer for Long-term Series Forecasting

Tian Zhou, Ziqing Ma, Qingsong Wen, Xue Wang, Liang Sun, Rong Jin

arXiv:2201.12740v3cs.LGstat.ML

TL;DR

Long-term forecasting models can struggle to capture time series’ global characteristics while remaining computationally efficient. FEDformer combines seasonal-trend decomposition with frequency-enhanced Transformer blocks and achieves state-of-the-art forecasting performance, reducing error by 14.8% for multivariate and 22.6% for univariate series.

  • Problem

    Transformer-based forecasters can fail to capture the overall characteristics and distribution of time series, limiting global-profile modeling.

  • Method

    FEDformer combines mixture-of-experts seasonal-trend decomposition with Fourier- and wavelet-enhanced Transformer blocks that operate in the frequency domain.

  • Results

    FEDformer reduces prediction error by 14.8% for multivariate and 22.6% for univariate forecasting across six benchmark datasets.

  • Takeaways & Limitations

    FEDformer delivers state-of-the-art long-term forecasting with linear computational complexity and memory cost.

  • Takeaways & Limitations

    The theoretical frequency-selection result assumes that the Fourier-basis matrix has coherence measure Ω(k/n).

Abstract

from arXiv · show

Although Transformer-based methods have significantly improved state-of-the-art results for long-term series forecasting, they are not only computationally expensive but more importantly, are unable to capture the global view of time series (e.g. overall trend). To address these problems, we propose to combine Transformer with the seasonal-trend decomposition method, in which the decomposition method captures the global profile of time series while Transformers capture more detailed structures. To further enhance the performance of Transformer for long-term prediction, we exploit the fact that most time series tend to have a sparse representation in well-known basis such as Fourier transform, and develop a frequency enhanced Transformer. Besides being more effective, the proposed method, termed as Frequency Enhanced Decomposed Transformer ({\bf FEDformer}), is more efficient than standard Transformer with a linear complexity to the sequence length. Our empirical studies with six benchmark datasets show that compared with state-of-the-art methods, FEDformer can reduce prediction error by $14.8\%$ and $22.6\%$ for multivariate and univariate time series, respectively. Code is publicly available at https://github.com/MAZiqing/FEDformer.

1. Introduction

FEDformer addresses limitations of RNN- and Transformer-based long-term forecasting by combining seasonal-trend decomposition with frequency-domain enhancements. It captures global time-series properties while reducing computational and memory costs, and improves results across six benchmark datasets.

  • RNN-type methods can suffer from vanishing or exploding gradients, limiting their performance in long-term time-series forecasting.
  • Transformer-based methods may fail to capture the overall characteristics or distribution of time series in some cases.A vanilla Transformer prediction on the real-world ETTm1 dataset showed a distribution different from the ground truth.
  • FEDformer uses a frequency-enhanced decomposed Transformer with mixture-of-experts seasonal-trend decomposition to better capture global time-series properties.
  • Fourier- and wavelet-enhanced blocks replace self-attention and cross-attention, capturing important time-series structures through frequency-domain mapping.
  • Randomly selecting a fixed number of Fourier components gives FEDformer linear computational complexity and memory cost, with theoretical and empirical verification.
  • 14.8% and 22.6% improvements over state-of-the-art methods were reported for multivariate and univariate forecasting, respectively, across 6 benchmark datasets.The datasets span energy, traffic, economics, weather, and disease domains.

2. Compact Representation of Time Series in Frequency Domain

FEDformer represents multivariate time series in the frequency domain, using Fourier analysis with a selectively sampled set of components to reduce representation size while preserving most information under a mild condition. Wavelet-based representations are also considered for better capture of local structures in some forecasting tasks.

  • Frequency-domain representation: Fourier transforms convert each of m time series into vectors, forming a matrix whose columns represent distinct frequency components.Using all components best preserves historical information but may produce inferior representations.
  • Random Fourier sampling: Randomly selecting s Fourier components constructs A′ = AS^T, which can preserve most information from A under a mild condition.The selected components are represented by a binary selection matrix S.
  • Information preservation: Information preservation is evaluated by projecting A onto the subspace spanned by A′ and measuring the resulting approximation error.The analysis compares A with its projection and relates approximation quality to the rank-k singular-value decomposition approximation.
  • Theoretical guarantee: Under the stated coherence assumption, the theorem provides a high-probability guarantee when s = O(k^2/ε^2).The theorem assumes that the coherence measure μ(A) satisfies μ(A) = Ω(k/n).
  • Wavelet representation: Wavelet-based representations can capture local time-series structures more effectively than Fourier bases and may improve some forecasting tasks.Wavelet orthogonal polynomials such as Legendre Polynomials obey the restricted isometry property.

3. Model Structure

FEDformer renovates the Transformer into a deep decomposition architecture that combines frequency-enhanced encoder-decoder blocks with mixture-of-experts seasonal-trend decomposition. Its Fourier- and wavelet-based variants use selected frequency modes to achieve linear time and memory complexity.

  • FEDformer Structure: FEDformer’s deep decomposition architecture comprises Frequency Enhanced Blocks, Frequency Enhanced Attention connecting encoder and decoder, and a Mixture Of Experts Decomposition block.These components are detailed respectively in Sections 3.2, 3.3, and 3.4.
  • Frequency-Enhanced Blocks: FEB has Fourier and wavelet versions implemented with DFT and DWT, respectively, that can replace self-attention.FEA similarly has DFT- and DWT-based versions that can replace cross-attention.
  • Mixture Of Experts Decomposition: MOEDecomp combines average filters of different sizes with data-dependent weights to extract and combine multiple trend components.It is designed to address complex periodic patterns coupled with trends that fixed-window average pooling may not capture well.
  • Complexity Analysis: O(L) time and memory complexity is achieved by FEDformer-f with a fixed number of randomly selected modes in FEB and FEA, using M = 64 by default.This is lower than the O(L log(L)) cost of full DFT computation by FFT.
  • Complexity Analysis: O(L) time complexity and memory usage are also obtained by FEDformer-w when the recursive decomposition depth and selected mode count are fixed.The default settings are L = 3 and modes number M = 64.

4. Experiments

FEDformer is evaluated on six real-world datasets across long-term multivariate and univariate forecasting tasks, with comparisons against state-of-the-art Transformer models. It achieves substantial error reductions over Autoformer, while additional experiments examine its frequency-enhanced components, Fourier-mode selection, and output-distribution similarity.

  • Multivariate Results: FEDformer achieves the best multivariate forecasting performance on all six benchmark datasets across all evaluated horizons.The experiments use Transformer-based baselines including Autoformer, Informer, LogTrans, and Reformer.
  • Multivariate Results: 14.8% overall relative MSE reduction is achieved by FEDformer compared with Autoformer in multivariate forecasting.The reduction exceeds 20% on datasets such as Exchange and ILI and remains consistent across varying horizons.
  • Univariate Results: 22.6% overall relative MSE reduction is achieved by FEDformer compared with Autoformer in univariate forecasting.On datasets such as traffic and weather, the improvement exceeds 30%; FEDformer-f and FEDformer-w perform well on different datasets.
  • Ablation Studies: Three ablation variants test replacing self-attention, cross attention, or both with FEDformer’s frequency-enhanced blocks.The variants are evaluated against Autoformer and other state-of-the-art models on multivariate ETTm1 and ETTm2 forecasting.
  • Fourier Basis Selection: Random Fourier-mode selection is empirically compared with fixed selection because it supports effective signal representation without prior input knowledge.The paper identifies random selection as better suited to forecasting and easier to generalize to new tasks.
  • Distribution Similarity: At a common P-value of 0.01, most existing Transformer baselines produce much lower Kolmogorov–Smirnov test values than 0.01, whereas Autoformer is the exception.The test evaluates whether fixed-length input sequences and predicted sequences come from the same distribution on ETTm1 and ETTm2.

5. Conclusions … B.1. RIP Matrices

FEDformer combines frequency-enhanced attention with seasonal-trend decomposition to achieve accurate long-term forecasting with linear computational and memory complexity. The paper situates this approach among forecasting, Transformer, Fourier, low-rank approximation, and RIP-matrix methods.

  • 5. Conclusions: FEDformer achieves state-of-the-art long-term forecasting with linear computational complexity and memory cost through frequency-enhanced attention and mixture-of-experts decomposition.The frequency-enhanced structure decouples input sequence length from attention-matrix dimension.
  • A.1. Traditional Time Series Models: Data-driven time-series forecasting developed from traditional models into methods supporting system understanding without explicitly specifying governing physical laws.ARIMA is identified as an early autoregressive approach based on the Markov process.
  • A.2. Transformers for Time Series Forecasting: Transformer-based forecasting commonly uses encoder-decoder architectures with self-attention and cross-attention as core mechanisms.The literature review places these models after Transformer advances in natural language processing and computer vision.
  • A.2. Transformers for Time Series Forecasting: Transformer forecasting efficiency has been improved through predefined sparse patterns, top-k truncation, and low-rank approximations of attention matrices.Examples include LogTrans with N log2 N complexity, Informer and Autoformer with N log N complexity, and Linformer and Luna with O(n) complexity.
  • A.3. Fourier Transform in Transformers: FFT reduces Fourier-transform computation from N^2 to N log N, while Fourier methods support efficient convolution and low-frequency representation learning.Fourier and wavelet neural operators apply these ideas in PDE and computer-vision settings.
  • A.3. Fourier Transform in Transformers: FEDformer is presented as the first time-series forecasting method using low-rank approximated attention transformations in the frequency domain.Its theoretical and architectural development combines frequency-domain approximation with Transformer attention.
  • B. Low-rank Approximation of Attention: Sparse or compressible signals can be recovered from fewer measurements, motivating projection of low-rank attention matrices into subspaces where they become sparse.Selecting an appropriate projection basis remains an open question addressed through RIP-based constructions.
  • B.1. RIP Matrices: RIP matrices preserve norms of K-sparse vectors within δ-dependent bounds, and Gaussian, Bernoulli, and Fourier bases satisfy RIP with probability p ≈1 −e−n.The paper uses the Fourier basis as an example for low-rank approximation in attention mechanisms.

B.2. Low-rank Approximation with Fourier Basis/Legendre Polynomials

FEDformer uses randomly selected Fourier basis/Legendre Polynomials as an RIP matrix for low-rank attention approximation. This reduces computation while maintaining bounded approximation error, including with softmax activation.

  • Low-rank Approximation with Fourier Basis/Legendre Polynomials: Fourier basis/Legendre Polynomials form an RIP matrix that supports low-rank approximation of the attention mechanism.The analysis states that randomly selected Fourier bases provide a theoretical error bound for attention approximation.
  • Low-rank Approximation with Fourier Basis/Legendre Polynomials: The theoretical guarantees rely on RIP-based inequalities that hold with high probability for the selected Fourier basis/Legendre Polynomials.The passages specify probabilities approximately 1 − e^−n and 1 − 4e^−n for the relevant inequalities.
  • Low-rank Approximation with Fourier Basis/Legendre Polynomials: O(NMd) replaces O(N^2d) computation when Fourier basis/Legendre Polynomials are inserted between the attention matrix and values.Here, N is sequence length, M is the number of selected basis elements, and d is the hidden dimension; the approximation error remains bounded.
  • Low-rank Approximation with Fourier Basis/Legendre Polynomials: The bounded low-rank approximation error still holds when the attention mechanism includes softmax activation.The result follows using the Cauchy inequality and the Lipschitz continuity of the exponential function on a compact region.

C. Fourier Component Selection … D.5. Multiwavelets

The paper selects a random subset of Fourier components under a coherence condition and introduces wavelet foundations progressing from continuous and discrete transforms to Legendre-based multiwavelets. These constructions provide basis functions, multiscale representations, and polynomial-subspace projections for the proposed framework.

  • C. Fourier Component Selection: The method uniformly samples s<d Fourier components from each series, forming a reduced representation from the full Fourier-component matrix.Each time series is transformed into a d-dimensional Fourier vector, and the vectors are assembled into A.
  • C. Fourier Component Selection: Under a mild coherence condition, the randomly selected Fourier basis preserves most information in A with high probability.The theorem assumes µ(A)=Ω(k/n), with a sufficient sample size stated as s=O(k^2/ε^2×µ(A)n/k).
  • D. Wavelets: Wavelet transforms serve as technical background for the proposed framework by decomposing functions into scaled and translated basis functions.The continuous wavelet transform introduces scale and translation as new dimensions, while wavelets derive from a mother wavelet through scaling and translation.
  • D.2. Discrete Wavelet Transform: Continuous wavelet transforms map one-dimensional signals to redundant two-dimensional time-scale representations, motivating discrete wavelet transforms.DWT samples scale and translation at discrete intervals, commonly using s0=2 for dyadic frequency sampling and τ0=1 for translation.
  • D.3. Orthogonal Polynomials: Orthogonal polynomials provide candidate mother wavelets subject to admissibility, regularity, and vanishing-moment properties.The framework focuses on polynomials that are nonzero over a finite domain and nearly zero elsewhere, using Legendre polynomials in the reported work.
  • D.4. Legendre Polynomails: Legendre polynomials are defined on [-1,1] with the uniform weight wL(x)=1 and can be extended to any interval [a,b] by shifting and scaling.Their stated orthogonality relation distinguishes equal and unequal polynomial indices.
  • D.5. Multiwavelets: The proposed multiwavelets combine wavelet and orthogonal-polynomial advantages by projecting functions onto subspaces of degree-restricted polynomials.The work restricts exploration to the Legendre-polynomial family rather than a single wavelet function.
  • D.5. Multiwavelets: Multiwavelet bases are constructed as orthonormal functions under a measure, with Legendre-based filter coefficients derived using Gaussian quadrature and Gram-Schmidt orthogonalization.For k=3, the stated formula yields an example set of filter coefficients.

E. Output Distribution Analysis · E.1. Bad Case Analysis · E.2. Kolmogorov-Smirnov Test

The analysis examines distributional failures in vanilla Transformer forecasts and introduces the Kolmogorov-Smirnov test to compare forecast and ground-truth samples. It attributes forecasting shifts to point-wise generation under MSE-based learning and characterizes KS as a nonparametric empirical-distribution comparison.

  • E.1. Bad Case Analysis: Vanilla Transformer exhibits two bad long-term forecasting cases on the real-world ETTm1 dataset.The cases are presented using vanilla Transformer as the baseline model.
  • E.1. Bad Case Analysis: The two cases show different distributions between ground truth and vanilla Transformer outputs, involving frequency-mode and trend shifts.Figure 7 presents frequency mode and trend shift on the left, and trend shift on the right.
  • E.1. Bad Case Analysis: Forecasting shifts are particularly related to vanilla Transformer’s point-wise generation mechanism.Unlike ARIMA’s predefined output-distribution bias structure, Transformer forecasts each point independently.
  • E.1. Bad Case Analysis: Forecasting each point independently using only overall MSE loss can produce different distributions between ground truth and forecasting output.The passage contrasts this mechanism with classic models such as ARIMA, which use a predefined data-bias structure for output distribution.
  • E.2. Kolmogorov-Smirnov Test: The Kolmogorov-Smirnov test checks whether two data samples come from the same unknown distribution.It is described as a nonparametric test for equality of continuous or discontinuous two-dimensional probability distributions.
  • E.2. Kolmogorov-Smirnov Test: The KS test quantifies the distance between the empirical distribution functions of two samples.Its interpretation is the probability that the two sample sets were drawn from the same unknown probability distribution.
  • E.2. Kolmogorov-Smirnov Test: For large samples, the KS null hypothesis is evaluated for rejection at significance level α using the empirical-distribution comparison.The empirical distribution functions are denoted F1,n and F2,m; n and m are the respective sample sizes.

E.3. Distribution Experiments and Analysis · F. Supplemental Experiments

The distribution analysis uses the Kolmogorov–Smirnov test to compare forecast and input distributions, showing that FEDformer most consistently preserves the input distribution. The results attribute this behavior to seasonal-trend decomposition and output-trend control.

  • E.3. Distribution Experiments and Analysis: The KS test measures the global distributional similarity between input and forecast sequences, with a larger P-value indicating weaker rejection of the same-distribution null hypothesis.The test omits temporal information but evaluates the global property of the forecast output relative to the input.
  • E.3. Distribution Experiments and Analysis: The experiments compare fixed 96-step input distributions with outputs from 96–720-step prediction tasks on ETTm1 and ETTm2.A 0.01 P-value threshold is used for the comparison.
  • E.3. Distribution Experiments and Analysis: Existing Transformer baselines generally have P-values below 0.01, whereas Autoformer is the main exception.This indicates that most baselines are more likely to be sampled from a different distribution than the input.
  • E.3. Distribution Experiments and Analysis: Autoformer and FEDformer obtain much larger P-values than other models, mainly because of their seasonal-trend decomposition mechanism.The two models achieve close results on ETTm1, but FEDformer has much larger P-values there.
  • E.3. Distribution Experiments and Analysis: FEDformer is the only model whose null hypothesis cannot be rejected with P-value larger than 0.01 in every case across ETTm1 and ETTm2.This suggests that FEDformer’s outputs have distributions more similar to the inputs.
  • E.3. Distribution Experiments and Analysis: On ETTm1, the true output has a smaller P-value than FEDformer’s prediction, indicating that distributional closeness results from model control rather than solely higher prediction accuracy.The architecture constrains the output distribution’s trend, or mean.

F.1. Dataset Details · F.2. Implementation Details

The experiments use multiple benchmark datasets spanning transformer loads, electricity consumption, exchange rates, and traffic. Training uses ADAM with fixed optimization settings, early stopping, MSE and MAE metrics, and five repeated runs.

  • F.1. Dataset Details: ETT contains ETT1 and ETT2 sub-datasets collected from two electricity transformers at two stations.Each sub-dataset has 15min and 1h versions and includes multiple load series plus one oil-temperature series.
  • F.1. Dataset Details: Electricity1 records client electricity consumption, with each column corresponding to one client.
  • F.1. Dataset Details: Exchange contains current exchange data from 8 countries.
  • F.1. Dataset Details: Traffic2 is included among the experiment datasets, representing traffic occupation-rate data.The supplied passage truncates the description after “occupation rate of”.
  • F.2. Implementation Details: Training uses ADAM with learning rate 1e−4 and batch size 32.
  • F.2. Implementation Details: Early stopping terminates training after three epochs without validation-loss degradation, while MSE and MAE serve as evaluation metrics.
  • F.2. Implementation Details: All experiments are repeated 5 times, and final metrics are averaged across runs.The deep learning networks are implemented in PyTorch.

F.3. ETT Full Benchmark … F.8. When Fourier/Wavelet model performs better

Across the ETT benchmarks and targeted analyses, FEDformer improves forecasting accuracy, uses frequency-enhanced attention and mixture-of-experts decomposition, remains stable across runs, and links model choices to series complexity. The results indicate that Fourier-based models suit less complex or univariate series, whereas wavelet-based models better handle complex or multivariate series.

  • F.3. ETT Full Benchmark: 11.5% relative MSE reduction for multivariate forecasting and 9.4% reduction for univariate forecasting are achieved over Autoformer on the ETT full benchmark.ETTh1 and ETTh2 are hourly, while ETTm1 and ETTm2 are recorded every 15 minutes.
  • F.4. Cross Attention Visualization: Tanh and softmax are tested as activation functions for the frequency-enhanced cross-attention matrix, with tanh used by default.Different attention patterns are visualized for FEDformer-f trained on ETTm2.
  • F.5. Improvements of Mixture of Experts Decomposition: The mixture-of-experts decomposition extracts trends with multiple average-pooling layers and combines them using data-dependent weights.Compared with a single fixed-kernel average-pooling baseline, the designed mixture improves performance in multivariate forecasting.
  • F.6. Multiple random runs: Small performance variance is observed for FEDformer-f across five runs despite randomness in frequency selection.Table 11 reports both mean and standard deviation for FEDformer-f and Autoformer.
  • F.7. Sensitivity to the number of modes: ETTx1 vs ETTx2: Higher-complexity ETTx1 requires more frequency modes than ETTx2, whose complexity is lower according to permutation and SVD entropy.The analysis links the number of modes to the complexity of the time series.
  • F.8. When Fourier/Wavelet model performs better: Fourier-based models are usually better for less complex series, while wavelet-based models are more suitable for complex series.Wavelet models are more effective on multivariate series, whereas Fourier models normally perform better on univariate series; multivariate series have higher complexity measures.
Loading 2201.12740v3…