# A fast algorithm for computing distance correlation

arXiv: https://arxiv.org/abs/1810.11332 · HTML: https://mlsanity.com/paper/1810.11332/

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 26 Oct 2018.

## Built on by (most cited first, 8 of 8)

- [Label Leakage and Protection from Forward Embedding in Vertical Federated Learning](https://mlsanity.com/paper/2203.01451/) (2022)
- [Defending against Reconstruction Attack in Vertical Federated Learning](https://mlsanity.com/paper/2107.09898/) (2021)
- [IoT Data Analytics in Dynamic Environments: From An Automated Machine Learning Perspective](https://mlsanity.com/paper/2209.08018/) (2022)
- [Early Detection of Ovarian Cancer by Wavelet Analysis of Protein Mass Spectra](https://mlsanity.com/paper/2207.07028/) (2022)
- [Private measurement of nonlinear correlations between data hosted across multiple parties](https://mlsanity.com/paper/2110.09670/) (2021)
- [Measuring Statistical Dependencies via Maximum Norm and Characteristic Functions](https://mlsanity.com/paper/2208.07934/) (2022)
- [TSLiNGAM: DirectLiNGAM under heavy tails](https://mlsanity.com/paper/2308.05422/) (2023)
- [Explaining Categorical Feature Interactions Using Graph Covariance and LLMs](https://mlsanity.com/paper/2501.14932/) (2025)

## Abstract (arXiv)

Classical dependence measures such as Pearson correlation, Spearman's ρ, and Kendall's τ can detect only monotonic or linear dependence. To overcome these limitations, Szekely et al.(2007) proposed distance covariance as a weighted L2 distance between the joint characteristic function and the product of marginal distributions. The distance covariance is 0 if and only if two random vectors X and Y are independent. This measure has the power to detect the presence of a dependence structure when the sample size is large enough. They further showed that the sample distance covariance can be calculated simply from modified Euclidean distances, which typically requires O(n2) cost. The quadratic computing time greatly limits the application of distance covariance to large data. In this paper, we present a simple exact O(nlog(n)) algorithm to calculate the sample distance covariance between two univariate random variables. The proposed method essentially consists of two sorting steps, so it is easy to implement. Empirical results show that the proposed algorithm is significantly faster than state-of-the-art methods. The algorithm's speed will enable researchers to explore complicated dependence structures in large datasets.