A fast algorithm for computing distance correlation
By Arin Chaudhuri, Wenhao Hu. 2018
75 citations recorded by the source corpus.
Abstract 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. proposed distance covariance and its derived correlation. The distance covariance is a weighted L 2 distance between the joint characteristic function and the product of marginal distributions; it is 0 if and only if two random vectors X and Y are independent. This measure can 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 ( n 2 ) cost, where n is the sample size. Quadratic computing time greatly limits the use of the distance covariance for large data. To calculate the sample distance covariance between two univariate random variables, a simple, exact O ( n log ( n ) ) algorithms is developed. The proposed algorithm 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.
Subfields: Finance, Statistics and Probability
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Finance
In Statistics and Probability
Citations in the corpus
- NoPeek: Information leakage reduction to share activations in distributed deep learning (2020, background): “Fast estimators of distance correlation require O(nlogn) [55, 56] computational complexity for univariate and O(nKlogn) complexity [57] for multivariate settings with O(max(n,K)) memory requirement, where K is the number of random projections.”
- A Modified CRITIC Method to Estimate the Objective Weights of Decision Criteria (2021, unknown): “teria and not the nonlinear relationship [45,46].”