PaperlayerView exact revision on arXiv

Source-linked AI summary

Fast Computing for Distance Covariance

Xiaoming Huo, Gabor J. Szekely

arXiv:1410.1503v1stat.COstat.ME

TL;DR

The paper addresses the O(n^2) cost of directly computing distance covariance and distance correlation. It derives an O(n log n) algorithm for real-valued variables, establishes a U-statistic formulation for an unbiased squared distance-covariance estimator, and demonstrates the approach in simulations.

  • Problem

    Direct computation of distance covariance and distance correlation has O(n^2) complexity, creating a disadvantage compared with faster methods.

  • Method

    The paper derives an O(n log n) algorithm for computing distance covariance and distance correlation for real-valued random variables and develops an unbiased squared distance-covariance estimator.

  • Results

    The new unbiased estimator is a U-statistic, and simulations demonstrate the fast algorithm's effectiveness and increasing distance-correlation advantages as sample sizes grow.

  • Takeaways & Limitations

    The fast algorithm makes distance correlation applicable to a wider class of applications.

  • Takeaways & Limitations

    The paper refrains from further discussion of a potential research direction concerning feature screening.

Abstract

from arXiv · show

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($n^2$) which is a disadvantage compared to other faster methods. In this paper we show that the computation of distance covariance and distance correlation of real valued random variables can be implemented by an O(n log 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 applications.

1. INTRODUCTION

The paper addresses the O(n^2) complexity of direct distance-correlation computation by reformulating the statistic and developing an O(n log n) algorithm. Simulations show that the method enables larger samples and makes distance correlation’s comparative advantage more evident as sample size increases.

  • Direct implementation of distance correlation can require O(n^2) computation for sample size n.
  • The paper develops an O(n log(n)) algorithm for a version of distance correlation.
  • The derivation substantially reformulates the original distance-correlation formulation and extends an existing fast-algorithm idea for the paper’s purpose.
  • Simulations demonstrate the fast algorithm’s effectiveness and show distance correlation’s advantage over existing methods becomes more evident as sample sizes increase.
  • The proposed algorithm makes experiments with a sample size increased 100-fold from a previously published simulation study feasible.
  • The paper presents a reformulated distance-covariance estimator that is unbiased and a U-statistic, followed by an average-complexity O(n log n) algorithm.

2. A REVIEW OF DISTANCE COVARIANCE

This section reviews distance covariance as a dependence measure based on characteristic functions and centered pairwise distances. It motivates the paper’s computational contribution by noting that the usual sample calculation requires O(n^2) steps, while the real-valued case can be computed in O(n log n).

  • The distance-covariance framework is defined for random vectors with finite first moments and uses independent identically distributed copies in its population formulation.
  • Distance covariance measures the weighted L2 distance between the joint characteristic function and the product of the marginal characteristic functions.
  • The sample statistic uses pairwise distances, double-centered distance matrices, and their squared covariance and variance formulas.
  • Distance correlation standardizes sample distance covariance, while the population quantity is invariant to rigid motions and scale.
  • Distance covariance is zero if and only if the underlying random variables are independent.
  • Straightforward computation of sample distance covariance and correlation requires O(n^2) steps, but real-valued variables need no more than O(n log n).

3. THE UNBIASED VERSION OF THE SQUARED SAMPLE DISTANCE COVARIANCE: REFORMULATION AND RELATION TO U-STATISTICS

The paper reformulates the unbiased squared sample distance covariance as a U-statistic and establishes properties that support both asymptotic analysis and O(n log n) computation.

  • 3.1 Reformulation: The reformulation defines a U-centered matrix whose inner product provides an unbiased estimator of squared distance covariance.The construction uses Euclidean distance matrices for paired samples and an inner product based on their U-centered forms.
  • 3.1 Reformulation: Under E(|X| + |Y|) < 1 and n > 3, the proposed statistic is an unbiased estimator of squared population distance covariance V2(X, Y).
  • 3.2 Validating the Statistic is a U-Statistic: The estimator can be computed in O(n log n) steps, enabling efficient calculation alongside the U-statistic formulation.
  • 3.2 Validating the Statistic is a U-Statistic: The recursive relation is a necessary and sufficient condition for a statistic to be a U-statistic.The condition is expressed through statistics computed after removing individual observations and holds for all n ≥ r.
  • 3.2 Validating the Statistic is a U-Statistic: The estimator is a U-statistic, with its kernel given by the corresponding inner product.The result follows from recursive jackknife relations that characterize U-statistics.
  • 3.2 Validating the Statistic is a U-Statistic: Under independence, the U-statistic has a degenerate kernel and yields a limit distribution for n(eA · eB); under alternatives, n|(eA · eB)| →∞.These properties support construction of a consistent independence test when the relevant second moments are finite.

4. FAST ALGORITHM

For univariate X and Y, the paper develops an O(n log n) algorithm for the unbiased estimator of squared population distance covariance. The construction uses intermediate lemmas, partial sums, sorting, and tree-based methods, with detailed algorithms provided in the appendix.

  • Main result: Univariate distance covariance can be computed with an O(n log n) algorithm.The paper presents this result through a sequence of intermediate lemmas and a main theorem.
  • Computational ingredients: The algorithm uses a modification and extension of fast methods for Kendall’s τ, with an AVL tree structure adopted in the construction.The paper notes that its algorithmic details differ from those earlier methods despite their similar spirit.
  • Main result: The unbiased estimator of squared population distance covariance is computed in O(n log n) time.Each of the three terms in its rewritten expression is shown to admit an O(n log n) computation.
  • Computational ingredients: Partial sums and sorting of the x_i values enable computation of the required a_i· and b_i· quantities in O(n log n) time.The logarithmic factor may arise from sorting the x_i values.
  • Implementation: The appendix provides detailed implementations, including algorithms for a core subroutine and for computing distance covariance at O(n log n).Algorithm 2 realizes the idea from Lemma 4.5, Algorithm 3 supplies a subroutine, and Algorithm 1 computes distance covariance.

5. NUMERICAL EXPERIMENTS

Numerical experiments compare the fast distance-correlation algorithm with direct computation, test its scaling, and apply it to dependence examples and feature screening. The fast method matches direct solutions, avoids the direct method’s memory failure at large n, and reveals differences between Pearson’s and distance correlation in nonlinear cases.

  • 5.1 Matlab Implementation: The fast and direct implementations produced identical solutions across sample sizes from 32 to 2048.The comparison used 1,000 replications at each sample size.
  • 5.1 Matlab Implementation: At n = 1,048,576, the fast method completed in a little more than three minutes, with running time scaling approximately linearly with n.The observed trend was consistent with the claimed O(n log n) algorithm.
  • 5.2 Measuring Effectiveness of Distance Correlation: With n = 10,000, cases (3)–(8) had distance correlations clearly nonzero while Pearson’s correlations became nearly zero.For cases (1), (2), and (9), the two correlations were close to each other, as theory predicts.
  • 5.3 Feature Screening: In cases (3)–(8), Pearson’s correlation quickly converged to zero while sample distance correlation stayed away from zero.The convergence experiment supports the earlier large-sample comparison with high probability.
  • 5.3 Feature Screening: The feature-screening experiment increased the sample size from n = 200 to n = 20,000, making the advantage of distance correlation more evident as sample size increased.The earlier direct-method study had restricted the sample size to n = 200.

S SIS SIRS DC-SIS

The simulations compare SIS, SIRS, and DC-SIS across model settings using minimum model size and coverage probabilities. DC-SIS significantly outperforms SIS and SIRS in models (1.b)–(1.d), while their performance is similar in model (1.a).

  • Tables 4–6 report minimum model size S and coverage probabilities Ps and Pa across the simulation cases.The experiments use model sizes d1 = [p/10 log n], d2 = 2d1, and d3 = 3d1.
  • In model (1.a), SIS, SIRS, and DC-SIS have quite similar performance, indicating robust SIS performance there.
  • DC-SIS significantly outperforms SIS and SIRS in models (1.b)–(1.d).SIS and SIRS have little chance to identify X1 and X2 in models (1.b) and (1.c), and X22 in model (1.d).
  • Comparisons with Li et al. (2012) show a clearer distance-correlation advantage through smaller sample quantiles and larger coverage probabilities.

6. CONCLUSION

The conclusion addresses the O(n^2) cost of direct distance-correlation computation by proposing an average O(n log n) algorithm. Numerical experiments report a more evident advantage in many cases, and the method broadens the situations where distance correlation can be applied.

  • Direct implementation of distance correlation requires an O(n^2) algorithm for sample size n.
  • The paper proposes a fast algorithm with average computational complexity O(n log n).
  • Numerical experiments use sample sizes not attempted before and find the distance-correlation advantage more evident in many cases.
  • The proposed algorithm makes distance correlation more applicable where statistical dependence needs evaluation.

APPENDIX A. ALGORITHMS

The appendix presents algorithms for computing distance covariance through sorting, order indices, partial sums, and dyadic updates. These procedures culminate in an O(n log n) computation and return the distance covariance defined in (3.3).

  • Algorithm 2 uses a fast partial-sum sequence and a dyadic updating scheme as subroutines for the covariance computation.
  • For non-dyadic n, the algorithm chooses the smallest L such that n < 2^L before defining dyadic intervals.
  • The final algorithm outputs the distance covariance defined in (3.3).
  • The fast procedure takes observations x1, . . . , xn and y1, . . . , yn, sorts them, and records their order indices.
  • Recursive partial-sum relations compute sx(i) and sy(i) across the ordered observations.
  • Algorithm 1 computes distance covariance using an O(n log n) algorithm.

APPENDIX B. PROOFS

The proofs establish the statistical representation and computational complexity underlying the fast method. They show that the relevant statistic is a U-statistic and that the required summations can be computed in O(n log n).

  • The resulting implementation takes O(n log n) operations on average.
  • The proof identifies Ω_n as a U-statistic with a kernel given by the inner product defined in (3.2) for n = 4.
  • The proof reduces key terms to partial sums that can be computed in O(n) after sorting.
  • Sorting the y_j values can be performed in O(n log n) time using QuickSort.
  • A dynamic-programming-style update performs no more than log2 n updates at each of n stages, giving O(n log n) total computation.
  • The sums over prior observations satisfying y_j < y_i can be computed for all i in O(n log n).

4. Compute

The computation uses partial sums to make each algorithmic step efficient, yielding an overall average complexity of O(n log n) operations.

  • Partial sums make each of the algorithm’s steps executable within O(n log n) operations on average.The relevant quantities are α_i, β_i, and γ_i.
  • The algorithm’s efficiency follows from computing α_i, β_i, and γ_i as partial sums.
  • O(n log n) operations are required by the entire algorithm on average.
Loading 1410.1503v1…