Divergence estimation for multidimensional densities via κ-nearest-neighbor distances

Qing Wang; Sanjeev R. Kulkarni; Sergio Verdú

doi:10.1109/TIT.2009.2016060

Divergence estimation for multidimensional densities via κ-nearest-neighbor distances

Qing Wang, Sanjeev R. Kulkarni, Sergio Verdú

Research output: Contribution to journal › Article › peer-review

258 Scopus citations

Abstract

A new universal estimator of divergence is presented for multidimensional continuous densities based on κ-nearest-neighbor (κ-NN) distances. Assuming independent and identically distributed (i.i.d.) samples, the new estimator is proved to be asymptotically unbiased and mean-square consistent. In experiments with high-dimensional data, the κ-NN approach generally exhibits faster convergence than previous algorithms. It is also shown that the speed of convergence of the κ-NN method can be further improved by an adaptive choice of κ.

Original language	English (US)
Pages (from-to)	2392-2405
Number of pages	14
Journal	IEEE Transactions on Information Theory
Volume	55
Issue number	5
DOIs	https://doi.org/10.1109/TIT.2009.2016060
State	Published - 2009

All Science Journal Classification (ASJC) codes

Information Systems
Computer Science Applications
Library and Information Sciences

Keywords

Divergence
Information measure
Kullback
Leibler
Nearest-neighbor
Partition
Random vector
Universal estimation

Access to Document

10.1109/TIT.2009.2016060

Cite this

@article{69f89afaf76c43aca6070f2ccb50d72e,

title = "Divergence estimation for multidimensional densities via κ-nearest-neighbor distances",

abstract = "A new universal estimator of divergence is presented for multidimensional continuous densities based on κ-nearest-neighbor (κ-NN) distances. Assuming independent and identically distributed (i.i.d.) samples, the new estimator is proved to be asymptotically unbiased and mean-square consistent. In experiments with high-dimensional data, the κ-NN approach generally exhibits faster convergence than previous algorithms. It is also shown that the speed of convergence of the κ-NN method can be further improved by an adaptive choice of κ.",

keywords = "Divergence, Information measure, Kullback, Leibler, Nearest-neighbor, Partition, Random vector, Universal estimation",

author = "Qing Wang and Kulkarni, {Sanjeev R.} and Sergio Verd{\'u}",

note = "Funding Information: Manuscript received February 20, 2007; revised June 04, 2008. Current version published April 22, 2009. This work was supported in part by ARL MURI under Grant DAAD19-00-1-0466, Draper Laboratory under IR&D 6002 Grant DL-H-546263, and the National Science Foundation under Grant CCR-0312413. The material in this paper was presented in part at the IEEE International Symposium on Information Theory (ISIT), Seattle, WA, July 2006.",

year = "2009",

doi = "10.1109/TIT.2009.2016060",

language = "English (US)",

volume = "55",

pages = "2392--2405",

journal = "IEEE Transactions on Information Theory",

issn = "0018-9448",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

number = "5",

}

TY - JOUR

T1 - Divergence estimation for multidimensional densities via κ-nearest-neighbor distances

AU - Wang, Qing

AU - Kulkarni, Sanjeev R.

AU - Verdú, Sergio

N1 - Funding Information: Manuscript received February 20, 2007; revised June 04, 2008. Current version published April 22, 2009. This work was supported in part by ARL MURI under Grant DAAD19-00-1-0466, Draper Laboratory under IR&D 6002 Grant DL-H-546263, and the National Science Foundation under Grant CCR-0312413. The material in this paper was presented in part at the IEEE International Symposium on Information Theory (ISIT), Seattle, WA, July 2006.

PY - 2009

Y1 - 2009

N2 - A new universal estimator of divergence is presented for multidimensional continuous densities based on κ-nearest-neighbor (κ-NN) distances. Assuming independent and identically distributed (i.i.d.) samples, the new estimator is proved to be asymptotically unbiased and mean-square consistent. In experiments with high-dimensional data, the κ-NN approach generally exhibits faster convergence than previous algorithms. It is also shown that the speed of convergence of the κ-NN method can be further improved by an adaptive choice of κ.

AB - A new universal estimator of divergence is presented for multidimensional continuous densities based on κ-nearest-neighbor (κ-NN) distances. Assuming independent and identically distributed (i.i.d.) samples, the new estimator is proved to be asymptotically unbiased and mean-square consistent. In experiments with high-dimensional data, the κ-NN approach generally exhibits faster convergence than previous algorithms. It is also shown that the speed of convergence of the κ-NN method can be further improved by an adaptive choice of κ.

KW - Divergence

KW - Information measure

KW - Kullback

KW - Leibler

KW - Nearest-neighbor

KW - Partition

KW - Random vector

KW - Universal estimation

UR - http://www.scopus.com/inward/record.url?scp=65749108082&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=65749108082&partnerID=8YFLogxK

U2 - 10.1109/TIT.2009.2016060

DO - 10.1109/TIT.2009.2016060

M3 - Article

AN - SCOPUS:65749108082

SN - 0018-9448

VL - 55

SP - 2392

EP - 2405

JO - IEEE Transactions on Information Theory

JF - IEEE Transactions on Information Theory

IS - 5

ER -

Divergence estimation for multidimensional densities via κ-nearest-neighbor distances

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this