A Statistically and Numerically Efficient Independence Test Based on Random Projections and Distance Covariance

By Cheng Huang, Xiaoming Huo. 2017

36 citations recorded by the source corpus.

Testing for independence plays a fundamental role in many statistical techniques. Among the nonparametric approaches, the distance-based methods (such as the distance correlation-based hypotheses testing for independence) have many advantages, compared with many other alternatives. A known limitation of the distance-based method is that its computational complexity can be high. In general, when the sample size is n, the order of computational complexity of a distance-based method, which typically requires computing of all pairwise distances, can be O(n 2). Recent advances have discovered that in the univariate cases, a fast method with O(n log n) computational complexity and O(n) memory requirement exists. In this paper, we introduce a test of independence method based on random projection and distance correlation, which achieves nearly the same power as the state-of-the-art distance-based approach, works in the multivariate cases, and enjoys the O(nK log n) computational complexity and O( max{n, K}) memory requirement, where K is the number of random projections. Note that saving is achieved when K < n/ log n. We name our method a Randomly Projected Distance Covariance (RPDC). The statistical theoretical analysis takes advantage of some techniques on the random projection which are rooted in contemporary machine learning. Numerical experiments demonstrate the efficiency of the proposed method, relative to numerous competitors.

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

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 fast algorithm for computing distance correlation (2018, methodology): “For multivariate random variables, random projection approach can be adopted (Huang and Huo, 2017), which depends on calculation of distance covariance for univariate variables.”