Demystifying Fixed <inline-formula> <tex-math notation="LaTeX">k </tex-math> </inline-formula>-Nearest Neighbor Information Estimators

DOI10.1109/TIT.2018.2807481MaRDI QIDQ4682867zbMATH OpenOpenAlexFDO

Authors Weihao Gao, Sewoong Oh, P. Viswanath

Publication date 19 September 2018

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1604.03006

Mathematics Subject Classification ID

Statistical aspects of information-theoretic topics (62B10) Nonparametric estimation (62G05) Information theory (general) (94A15) Measures of information, entropy (94A17)

Abstract: Estimating mutual information from i.i.d. samples drawn from an unknown joint density function is a basic statistical problem of broad interest with multitudinous applications. The most popular estimator is one proposed by Kraskov and St"ogbauer and Grassberger (KSG) in 2004, and is nonparametric and based on the distances of each sample to its $k^{mth}$ nearest neighboring sample, where $k$ is a fixed small integer. Despite its widespread use (part of scientific software packages), theoretical properties of this estimator have been largely unexplored. In this paper we demonstrate that the estimator is consistent and also identify an upper bound on the rate of convergence of the bias as a function of number of samples. We argue that the superior performance benefits of the KSG estimator stems from a curious "correlation boosting" effect and build on this intuition to modify the KSG estimator in novel ways to construct a superior estimator. As a byproduct of our investigations, we obtain nearly tight rates of convergence of the $el{l}_2$ error of the well known fixed $k$ nearest neighbor estimator of differential entropy by Kozachenko and Leonenko.

Cited in

(10)

• Efficient multivariate entropy estimation via \(k\)-nearest neighbour distances
• Optimal rates of entropy estimation over Lipschitz balls
• The entropy based goodness of fit tests for generalized von Mises-Fisher distributions and beyond
• Entropy-based test for generalised Gaussian distributions
• Exact upper bound on the sum of squared nearest-neighbor distances between points in a rectangle
• Analysis of KNN Information Estimators for Smooth Distributions
• Quantifying information conveyed by large neuronal populations
• Bucketing Coding and Information Theory for the Statistical High-Dimensional Nearest-Neighbor Problem
• Entropy estimation via uniformization
• Optimal experimental design: formulations and computations

This page was built for publication: Demystifying Fixed <inline-formula> <tex-math notation="LaTeX">$k$ </tex-math> </inline-formula>-Nearest Neighbor Information Estimators

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4682867)