# Optimal Randomized Approximations for Matrix based Renyi's Entropy

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 16 of its 61 references that are in the map.
- First posted on arXiv 16 May 2022.

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

- [Very Deep Convolutional Networks for Large-Scale Image Recognition](https://mlsanity.com/paper/1409.1556/) (2014)
- [Deep Variational Information Bottleneck](https://mlsanity.com/paper/1612.00410/) (2016)
- [Don't Decay the Learning Rate, Increase the Batch Size](https://mlsanity.com/paper/1711.00489/) (2017)
- [Invariance Principle Meets Information Bottleneck for Out-of-Distribution Generalization](https://mlsanity.com/paper/2106.06607/) (2021)
- [Graph Information Bottleneck](https://mlsanity.com/paper/2010.12811/) (2020)
- [Learning Representations for Neural Network-Based Classification Using the Information Bottleneck Principle](https://mlsanity.com/paper/1802.09766/) (2018)
- [Hutch++: Optimal Stochastic Trace Estimation](https://mlsanity.com/paper/2010.09649/) (2020)
- [The deterministic information bottleneck](https://mlsanity.com/paper/1604.00268/) (2016)
- [From Manifold to Manifold: Geometry-Aware Dimensionality Reduction for SPD Matrices](https://mlsanity.com/paper/1407.1120/) (2014)
- [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)
- [Stability of the Lanczos Method for Matrix Function Approximation](https://mlsanity.com/paper/1708.07788/) (2017)
- [Unpacking Information Bottlenecks: Unifying Information-Theoretic Objectives in Deep Learning](https://mlsanity.com/paper/2003.12537/) (2020)
- [Information Theoretic Learning with Infinitely Divisible Kernels](https://mlsanity.com/paper/1301.3551/) (2013)
- [HRel: Filter Pruning based on High Relevance between Activation Maps and Class Labels](https://mlsanity.com/paper/2202.10716/) (2022)

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

- [Towards a Scalable Reference-Free Evaluation of Generative Models](https://mlsanity.com/paper/2407.02961/) (2024)
- [Do Vendi Scores Converge with Finite Samples? Truncated Vendi Score for Finite-Sample Convergence Guarantees](https://mlsanity.com/paper/2410.21719/) (2024)
- [MvHo-IB: Multi-View Higher-Order Information Bottleneck for Brain Disorder Diagnosis](https://mlsanity.com/paper/2507.02847/) (2025)
- [Discovering Common Information in Multi-view Data](https://mlsanity.com/paper/2406.15043/) (2024)
- [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 Matrix-based Renyi's entropy enables us to directly measure information quantities from given data without the costly probability density estimation of underlying distributions, thus has been widely adopted in numerous statistical learning and inference tasks. However, exactly calculating this new information quantity requires access to the eigenspectrum of a semi-positive definite (SPD) matrix A which grows linearly with the number of samples n, resulting in a O(n3) time complexity that is prohibitive for large-scale applications. To address this issue, this paper takes advantage of stochastic trace approximations for matrix-based Renyi's entropy with arbitrary α ∈ R^+ orders, lowering the complexity by converting the entropy approximation to a matrix-vector multiplication problem. Specifically, we develop random approximations for integer order α cases and polynomial series approximations (Taylor and Chebyshev) for non-integer α cases, leading to a O(n2sm) overall time complexity, where s,m ll n denote the number of vector queries and the polynomial order respectively. We theoretically establish statistical guarantees for all approximation algorithms and give explicit order of s and m with respect to the approximation error varepsilon, showing optimal convergence rate for both parameters up to a logarithmic factor. Large-scale simulations and real-world applications validate the effectiveness of the developed approximations, demonstrating remarkable speedup with negligible loss in accuracy.