Periodic Kernel Approximation by Index Set Fourier Series Features

Anthony Tompkins, Fabio RamosUAI 2019 · OpenReview

Abstract

Periodicity is a fundamental characteristic of many physical processes, from crystal lattices to robotic gaits, yet modeling it efficiently in high-dimensional Gaussian Processes (GPs) remains a challenge. Standard approximations like Random Fourier Features (RFFs) often require a prohibitive number of features to capture periodic signals accurately. This paper introduces Index Set Fourier Series Features (ISFSF), a deterministic approach that leverages sparse frequency grids to achieve high-accuracy periodic kernel approximation with significantly reduced computational overhead.

Introduction

Gaussian Processes are a cornerstone of non-parametric modeling, but their $O(N^3)$ scaling limits their application to large datasets. While periodic kernels exist, approximating them in multiple dimensions is difficult. Stochastic methods like RFFs suffer from high variance and may require thousands of features to represent complex periodicities. Conversely, deterministic Fourier expansions typically scale exponentially with input dimensions—the "curse of dimensionality." ISFSF addresses these issues by using structured index sets to select the most informative frequencies.

Methods

The core of ISFSF is the representation of periodic kernels through multivariate Fourier series. Instead of random sampling or full grids, the authors utilize "index sets" to define a sparse set of frequencies. A key contribution is the use of the Energy Norm Hyperbolic Cross (ENHC), which identifies the most significant frequency interactions while discarding redundant terms.

Visual comparison of a sparse hyperbolic cross index set (left) versus a full grid (right).

This deterministic construction ensures stability and avoids the "negative covariance" issues common in random approximations. Furthermore, the method is optimized by removing zero-frequency constant terms, ensuring every feature contributes to the model's predictive power. The authors also note that kernels with smaller lengthscales (more "wiggly" functions) are inherently harder to approximate, requiring higher-frequency components.

Results

The authors evaluated ISFSF across synthetic benchmarks, real-world textures, and high-dimensional robotics data. In texture modeling tasks (Pores, Rubber, and Tread), ISFSF demonstrated superior efficiency. For instance, using just 49 features, the method achieved performance comparable to RFFs using nearly 800 features.

Normalized error across different texture datasets, showing the superior convergence of the ENHC-based ISFSF method compared to alternatives.

In robotics experiments using the PyBullet simulator, specifically for the 16-dimensional "Ant" robot trajectory, ISFSF showed significantly faster convergence in predictive error. This suggests that ISFSF is particularly well-suited for real-time system identification and potentially for reinforcement learning loops where periodic gaits are common.

Conclusion

ISFSF provides a robust framework for high-dimensional periodic modeling. By moving from random to deterministic, sparse frequency selection, it makes large-scale periodic GPs computationally tractable. While currently designed for stationary kernels, future work may explore learning these index sets directly from data to handle non-stationary periodic processes and integrating ISFSF into active policy learning for robotics.

Summary updated

Abstract

Periodicity is often studied in timeseries modelling with autoregressive methods but is less popular in the kernel literature, particularly for multi-dimensional problems such as in textures, cryst...
BibTeX
@inproceedings{tompkins2019periodic,
  author = {Anthony Tompkins and Fabio Ramos},
  title = {{Periodic Kernel Approximation by Index Set Fourier Series Features}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {2019},
  url = {https://openreview.net/forum?id=SLJVWUsdFPV},
}
Figure