# Computationally Efficient Approximations for Matrix-based Renyi's Entropy

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 23 of its 89 references that are in the map.
- First posted on arXiv 27 Dec 2021.

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

- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [Very Deep Convolutional Networks for Large-Scale Image Recognition](https://mlsanity.com/paper/1409.1556/) (2014)
- [Learning deep representations by mutual information estimation and maximization](https://mlsanity.com/paper/1808.06670/) (2018)
- [Deep Variational Information Bottleneck](https://mlsanity.com/paper/1612.00410/) (2016)
- [MINE: Mutual Information Neural Estimation](https://mlsanity.com/paper/1801.04062/) (2018)
- [Don't Decay the Learning Rate, Increase the Batch Size](https://mlsanity.com/paper/1711.00489/) (2017)
- [On Mutual Information Maximization for Representation Learning](https://mlsanity.com/paper/1907.13625/) (2019)
- [Information-theoretic analysis of generalization capability of learning algorithms](https://mlsanity.com/paper/1705.07809/) (2017)
- [CLUB: A Contrastive Log-ratio Upper Bound of Mutual Information](https://mlsanity.com/paper/2006.12013/) (2020)
- [Graph Information Bottleneck](https://mlsanity.com/paper/2010.12811/) (2020)
- [Nonlinear Information Bottleneck](https://mlsanity.com/paper/1705.02436/) (2017)
- [Learning Representations for Neural Network-Based Classification Using the Information Bottleneck Principle](https://mlsanity.com/paper/1802.09766/) (2018)
- [Understanding Convolutional Neural Networks with Information Theory: An Initial Exploration](https://mlsanity.com/paper/1804.06537/) (2018)
- [Distributed Variational Representation Learning](https://mlsanity.com/paper/1807.04193/) (2018)
- [Measuring Dependence with Matrix-based Entropy Functional](https://mlsanity.com/paper/2101.10160/) (2021)
- [Information Theoretic Representation Distillation](https://mlsanity.com/paper/2112.00459/) (2021)
- [Deep Deterministic Information Bottleneck with Matrix-based Entropy Functional](https://mlsanity.com/paper/2102.00533/) (2021)
- [Partial Information Decomposition as a Unified Approach to the Specification of Neural Goal Functions](https://mlsanity.com/paper/1510.00831/) (2015)
- [Information Plane Analysis of Deep Neural Networks via Matrix-Based Renyi's Entropy and Tensor Kernels](https://mlsanity.com/paper/1909.11396/) (2019)
- [Quantum query complexity of entropy estimation](https://mlsanity.com/paper/1710.06025/) (2017)
- [Information Theoretic Learning with Infinitely Divisible Kernels](https://mlsanity.com/paper/1301.3551/) (2013)
- [A Randomized Algorithm for Approximating the Log Determinant of a Symmetric Positive Definite Matrix](https://mlsanity.com/paper/1503.00374/) (2015)
- [Perturbation Theory for the Information Bottleneck](https://mlsanity.com/paper/2105.13977/) (2021)

## Built on by (most cited first, 4 of 4)

- [Modeling Higher-Order Brain Interactions via a Multi-View Information Bottleneck Framework for fMRI-based Psychiatric Diagnosis](https://mlsanity.com/paper/2604.17713/) (2026)
- [Robust and Fast Measure of Information via Low-rank Representation](https://mlsanity.com/paper/2211.16784/) (2022)
- [InfoSAM: Fine-Tuning the Segment Anything Model from An Information-Theoretic Perspective](https://mlsanity.com/paper/2505.21920/) (2025)
- [Deep Deterministic Nonlinear ICA via Total Correlation Minimization with Matrix-Based Entropy Functional](https://mlsanity.com/paper/2601.00904/) (2025)

## Abstract (arXiv)

The recently developed matrix based Renyi's entropy enables measurement of information in data simply using the eigenspectrum of symmetric positive semi definite (PSD) matrices in reproducing kernel Hilbert space, without estimation of the underlying data distribution. This intriguing property makes the new information measurement widely adopted in multiple statistical inference and learning tasks. However, the computation of such quantity involves the trace operator on a PSD matrix G to power α(i.e., tr(Gα)), with a normal complexity of nearly O(n3), which severely hampers its practical usage when the number of samples (i.e., n) is large. In this work, we present computationally efficient approximations to this new entropy functional that can reduce its complexity to even significantly less than O(n2). To this end, we leverage the recent progress on Randomized Numerical Linear Algebra, developing Taylor, Chebyshev and Lanczos approximations to tr(Gα) for arbitrary values of α by converting it into matrix-vector multiplications problem. We also establish the connection between the matrix-based Renyi's entropy and PSD matrix approximation, which enables exploiting both clustering and block low-rank structure of G to further reduce the computational cost. We theoretically provide approximation accuracy guarantees and illustrate the properties of different approximations. Large-scale experimental evaluations on both synthetic and real-world data corroborate our theoretical findings, showing promising speedup with negligible loss in accuracy.