Estimation of Rényi Entropy and Mutual Information Based on Generalized Nearest-Neighbor Graphs

Abstract

We present simple and computationally efficient nonparametric estimators of Rényi entropy and mutual information based on an i.i.d. sample drawn from an unknown, absolutely continuous distribution over ${\mathbb{R}}^d$. The estimators are calculated as the sum of $p$-th powers of the Euclidean lengths of the edges of the `generalized nearest-neighbor' graph of the sample and the empirical copula of the sample respectively. For the first time, we prove the almost sure consistency of these estimators and upper bounds on their rates of convergence, the latter of which under the assumption that the density underlying the sample is Lipschitz continuous. Experiments demonstrate their usefulness in independent subspace analysis.

to appear at NIPS 2010 (Neural Information Processing Systems)

References in corpus (4)

• Estimating Mutual Information
• Information theory in molecular biology
• A class of Rényi information estimators for multidimensional densities
• Undercomplete Blind Subspace Deconvolution

Cited by in corpus (19)

• Nonparametric Divergence Estimation with Applications to Machine Learning on Distributions
• Copula-based Kernel Dependency Measures
• Analysis of k-Nearest Neighbor Distances with Application to Entropy Estimation
• A Kernel Test for Three-Variable Interactions
• Entropic one-class classifiers
• Clustering with minimum spanning trees: How good can it be?
• CCMI : Classifier based Conditional Mutual Information Estimation
• Demystifying Fixed k-Nearest Neighbor Information Estimators
• Direct estimation of density functionals using a polynomial basis
• Information Theoretic Structure Learning with Confidence
• Geometric Estimation of Multivariate Dependency
• Quantifying dependencies for sensitivity analysis with multivariate input sample data
• Nearest neighbor density functional estimation from inverse Laplace transform
• One-class classifiers based on entropic spanning graphs
• Lepski's Method and Adaptive Estimation of Nonlinear Integral Functionals of Density
• Distributed High Dimensional Information Theoretical Image Registration via Random Projections
• Model of Cognitive Dynamics Predicts Performance on Standardized Tests
• Building Models for Biopathway Dynamics Using Intrinsic Dimensionality Analysis
• Estimating Rényi's $\alpha$-Cross-Entropies in a Matrix-Based Way