Biased and Unbiased HSIC Estimators

Why HSIC Has Two Sample Estimators

HSIC measures dependence by comparing feature representations of paired observations. Its population value is nonnegative, but estimating it from a finite sample involves choices about how to handle repeated indices and empirical centering. The common biased estimator uses all entries of two Gram matrices, including their diagonals. The unbiased estimator removes self-pairs and adjusts the remaining terms so its expectation equals population HSIC.

These names describe finite-sample bias, not whether an estimate is statistically useful. The biased estimator is always nonnegative, while the unbiased estimator can be negative in a particular sample. The distinction matters when interpreting a computed HSIC value: nonnegativity is a property of the population quantity, not of every unbiased estimate of it.

For independent copies \((X',Y')\) and \((X'',Y'')\), the population HSIC functional can be written as

In the last term, \((X,Y)\), \(X'\), and \(Y''\) are independent, with \(X'\) and \(Y''\) drawn from their respective marginal distributions. This expression is equivalent to the squared Hilbert–Schmidt norm of the cross-covariance operator when that operator is defined. In particular, population HSIC is nonnegative.

The Biased V-Statistic

The biased estimator is the HSIC functional evaluated at the empirical distribution of the observed pairs. Empirical averaging allows indices to repeat, so the sums include diagonal entries such as \(K_{ii}=k(X_i,X_i)\). In matrix notation, the result is

The equality follows because \(H\) is symmetric and idempotent: \(\operatorname{tr}(KHLH)=\operatorname{tr}(HKHLH)=\operatorname{tr}((HKH)(HLH))\). The centered Gram matrices \(HKH\) and \(HLH\) are positive semidefinite. Their entrywise inner product, which is the trace above, is nonnegative: for positive semidefinite matrices \(A,B\), \(\operatorname{tr}(AB)=\operatorname{tr}(A^{1/2}BA^{1/2})\geq 0\). Thus the biased estimate cannot be negative.

The estimator is a V-statistic because its sums range over all index tuples, including tuples with repeated indices. The empirical centering and the diagonal terms make it a convenient direct plug-in estimate, but do not make it exactly unbiased at finite \(n\).

The Unbiased U-Statistic

To remove finite-sample bias, estimate the three expectations in the population formula using only distinct observations. Define the following sums, with every index in each sum distinct:

Here \(A_n\) estimates the first expectation, \(B_n\) estimates the product of marginal expectations, and \(C_n\) estimates the final expectation in the population expression. For example, in a summand of \(C_n\), the shared anchor observation \(i\) supplies \(X_i\) and \(Y_i\), while observations \(j\) and \(q\) supply independent draws of \(X'\) and \(Y''\).

Proof. For every summand in \(A_n\), the two observations are independent copies of \((X,Y)\). Hence \(E[K_{ij}L_{ij}]=E[k(X,X')l(Y,Y')]\), so \(E[A_n]\) equals the first population term. In every summand of \(B_n\), the two kernel factors are formed from four distinct independent observations. Thus \(E[K_{ij}L_{qr}]=E[k(X,X')]E[l(Y,Y')]\), and \(E[B_n]\) equals the second term. In every summand of \(C_n\), the three distinct observations have the roles described above, so \(E[K_{ij}L_{iq}]=E[k(X,X')l(Y,Y'')]\). Consequently, taking expectations of \(A_n+B_n-2C_n\) gives exactly the population formula. \(\square\)

A common matrix form makes this estimator easier to compute. Let \(K^{0}\) and \(L^{0}\) equal \(K\) and \(L\) off the diagonal and have zero diagonal. Then

This formula is obtained by expanding the distinct-index sums and collecting terms according to which indices coincide. In particular, the product of the two off-diagonal totals contains both disjoint index pairs and pairs that overlap; the row-sum correction removes the unwanted overlap contributions. The zero diagonals are part of the formula. Substituting the original Gram matrices without zeroing their diagonals does not give this U-statistic.

Finite-Sample Interpretation and a Common Pitfall

The V-statistic uses empirical centering and all \(n^2\) observation pairs, including self-pairs. It is nonnegative and is often convenient for reporting or computation, but its finite-sample expectation need not equal population HSIC. The U-statistic excludes diagonal terms and corrects for the resulting index overlaps. It is unbiased under the independent and identically distributed sampling assumption, but it may have higher variability and may be negative.

Common mistake: “HSIC is nonnegative, so a negative unbiased HSIC estimate must be a coding error.” This reasoning confuses a population quantity with an unbiased estimate based on one random sample. The population value is nonnegative; unbiasedness constrains the average of the estimator over repeated samples, not its sign in each sample. A negative estimate should prompt checks of the zero-diagonal convention and the formula, but it is not by itself evidence of an error.

A second practical error is to treat the two estimates as interchangeable without recording which one was used. Their finite-sample values can differ substantially, and a reported number should identify the estimator. The unbiased formula also requires \(n\geq4\); its denominators do not define an estimator for smaller samples.