U-centering as subset ANOVA: edge regression and higher-order theory

Abstract

The unbiased sample versions of squared distance covariance and the Hilbert-Schmidt independence criterion (HSIC) are fourth-order U-statistics, yet U-centering evaluates them from pairwise arrays in $O(n^2)$ operations. We show that U-centering is exactly the least-squares residual obtained after fitting additive endpoint effects to a symmetric hollow array. This interpretation explains the zero row sums and the denominator $n(n-3)$ through the residual degrees of freedom. The same pairwise residualization also gives useful regression identities. After endpoint effects are removed from both arrays, the U-centered dependence $t$-statistic is the ordinary slope $t$-statistic obtained by regressing one adjusted array on the other. In the two-sample problem, pooling the observations and using the between-group pair indicator as the predictor shows that the generalized-energy statistic is twice the fitted slope. The common-endpoint and fully interacted regressions give the same slope but use different residual standard errors. For $n\ge2r$, we extend the construction to arrays indexed by $r$-subsets. Higher-order U-centering removes all effects involving fewer than $r$ sample labels, leaves zero $(r-1)$-way margins, and projects onto a residual space of dimension $\binom nr-\binom n{r-1}$. For two symmetric kernels with $r$ arguments, the normalized inner product of the centered arrays is unbiased for the cross-moment of their $r$th Hoeffding components. A direct estimator can involve products spanning as many as $2r$ observations, but subset-margin inversion or higher-order U-centering evaluates the same quantity in $O(n^r)$ operations for fixed $r$. When both arrays are formed from the same kernel and sample, this becomes a nonnegative unbiased estimator of the variance of the highest-order Hoeffding component.