HSIC as Kernel Cross-Covariance

From Scalar Covariance to Kernel Cross-Covariance

For scalar random variables, covariance summarizes linear association. When observations are vectors or have more complex structure, one can instead map each observation into a feature space and measure covariance there. The Hilbert–Schmidt independence criterion, or HSIC, is the squared size of the resulting cross-covariance operator. It is therefore a nonnegative measure of dependence in the chosen feature spaces, with a population definition and a direct empirical Gram-matrix form.

The definition itself does not guarantee that HSIC detects every possible dependence. That depends on properties of the kernels, considered separately in the study of characteristic kernels. Here the focus is the operator definition, its kernel expression, and the exact relationship to a centered Gram-matrix statistic.

Feature Maps and the Cross-Covariance Operator

Let \(X\) and \(Y\) be random elements taking values in measurable spaces \(\mathcal X\) and \(\mathcal Y\). Let \(k\) and \(l\) be measurable, real-valued positive definite kernels on those spaces, with reproducing-kernel Hilbert spaces (RKHSs) \(\mathcal H\) and \(\mathcal G\). Write their feature maps as \(\phi(x)=k(x,\cdot)\) and \(\psi(y)=l(y,\cdot)\). The reproducing property gives \(k(x,x')=\langle\phi(x),\phi(x')\rangle_{\mathcal H}\), and likewise for \(l\).

Assume the feature maps are strongly measurable, the RKHSs are separable, and \(E[k(X,X)]<\infty\) and \(E[l(Y,Y)]<\infty\). These moment conditions ensure that the feature means exist as Bochner expectations. Define \(\mu_X=E[\phi(X)]\), \(\mu_Y=E[\psi(Y)]\), and the centered features \(\tilde\phi(X)=\phi(X)-\mu_X\), \(\tilde\psi(Y)=\psi(Y)-\mu_Y\).

The operator is well-defined under the stated conditions. Indeed, \(E\|\tilde\phi(X)\|_{\mathcal H}^2<\infty\) and \(E\|\tilde\psi(Y)\|_{\mathcal G}^2<\infty\). By Cauchy–Schwarz, \(E[\|\tilde\phi(X)\|\|\tilde\psi(Y)\|]\leq \{E\|\tilde\phi(X)\|^2 E\|\tilde\psi(Y)\|^2\}^{1/2}<\infty\). Thus the rank-one operator inside the expectation has integrable Hilbert–Schmidt norm.

For \(f\in\mathcal H\) and \(g\in\mathcal G\), the operator connects centered feature values to scalar covariance: $$ \langle f,C_{XY}g\rangle_{\mathcal H} =E[\langle f,\tilde\phi(X)\rangle_{\mathcal H} \langle g,\tilde\psi(Y)\rangle_{\mathcal G}]. $$ So \(C_{XY}\) collects covariances between all pairs of linear functionals of the two feature maps. HSIC squares and sums these covariances in an orthonormal-basis-independent way.

Population HSIC as a Centered-Kernel Expectation

Define the population-centered kernels by centering each feature map with respect to its own marginal distribution: $$ k_c(x,x')=\langle\phi(x)-\mu_X,\phi(x')-\mu_X\rangle_{\mathcal H}, \qquad l_c(y,y')=\langle\psi(y)-\mu_Y,\psi(y')-\mu_Y\rangle_{\mathcal G}. $$ Equivalently, \(k_c(x,x')=k(x,x')-E[k(x,X)]-E[k(X,x')]+E[k(X,X')]\), where \(X,X'\) in the expectations are independent draws from the marginal distribution. The analogous expression holds for \(l_c\).

Proof. Write \(A=\tilde\phi(X)\), \(B=\tilde\psi(Y)\), and let \(A',B'\) be the corresponding centered features from the independent copy. For rank-one operators, the Hilbert–Schmidt inner product satisfies \(\langle a\otimes b,a'\otimes b'\rangle_{\mathrm{HS}} =\langle a,a'\rangle_{\mathcal H}\langle b,b'\rangle_{\mathcal G}\). The integrability established above permits taking the expectation of this inner product for independent copies. Therefore $$ \begin{aligned} \|C_{XY}\|_{\mathrm{HS}}^2 &=\langle E[A\otimes B],E[A'\otimes B']\rangle_{\mathrm{HS}}\\ &=E[\langle A,A'\rangle_{\mathcal H}\langle B,B'\rangle_{\mathcal G}]\\ &=E[k_c(X,X')l_c(Y,Y')]. \end{aligned} $$ The last equality follows from the definitions of the centered kernels. This proves the result. \(\square\)

This expression is useful because it turns an operator norm into an expectation involving scalar kernel evaluations. It also makes clear that the two kernel factors are centered using their separate marginals, while the expectation is over paired observations from the joint distribution.

The Empirical Centered Gram-Matrix Statistic

Now observe \(n\) paired data points \((x_1,y_1),\ldots,(x_n,y_n)\). Let \(K,L\in\mathbb R^{n\times n}\) be their Gram matrices, with \(K_{ij}=k(x_i,x_j)\) and \(L_{ij}=l(y_i,y_j)\). Let \(\mathbf 1\) be the length-\(n\) vector of ones and define the centering matrix \(H=I_n-\mathbf 1\mathbf 1^\mathsf T/n\). Multiplication on both sides gives the centered Gram matrices \(K_c=HKH\) and \(L_c=HLH\).

The empirical feature means are \(\bar\phi=n^{-1}\sum_i\phi(x_i)\) and \(\bar\psi=n^{-1}\sum_i\psi(y_i)\). The empirical cross-covariance operator, using divisor \(n\), is $$ \widehat C_{XY}=\frac1n\sum_{i=1}^n (\phi(x_i)-\bar\phi)\otimes(\psi(y_i)-\bar\psi). $$ Its squared Hilbert–Schmidt norm is the empirical plug-in HSIC statistic.

Proof. Set \(\tilde\phi_i=\phi(x_i)-\bar\phi\) and \(\tilde\psi_i=\psi(y_i)-\bar\psi\). Expanding the squared norm and applying the rank-one inner-product identity gives $$ \begin{aligned} \|\widehat C_{XY}\|_{\mathrm{HS}}^2 &=\frac{1}{n^2}\sum_{i,j} \langle\tilde\phi_i,\tilde\phi_j\rangle_{\mathcal H} \langle\tilde\psi_i,\tilde\psi_j\rangle_{\mathcal G}. \end{aligned} $$ The first inner product is \((HKH)_{ij}\), and the second is \((HLH)_{ij}\), because centering the feature vectors subtracts their sample means. This proves the double-sum identity. Since \(K_c,L_c\) are symmetric, \(\sum_{i,j}(K_c)_{ij}(L_c)_{ij}=\operatorname{tr}(K_cL_c)\). Using \(H^2=H\) and cyclic invariance of trace, $$ \operatorname{tr}(K_cL_c)=\operatorname{tr}(HKHLH) =\operatorname{tr}(KHLH). $$ Dividing by \(n^2\) gives the claimed trace formula. \(\square\)

Interpretation and a Common Pitfall

HSIC is nonnegative because it is a squared norm, and it measures cross-covariance across the selected feature spaces rather than just covariance between the original coordinates. For example, with \(X\) equally likely to be \(-1,0,1\) and \(Y=X^2\), \(E[X]=0\), \(E[Y]=2/3\), and \(E[XY]=E[X^3]=0\), so \(\operatorname{Cov}(X,Y)=0\) even though \(Y\) is determined by \(X\). Linear kernels therefore give HSIC equal to zero in this example. A richer feature representation can capture associations that a scalar covariance misses, but the choice of kernels matters.

• Pitfall: treating zero cross-covariance as independence for every kernel. The reasoning “HSIC is zero, therefore \(X\) and \(Y\) are independent” is not valid without additional conditions on the kernels. With linear kernels, HSIC is only squared covariance in the scalar case, and the preceding example has zero covariance despite dependence. The correction is to interpret zero HSIC first as \(C_{XY}=0\); an independence conclusion requires suitable kernel properties.
• Pitfall: using uncentered Gram matrices in the centered formula. The formula involves \(K_c=HKH\) and \(L_c=HLH\), or equivalently the trace expression with the centering matrices. Omitting centering changes the statistic because it retains feature-mean contributions.
• Pitfall: losing a factor of \(n\). The empirical operator uses divisor \(n\), so its squared norm has divisor \(n^2\). A different divisor defines a different finite-sample scaling.

The operator view explains why the matrix calculation works: centering the Gram matrices is exactly centering the feature vectors, and the trace aggregates all pairwise products of those centered feature inner products. This makes the population concept usable even when feature maps are implicit and the RKHS is infinite-dimensional.