# Linear cost mutual information estimation and independence test of similar performance as HSIC

arXiv: https://arxiv.org/abs/2508.18338 · HTML: https://mlsanity.com/paper/2508.18338/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 9 of its 18 references that are in the map.
- First posted on arXiv 25 Aug 2025.

## Builds on (most cited first, 9 of 9)

- [The HSIC Bottleneck: Deep Learning without Back-Propagation](https://mlsanity.com/paper/1908.01580/) (2019)
- [New Bounds for Matrix Multiplication: from Alpha to Omega](https://mlsanity.com/paper/2307.07970/) (2023)
- [Kernelized information bottleneck leads to biologically plausible 3-factor Hebbian learning in deep networks](https://mlsanity.com/paper/2006.07123/) (2020)
- [A Practical Introduction to Kernel Discrepancies: MMD, HSIC & KSD](https://mlsanity.com/paper/2503.04820/) (2025)
- [Modelling bid-ask spread conditional distributions using hierarchical correlation reconstruction](https://mlsanity.com/paper/1911.02361/) (2019)
- [Exploiting statistical dependencies of time series with hierarchical correlation reconstruction](https://mlsanity.com/paper/1807.04119/) (2018)
- [Predicting conditional probability distributions of redshifts of Active Galactic Nuclei using Hierarchical Correlation Reconstruction](https://mlsanity.com/paper/2206.06194/) (2022)
- [Credibility evaluation of income data with hierarchical correlation reconstruction](https://mlsanity.com/paper/1812.08040/) (2018)
- [Fast optimization of common basis for matrix set through Common Singular Value Decomposition](https://mlsanity.com/paper/2204.08242/) (2022)

## Abstract (arXiv)

Evaluation of statistical dependencies between two data samples is a basic problem of data science/machine learning, and HSIC (Hilbert-Schmidt Information Criterion)~citeHSIC is considered the state-of-art method. However, for size n data sample it requires multiplication of n× n matrices, what currently needs ~ O(n2.37) computational complexity~citemult, making it impractical for large data samples. We discuss HCR (Hierarchical Correlation Reconstruction) as its linear cost practical alternative, in tests of even higher sensitivity to dependencies, and additionally providing actual joint distribution model for chosen significance level, by description of dependencies through features being mixed moments, starting with correlation and homoscedasticity. Also allowing to approximate mutual information as just sum of squares of such nontrivial mixed moments between two data samples. Such single dependence describing feature is calculated in O(n) linear time. Their number to test varies with dimension d - requiring O(d2) for pairwise dependencies, O(d3) if wanting to also consider more subtle triplewise, and so on.