# measuring statistical dependence with Hilbert-Schmidt norms

This is another very popular kernel-based approach fro detecting dependence which is called HSIC(Hilbert-Schmidt Independence Criteria). It's based on the eigenspectrum of covariance operators in reproducing kernel Hilbert spaces(RKHSs).This approach is simple and no user-defined regularisation is needed. Exponential convergence is guaranteed, so convergence is fast.

## Background

Before the proposal of HSIC, there are already a few kernel-based independence detecting methods. Bach[] proposed a regularised correlation operator which is derived from the covariance and cross-covariance operators, and its largest singular value was used as a static to test independence. Gretton et al.[] used the largest singular value of the cross-covariance operator which resulted constrained covariance(COCO). HSIC is a extension of the concept COCO by using the entire spectrum of cross-covariance operator to determine when all its singular values are zero rather than just looking the largest singular value.

## Cross-Covariance Operators

Hilbert-Schmidt Norm. Denote by $\mathit{C}:\mathcal{G}\to\mathcal{F}$ a linear operator. Provided the sum converges, the HS norm of $\mathit{C}$ is defined as

$||\mathit{C}||^2_{HS}:=\sum_{i,j}\lt \mathit{C}v_i,u_j\gt _\mathcal{F}^2$

Where $v_i,u_j$ are orthonormal bases of $\mathcal{G}$ and $\mathcal{F}$ respectively.

Hilbert-Schmidt Operator is defined based on the definition of Hilbert Schmidt norm as

$\lt \mathit{C},\mathit{D}\gt {HS}:=\sum_{i,j}\lt \mathit{C}v_i,u_j\gt _\mathcal{F}\lt \mathit{D}v_i,u_j\gt _\mathcal{F}$

Tensor Product. Let $f\in \mathcal{F}$ and $g\in \mathcal{G}$. The tensor product operator $f\otimes g:\mathcal{G}\to \mathcal{F}$ is defined as

$(f\otimes g)h:=f\lt g,h\gt _\mathcal{G}$ for all $h\in \mathcal{G}$

Cross-Covariance Operator associated with the joint measure $p_{x,y}$ on $(\mathcal{X}\times\mathcal{Y},\Gamma\times\Lambda)$ is a linear operator $C_{xy}:\mathcal{G}\to \mathcal{F}$ defined as

$C_{xy}:=E_{x,y}[(\theta (x)-\mu_x)\otimes (\psi (y)-\mu_y)]=E_{x,y}[\theta (x)\otimes \psi (y)]-\mu_x\otimes\mu_y$

## Hilbert-Schmidt Independence Criterion

Given separable RKHSs $\mathcal{F},\mathcal{G}$ and a joint measure $p_{xy}$ over $(\mathcal{X}\times\mathcal{Y},\Gamma\times\Lambda)$, HSIC is defined as the squared HS-norm of the associated cross-covariance operator $C_{xy}$:

$HSIC(p_{xy},\mathcal{F},\mathcal{G}):=||C_{xy}||_{HS}^2$

According to Gretton et al., the largest singular value $||C_{xy}||_{HS}=0$ if and only if x and y are independent. Since $||C_{xy}=0||_S$ if and only if $||C_{xy}||_{HS}=0$, so $||C_{xy}||_{HS}=0$ if and only if x and y are independent. Therefore, HSIC can be used as a independence criteria.

## Estimator of HSIC

Let $Z:={(x_1,y_1),\dots,(x_m,y_m)}\subseteq \mathcal{X}\times\mathcal{Y}$ be a series of m independent observations drawn from $p_{xy}$. An empirical estimator of HSIC, written HSIC(Z,\mathcal{F},\mathcal{G}) is given by

$HSIC(Z,\mathcal{F},\mathcal{G}):=(m-1)^{-2}trKHLH$

where $H,K,L\in \mathbb{R}^{m\times m},K_{ij}:=k(x_i,x_j),L_{i,j}:=l(y_i,y_j) and H_{ij}:=\delta_{ij}-m^{-1}$. It can be proved that the bias of the empirical HSIC is at $\mathnormal{O}(m^{-1})$.

## References

[1] Gretton, Arthur, et al. "Measuring statistical dependence with Hilbert-Schmidt norms." Algorithmic learning theory. Springer Berlin Heidelberg, 2005.

[2] Fukumizu, Kenji, Francis R. Bach, and Michael I. Jordan. "Kernel dimension reduction in regression." The Annals of Statistics 37.4 (2009): 1871-1905.

[3] Bach, Francis R., and Michael I. Jordan. "Kernel independent component analysis." The Journal of Machine Learning Research 3 (2003): 1-48.

[4] Baker, Charles R. "Joint measures and cross-covariance operators." Transactions of the American Mathematical Society 186 (1973): 273-289.