A Statistically and Numerically Efficient Independence Test Based on Random Projections and Distance Covariance
A Statistically and Numerically Efficient Independence Test Based on Random Projections and Distance Covariance
复制标题
DOI：
10.3389/fams.2021.779841
复制
发表时间：
2017-01
期刊：
影响因子：
--
通讯作者：
Cheng Huang;X. Huo
中科院分区：
文献类型：
--
作者：
Cheng Huang;X. Huo
独立性检验在许多统计技术中扮演着重要的角色。在非参数方法中，基于距离的方法(如基于距离相关性的假设独立性检验)与许多其他方法相比具有许多优点。基于距离的方法的一个已知限制是其计算复杂性可能很高。一般来说，当样本大小为n时，通常需要计算所有成对距离的基于距离的方法的计算复杂度的量级可以是O(N 2)。最近的进展发现，在单变量情况下，存在一个计算复杂度为O(Nlogn)、存储需求为O(N)的快速方法。本文介绍了一种基于随机投影和距离相关的独立性测试方法，该方法与目前最先进的基于距离的方法具有几乎相同的能力，适用于多变量情况，具有O(NKlogn)的计算复杂性和O(max{n，K})的存储需求，其中K是随机投影的个数。注意，当K<；n/logn时，实现了节省。我们将我们的方法命名为随机投影距离协方差(RPDC)。统计理论分析利用了植根于当代机器学习的一些关于随机投影的技术。数值实验证明了该方法相对于众多竞争者的有效性。
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.