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:
- Legendre Polynomials: Ideal for smooth, global relationships.
- Fourier Series: The standard choice for periodic data.
- Walsh Functions: Pulse-like functions suitable for digital logic patterns.
- Haar Wavelets: "Local" bases that focus on specific regions of the data space.
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.
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