Fast Computing for Distance Covariance

By Xiaoming Huo, G'abor J. Sz'ekely. 2014

152 citations recorded by the source corpus.

Distance covariance and distance correlation have been widely adopted in measuring dependence of a pair of random variables or random vectors. If the computation of distance covariance and distance correlation is implemented directly accordingly to its definition then its computational complexity is O(n2), which is a disadvantage compared to other faster methods. In this article we show that the computation of distance covariance and distance correlation of real-valued random variables can be implemented by an O(nlog n) algorithm and this is comparable to other computationally efficient algorithms. The new formula we derive for an unbiased estimator for squared distance covariance turns out to be a U-statistic. This fact implies some nice asymptotic properties that were derived before via more complex methods. We apply the fast computing algorithm to some synthetic data. Our work will make distance correlation applicable to a much wider class of problems. A supplementary file to this article, available online, includes a Matlab and C-based software that realizes the proposed algorithm.

Subfields: Artificial Intelligence, 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 Artificial Intelligence

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.”
Multivariate Rank-Based Distribution-Free Nonparametric Testing Using Measure Transportation (2019, background): “Moreover, note that, given the ranks, RdCovn can be computed in O(n(d1 + d2)) steps (see [74]).”
A fast algorithm for computing distance correlation (2018, methodology): “Our algorithm diﬀers from Huo and Sz´ekely (2016) in the following ways: First, they implicitly assume that there are no ties in the data (see Algorithm 1 and proof in Huo and Sz´ekely (2016)), whereas our proposed method is valid for any pair of real-valued univariate variables.”
High-dimensional consistent independence testing with maxima of rank correlations (2018, methodology): “Finally, the algorithm of Huo and Székely (2016) computes the distance covariance statistic in O(n log n) time.”
A Projection-based Conditional Dependence Measure with Applications to High-dimensional Undirected Graphical Models. (2015, methodology): “Other related works include Hoeffding (1948), Blomqvist (1950), Blum et al. (1961), and some methods described in Hollander et al. (2013) and Anderson (1962).”
Distribution-Free Consistent Independence Tests via Center-Outward Ranks and Signs (2019, methodology): “After obtaining [F(n)X,±(Xi)]ni=1 and [F(n)Y ,±(Y i)]ni=1, the test statistic M̂n in (10) can be computed using Equation (3.3) in Huo and Székely (2016) in O(n2) time.”
A Modified CRITIC Method to Estimate the Objective Weights of Decision Criteria (2021, background): “Huo and Székely [72] claimed that the computational complexity of distance correlation could be as high as a constant multiplied by m2 (i.e., O ∗m2), where m denotes the number of alternatives.”
A Statistically and Numerically Efficient Independence Test Based on Random Projections and Distance Covariance (2017, methodology): “It has been showed in ([8], Theorem 3.”
An Updated Literature Review of Distance Correlation and Its Applications to Time Series (2017, unknown): “…the properties of V U ( X , Y ) , we refer to the paper by Huang and Huo (2017). b By using the U-statistic representation of V U ( X, Y ) , Huo and Sz´ekely (2016) show that it can be computed by an O ( n log n ) algorithm. b This algorithm considerably speeds up the calculation of the…”