nufftcf: Fast Auto- and Cross-Correlation Function Estimation for Irregularly-Sampled Time Series via the Non-Uniform FFT
Abstract
Estimating the auto-correlation function (ACF) and cross-correlation function (CCF) of sampled series is a standard task in many physics fields, including astronomy and environmental sciences. We present nufftcf, an ACF/CCF estimator designed primarily for irregularly sampled series, numerically consistent with established kernel-weighted definitions and scaling as O(nK) for K requested lags, rather than O(n^2). nufftcf was initially developed to evaluate the Wiener-Khinchin theorem for irregularly sampled data using the Non-Uniform Fast Fourier Transform (NUFFT), through the Flatiron Institute FINUFFT library, with Gaussian and rectangle kernels. An O(n)-per-lag two-pointer scan replaces the naive O(n^2) computation of the effective pair count used to normalize each lag bin. This enabled real-space estimators using the same kernels, providing exact reference implementations with the same O(nK) complexity and, in some cases, lower cost than the NUFFT path. The library also provides dedicated classical-FFT estimators for regularly sampled data. All estimators share a common calling convention. Using synthetic time series, we validate nufftcf for ACF against pastas, a library used in groundwater time-series analysis, and for CCF against pyZDCF, used in astronomical time-series analysis. Benchmarks confirm O(nK) scaling for the NUFFT and real-space nufftcf estimators, compared with O(n^2) for the pastas slotting technique. nufftcf is already advantageous at moderate series lengths because of its low millisecond-scale overhead. For regularly sampled data, the FFT path further reduces computational cost. We also demonstrate nufftcf on a simulated ground-based stellar light curve combining quasi-periodic rotation, correlated flicker noise, seasonal sampling gaps, and heteroscedastic measurement errors. Notebooks and scripts are provided to reproduce the examples and explore other use cases.
Related
- νGundam: A unified framework for point-redshift and probability-density-function-aware spatial correlation functions
- Basis function expansions of the two-point correlation function and reconstruction of the cosmological distance scale
- TEMPEST - A modular Python-based thermophysical model for rough, irregularly-shaped airless bodies
- Testing the 4-Point Correlation Function as a Probe of Parity Violation with the Quijote-Odd Simulations
- A Two-Dimensional Test of Cosmological Parity Violation with the 3-Point Correlation Function
BibTeX
@misc{campagne2026nufftcf,
title = {{nufftcf: Fast Auto- and Cross-Correlation Function Estimation for Irregularly-Sampled Time Series via the Non-Uniform FFT}},
author = {Jean-Eric Campagne},
howpublished = {HAL},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.03866},
eprint = {2609.03866},
archivePrefix = {arXiv},
url = {https://hal.science/hal-05740618v1},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - nufftcf: Fast Auto- and Cross-Correlation Function Estimation for Irregularly-Sampled Time Series via the Non-Uniform FFT
AU - Jean-Eric Campagne
PY - 2026
DA - 2026/09/07
PB - HAL
DO - 10.48550/arxiv.2609.03866
UR - https://hal.science/hal-05740618v1
AB - Estimating the auto-correlation function (ACF) and cross-correlation function (CCF) of sampled series is a standard task in many physics fields, including astronomy and environmental sciences. We present nufftcf, an ACF/CCF estimator designed primarily for irregularly sampled series, numerically consistent with established kernel-weighted definitions and scaling as O(nK) for K requested lags, rather than O(n^2). nufftcf was initially developed to evaluate the Wiener-Khinchin theorem for irregularly sampled data using the Non-Uniform Fast Fourier Transform (NUFFT), through the Flatiron Institute FINUFFT library, with Gaussian and rectangle kernels. An O(n)-per-lag two-pointer scan replaces the naive O(n^2) computation of the effective pair count used to normalize each lag bin. This enabled real-space estimators using the same kernels, providing exact reference implementations with the same O(nK) complexity and, in some cases, lower cost than the NUFFT path. The library also provides dedicated classical-FFT estimators for regularly sampled data. All estimators share a common calling convention. Using synthetic time series, we validate nufftcf for ACF against pastas, a library used in groundwater time-series analysis, and for CCF against pyZDCF, used in astronomical time-series analysis. Benchmarks confirm O(nK) scaling for the NUFFT and real-space nufftcf estimators, compared with O(n^2) for the pastas slotting technique. nufftcf is already advantageous at moderate series lengths because of its low millisecond-scale overhead. For regularly sampled data, the FFT path further reduces computational cost. We also demonstrate nufftcf on a simulated ground-based stellar light curve combining quasi-periodic rotation, correlated flicker noise, seasonal sampling gaps, and heteroscedastic measurement errors. Notebooks and scripts are provided to reproduce the examples and explore other use cases.
ER -