Basis Choices for Frequency Domain Statistical Independence Tests and Algorithms for Algebraic Relation Extraction

Juan Shi, Wenbo Wang, Wan Zhang, Han Bao, Sergio Chavez, Jingfang Huang, Yichao Wu, Kai ZhangarXiv 2025 · DOI · arXiv

Abstract

This paper investigates the use of frequency-domain transformations to detect non-linear dependencies between variables. By evaluating various orthonormal bases—including Legendre polynomials, Fourier series, and Haar wavelets—the authors demonstrate how spectral coefficients can reveal complex algebraic relations and localized dependencies that traditional correlation tests often overlook. The study introduces two primary testing algorithms, Max-FiT and SVD-FiT, and provides a roadmap for selecting the optimal basis based on the expected nature of the data relationship.

Introduction

Detecting whether two variables are independent is a fundamental challenge in statistics. While classical tools like Pearson’s correlation are effective for linear relationships, they often fail to identify non-linear dependencies, such as data points forming a circle or a checkerboard pattern. This research proposes a shift from the "physical domain" of raw data points to the "frequency domain" of spectral coefficients. By treating the joint probability density function of the data as a signal to be decomposed, the authors enable more robust detection of hidden relationships.

Methodology: From Data Points to Spectral Coefficients

The proposed framework transforms paired data $(x_n, y_n)$ into a matrix of frequency-domain coefficients. The choice of the "basis"—the fundamental mathematical shapes used for decomposition—is critical. The authors compare four main types of orthonormal bases:

  1. Legendre Polynomials: Ideal for smooth, global relationships.
  2. Fourier Series: The standard choice for periodic data.
  3. Walsh Functions: Pulse-like functions suitable for digital logic patterns.
  4. Haar Wavelets: "Local" bases that focus on specific regions of the data space.
A 2x2 checkerboard pattern representing a non-linear dependency that traditional linear correlation measures often fail to detect.

Two primary algorithms are introduced for independence testing:

  • Max-FiT (Maximal coefficient Frequency-domain independence Test): Identifies the single strongest signal within the coefficient matrix.
  • SVD-FiT (Singular Value Decomposition Test): Analyzes the "rank" of the coefficient matrix. In the case of independent variables, the matrix should ideally be Rank-1, turning a statistical problem into a linear algebra task.

The Importance of Basis Selection: Local vs. Global

A key finding of the study is that there is no universal "best" basis; rather, the choice involves a trade-off between statistical power and sensitivity to local features. While Legendre polynomials excel at identifying smooth, global trends, they are often "blind" to localized dependencies. Conversely, Haar wavelets are essential for catching dependencies that only exist within a small subset of the data.

A grid of 2D Haar wavelet basis functions, showing the diverse set of local and global patterns used to decompose joint probability densities for independence testing.

This distinction was highlighted in the analysis of NYC daily temperature alterations versus the Dow Jones Industrial Average (DJI). While global Fourier bases found no significant relationship (p-value 0.275), the "Nonstandard Haar" basis revealed a highly significant relationship (p-value 0.005) localized around extreme temperature swings.

Empirical Results and Relation Extraction

Beyond independence testing, the authors utilize Canonical Correlation Analysis (CCA) and SVD-based Low Dimensional Structure (LDS) extraction to reconstruct the underlying mathematical formulas governing dependencies. The algorithms successfully extracted complex shapes like circles and lemniscates from noisy synthetic data. Furthermore, by utilizing Non-uniform Fast Fourier Transforms (NuFFT) and Fast Haar Transforms (FHT), the researchers reduced computational complexity from $O(N^2)$ to $O(N \log N)$, making these spectral tests viable for large-scale datasets.

Conclusion and Future Work

The frequency-domain approach offers a powerful lens for uncovering non-linear and localized dependencies. Future research will focus on extending these methods to high-dimensional manifolds, improving robustness against extreme noise, and developing adaptive techniques that automatically select the optimal basis for a given dataset.

Summary updated

BibTeX
@misc{shi2025basis,
  author = {Juan Shi and Wenbo Wang and Wan Zhang and Han Bao and Sergio Chavez and Jingfang Huang and Yichao Wu and Kai Zhang},
  title = {{Basis Choices for Frequency Domain Statistical Independence Tests and Algorithms for Algebraic Relation Extraction}},
  year = {2025},
  eprint = {2512.01963},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2512.01963},
}
Figure