PaperlayerView exact revision on arXiv

Source-linked AI summary

From Fourier to Koopman: Spectral Methods for Long-term Time Series Prediction

Henning Lange, Steven L. Brunton, Nathan Kutz

arXiv:2004.00574v1cs.LGeess.SPstat.ML

TL;DR

Stable long-term forecasting remains challenging, particularly when recursively fed one-step predictions accumulate error. The paper develops spectral methods for linear and nonlinear quasi-periodic signals, and reports stable long-term forecasting when the required properties hold.

  • Problem

    Generic methods for stable long-term forecasts are lacking, while recursive one-step predictions compound errors over time.

    Source: §1 · p. 1

  • Method

    The paper fits spectral forecasting models in a data-dependent basis, extending the linear approach to nonlinear systems through Koopman theory.

    Source: §1 · p. 2

  • Results

    Stable long-term forecasting is empirically achieved when the time series fulfills the required properties.

    Source: §1 · p. 3

  • Takeaways & Limitations

    The algorithms are designed to mitigate compounding errors and provide practical error bounds and uncertainty metrics.

    Source: §1 · p. 2, §6 · p. 29

    The algorithms will not work well for data from systems that are not quasi-periodic.

    Source: §6.1 · p. 30

Abstract

from arXiv · show

We propose spectral methods for long-term forecasting of temporal signals stemming from linear and nonlinear quasi-periodic dynamical systems. For linear signals, we introduce an algorithm with similarities to the Fourier transform but which does not rely on periodicity assumptions, allowing for forecasting given potentially arbitrary sampling intervals. We then extend this algorithm to handle nonlinearities by leveraging Koopman theory. The resulting algorithm performs a spectral decomposition in a nonlinear, data-dependent basis. The optimization objective for both algorithms is highly non-convex. However, expressing the objective in the frequency domain allows us to compute global optima of the error surface in a scalable and efficient manner, partially by exploiting the computational properties of the Fast Fourier Transform. Because of their close relation to Bayesian Spectral Analysis, uncertainty quantification metrics are a natural byproduct of the spectral forecasting methods. We extensively benchmark these algorithms against other leading forecasting methods on a range of synthetic experiments as well as in the context of real-world power systems and fluid flows.

1. Introduction

The paper targets stable long-term forecasting without recursive error accumulation, using spectral methods that combine signal processing and Koopman theory. Its scope is quasi-periodic systems with finite-dimensional Koopman operators, for which stable long-term forecasting is shown empirically.

1. Introduction

  • Recursive one-step forecasting compounds errors over time, while the paper seeks long-term methods that mitigate this problem without requiring knowledge of the dynamics.Forecasting is also motivated by the importance of prediction accuracy and uncertainty quantification across science, engineering, and control.Source: §1 · pp. 1–2
  • The paper combines operator theory, signal processing, and machine learning to derive long-term forecasting algorithms and practical error bounds and uncertainty metrics.The algorithms are described as generic and, under some conditions, optimal.Source: §1 · p. 2
  • From a signal-processing perspective, the method decomposes data in a data-learned nonlinear oscillatory basis that is optimal in the least-squares sense.A symmetry relationship lets the method use the Fast Fourier Transform to compute model parameters efficiently and scalably, drawing on Bayesian Spectral Analysis.Source: §1 · p. 2
  • Koopman theory lifts nonlinear dynamics into a space where time evolution is linear, analogous to how nonlinear transformations can make data linearly separable.The paper restricts its investigation to systems with finite-dimensional Koopman operators that preserve energy or persist over long times.Source: §1 · pp. 2–3
  • A discrete Fourier transform can fit any finite sequence of equidistant samples with enough Fourier modes, but its implicit periodicity assumption prevents generalization in the trivial construction.The paper aims to break that periodicity assumption.Source: §1 · pp. 2–3
  • When the required time-series properties hold, the authors report empirically that stable long-term forecasting can be accomplished.The stated scope is quasi-periodic systems with finite-dimensional Koopman operators.Source: §1 · p. 3

2. Fourier and Forecasting

This section develops a frequency-parameterized linear oscillator fit for quasi-periodic signals, then uses FFT-based search and gradient refinement to address its non-convex objective and the FFT’s periodicity assumptions.

2. Fourier and Forecasting

  • The linear model assumes imaginary eigenvalues and represents the measured signal through oscillator frequencies and amplitudes.The method fits a linear mapping from the measured signal to a linear dynamical system under this quasi-periodic assumption.Source: §2 · pp. 4–5
  • Coordinate descent optimizes frequencies one at a time, using the residual’s Fourier coefficients to evaluate each frequency’s error surface and locate its minimum.The squared-error surface has a symmetry with the Fourier transform of the residual; the FFT locates the global-optimum valley at 1/T precision.Source: §2 · pp. 6, 8, Figure 2 · p. 8

2.1 Breaking periodicity

  • The FFT supplies an initial valley under periodicity assumptions, then gradient descent refines the frequencies and breaks those assumptions.The FFT and gradient descent counterbalance one another: the former provides a global search and the latter a local refinement.Source: §2 · p. 4, Figure 3 · p. 8, §2.1 · p. 9

2.2 Connection to Spectral Leakage and Bayesian Spectral Analysis

  • Finite-window sampling makes quasi-periodic signals’ FFT spectra sinc-shaped, while sequential frequency selection explains away whole leakage patterns.As the observation length T increases, the sinc peak narrows and grows, improving frequency precision.Source: §2.2 · p. 10, Figure 4 · p. 11

2.3 Related Work

  • The method resembles DMD’s linear-system fitting step but uses FFT-based frequency estimates instead of a pseudoinverse.DMD typically estimates a matrix A, whereas this algorithm estimates a vector of frequencies.Source: §2.3 · p. 11
  • Under zero-mean, temporally uncorrelated measurement noise, the frequency estimator is unbiased; stationarity remains an inductive bias, and the method permits m frequencies for n-dimensional signals when m > n.The passage contrasts this capacity with original DMD, whose signal dimensionality limits the number of extractable frequencies.Source: §2.3 · p. 12

3. Koopman and Forecasting

The section develops a data-dependent nonlinear oscillatory basis through Koopman theory and uses frequency-domain structure to optimize its frequencies efficiently. It also discusses the unknown-phase problem and contrasts the method with existing Koopman approaches.

3. Koopman and Forecasting

  • The nonlinear basis is signal-dependent, and the section argues that invertible Koopman observables with a function approximation can rule out systems such as x_t = cos(t), whose repeated states have different next values.The proposed interpretation instead approximates the inverse observable with a function, representing signals as nonlinear functions of sines and cosines while preserving their periods.Source: §3 · pp. 13–14, §3.1 · p. 14

3.1 Nonlinear Frequency Decomposition

  • The method jointly learns a nonlinear oscillatory basis and least-squares fit from data, retaining frequency and periodicity while using the FFT to optimize frequencies efficiently.A computationally efficient frequency spectrum gives an initial frequency estimate, which is then refined with gradient descent.Source: §3 · p. 13, §3.1 · p. 16
  • Because each time-local loss repeats within a 2π span, the algorithm samples one period and combines repeated losses using zero-stuffing and zero-padding in O(T log T) rather than O(T^2).The local losses can be computed in parallel.Source: §3.1 · pp. 15–16

3.2 Unknown phase problem

  • With an untrained neural network, daily, weekly, and seasonal frequencies remain detectable as deviations from the error plateau, including upward spikes; training or restarting can often alleviate this unknown-phase problem.The error surface is shown for a signal with daily, weekly, and seasonal patterns.Source: §3.2 · p. 17, Figure 7 · p. 17

3.3 Related Work

  • Unlike approaches that optimize approximate or local latent linearity and may face unstable eigenvalues, this method imposes global linearity and stability as constraints and addresses a highly non-convex objective in the frequency domain.The related-work discussion notes that prior approaches often use gradient descent and may add Lyapunov regularization for stability.Source: §3.3 · p. 18

4. Algorithmic properties

The section examines approximation and error properties of the algorithms. It distinguishes finite-data fitting from infinite-signal expressiveness and describes how error depends on data amount, noise, and prediction horizon.

4.1.1 Finite data

  • For finite equidistant data, the Fourier-based algorithm can fit any dataset using finite parameters, but this trivial solution assumes periodicity and does not generalize.The construction uses an N-dimensional space, analogous to the trivial finite-data solution of Cover’s theorem.Source: §4.1.1 · p. 18

4.1.2 Infinite data

  • For infinite signals, the Koopman-based algorithm can represent a square wave with finite parameters, whereas its Fourier counterpart requires infinite model size.The passage notes that the square wave has a linearly decaying but infinite Fourier spectrum and can be modeled by a simple nonlinear function with one frequency.Source: §4.1.2 · p. 19

4.2 Error bounds

  • The derived error bound indicates that the algorithm scales super-linearly with data and degrades linearly with noise variance and prediction horizon t.The bound is developed under a scalar-valued, Lipschitz-continuous function assumption.Source: §4.2 · pp. 19–20

5. Experiments

The experiments benchmark the forecasting algorithms on synthetic oscillators and traveling waves, real energy demand and fluid flows, and a process-noise setting. Results favor Koopman over Fourier on the tested nonlinear signals, while the fluid-flow comparison favors Fourier over DMD variants on three of four tasks.

5.1.1 Forecasting nonlinear oscillators under measurement noise

  • In the synthetic training-data experiment, Koopman outperforms Fourier, and the algorithms' performance scales super-linearly with the amount of data.Noise variance is fixed at 0.2; the models receive 2,000, 4,000, 6,000, or 8,000 samples and predict the next 104 snapshots.Source: §5.1.1 · p. 21, Figure 8 · p. 21
  • On noisy nonlinear oscillators, LSTMs capture waveform shape but miss frequency, while Fourier can miss small, low-SNR modes that drift out of phase.The authors attribute the smaller modes' detection difficulty to their lower signal-to-noise ratio.Source: §5.1.1 · p. 22
  • With training data fixed at T = 4000, performance degrades linearly with noise variance, and the Koopman algorithm outperforms Fourier.Figure 10 also reports that Koopman significantly outperforms Fourier and LSTMs.Source: §5.1.1 · p. 22, Figure 10 · p. 23

5.1.2 Traveling waves

  • For a traveling wave, Fourier with PCA reaches approximately 6% error using 55 modes and frequencies, while Koopman with a transpose-convolutional decoder gets below 1% with one frequency.The Fourier comparison is the best of 100 tested mode-frequency combinations.Source: §5.1.2 · p. 24

5.2.1 Energy demand: RE-Europe data set

  • For RE-Europe energy demand, time-stepping methods miss slow frequencies and can produce frequency-biased forecasts; an out-of-phase oscillation can score worse under MSE than a constant prediction.The frequency comparison includes yearly, weekly, daily, and 12-hour periods.Source: §5.2.1 · pp. 26–27

5.2.2 Fluid flows and Video Frame Prediction

  • On PCA-space forecasts of oscillator flows, Fourier significantly outperforms DMD and FB-DMD on three of four tasks; a nonoscillatory, increasing video PCA mode is the exception.The experiments focus on oscillator flows and use a temporal 75/25 training/test split.Source: §5.2.2 · p. 27

5.3 Process noise and phase drifts

  • A phase-corrected modification of Fourier models process noise in accelerometer recordings of human gait, showing that small algorithm changes can accommodate phase drift.The test uses mobile-phone accelerometer readings from a phone in a subject's right pocket.Source: §5.3 · pp. 27–28

6. Conclusion

The conclusion presents frequency-domain optimization for fitting linear and nonlinear oscillators, with global objectives supporting long-term forecasts that mitigate compounding errors. Its advantages are bounded by a strong quasi-periodic-system bias and by trade-offs in conditional independence.

6. Conclusion

  • Global objectives solved efficiently in the frequency domain enable long-term forecasting while mitigating compounding errors.The approach uses the Fast Fourier Transform to find scalable solutions to the non-convex fitting problems.Source: §6 · pp. 28–29

6.1 Disadvantages

  • The algorithms are poorly suited to non-quasi-periodic data, although the authors report that fluid flows, space weather, and energy consumption seem to meet the quasi-periodic assumption.Source: §6.1 · p. 30
  • For nonlinear models, parameter solutions are usually unobtainable, so swings away from the error plateau can indicate a correct frequency.Source: §6.1 · p. 30
  • Conditional independence can make one-step forecasts hard to correct using a newly known true value, and a large error at one step may carry into the next.Source: §6.1 · p. 30

6.2 Advantages

  • For quasi-periodic systems, the algorithms offer a tight fit and guarantee quasi-periodic predictions, avoiding potential failures such as predictions diverging to infinity.Source: §6.2 · p. 30
  • Once model parameters are known, future predictions need no past values or time-stepping, which is especially useful for high-dimensional data.Source: §6.2 · p. 30
  • Errors do not compound under the global criterion and conditional independence, though noise-related uncertainty still makes errors accumulate linearly over time.Source: §6.2 · p. 30
  • The authors report strong noise resilience, relating it to Bayesian Spectral Analysis, whose frequency estimates can exceed the precision suggested by Nyquist’s theorem.The Nyquist comparison is presented as an anecdote about Jaynes’s work.Source: §6.2 · p. 30

7. Future Work

The future-work discussion proposes combining local and global models, extending the methods to driven systems, and improving fluid-flow interpretability. It also suggests Bayesian marginalization over frequencies for probabilistic forecasting.

Input/output systems

  • The current algorithms assume autonomous systems, limiting broader use; the authors suggest that extensions of Koopman theory and DMD to forced systems could inform future approaches.Source: §7 · p. 31

Interpretable flows

  • For fluid flows, a Koopman model with a rotation-capable nonlinear decoder could reduce the number of frequencies and potentially improve noise robustness and interpretability.The discussed cavity-flow forecasts currently use PCA for dimensionality reduction and the Fourier-based algorithm.Source: §7 · p. 31

Non-parametric Fourier/Koopman

  • A Bayesian probabilistic model could marginalize over frequencies when forecasting, using Bayesian Spectral Analysis to calculate their posterior distribution given the observed data.Source: §7 · p. 31

Local and global modeling

  • A local model could capture an anomalous current year while a global model contributes more at longer horizons, motivating future work on how to weight them.Source: §7 · p. 31

Related papers

Loading 2004.00574v1…