Efficient Computation of $N$-point Correlation Functions in $D$ Dimensions

Abstract

We present efficient algorithms for computing the $N$-point correlation functions (NPCFs) of random fields in arbitrary $D$-dimensional homogeneous and isotropic spaces. Such statistics appear throughout the physical sciences, and provide a natural tool to describe stochastic processes. algorithms for computing the NPCF components have $\mathcal{O}(n^N)$ complexity (for a data set containing $n$ particles); their application is thus computationally infeasible unless $N$ is small. By projecting the statistic onto a suitably-defined angular basis, we show that the estimators can be written in a separable form, with complexity $\mathcal{O}(n^2)$, or $\mathcal{O}(n_{\mathrm{g}}\log n_{\mathrm{g}})$ if evaluated using a Fast Fourier Transform on a grid of size $n_{\mathrm{g}}$. Our decomposition is built upon the $D$-dimensional hyperspherical harmonics; these form a complete basis on the $(D-1)$-sphere and are intrinsically related to angular momentum operators. Concatenation of $(N-1)$ such harmonics gives states of definite combined angular momentum, forming a natural separable basis for the NPCF. As $N$ and $D$ grow, the number of basis components quickly becomes large, providing a practical limitation to this (and all other) approaches: however, the dimensionality is greatly reduced in the presence of symmetries; for example, isotropic correlation functions require only states of zero combined angular momentum. We provide a \textsc{Julia} package implementing our estimators, and show how they can be applied to a variety of scenarios within cosmology and fluid dynamics. The efficiency of such estimators will allow higher-order correlators to become a standard tool in the analysis of random fields.

12 pages, 3 figures, accepted by PNAS. Code available at https://github.com/oliverphilcox/NPCFs.jl

References in corpus (5)

• Density Fluctuations in MHD Turbulence: Spectra, Intermittency and Topology
• Total Angular Momentum Waves for Scalar, Vector, and Tensor Fields
• Fast n-point correlation functions and three-point lensing application
• Graph Database Solution for Higher Order Spatial Statistics in the Era of Big Data
• Racah's method for general subalgebra chains: Coupling coefficients of SO(5) in canonical and physical bases

Cited by in corpus (8)

• Analytic Gaussian Covariance Matrices for Galaxy $N$-Point Correlation Functions
• A First Detection of the Connected 4-Point Correlation Function of Galaxies Using the BOSS CMASS Sample
• Optimal Estimation of the Binned Mask-Free Power Spectrum, Bispectrum, and Trispectrum on the Full Sky: Scalar Edition
• Breaking parity: the case of the trispectrum from chiral scalar-tensor theories of gravity
• Pair Counting without Binning -- A New Approach to Correlation Functions in Clustering Statistics
• Quantum speed limit for the OTOC from an open systems perspective
• An Optimal In-Situ Multipole Algorithm for the Isotropic Three-Point Correlation Functions
• nuGAN: Generative Adversarial Emulator for Cosmic Web with Neutrinos