Divergence Estimation for Multidimensional Densities Via k-Nearest-Neighbor Distances

<para xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> A new universal estimator of divergence is presented for multidimensional continuous densities based on <emphasis emphasistype="italic"><formula formulatype="inline"> <tex Notation="TeX">k</tex></formula></emphasis>-nearest-neighbor (<emphasis emphasistype="italic"><formula formulatype="inline"><tex Notation="TeX">k</tex> </formula></emphasis>-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 <emphasis emphasistype="italic"><formula formulatype="inline"><tex Notation="TeX">k</tex></formula></emphasis>-NN approach generally exhibits faster convergence than previous algorithms. It is also shown that the speed of convergence of the <emphasis emphasistype="italic"><formula formulatype="inline"> <tex Notation="TeX">k</tex></formula></emphasis>-NN method can be further improved by an adaptive choice of <emphasis emphasistype="italic"><formula formulatype="inline"><tex Notation="TeX">k</tex></formula></emphasis>. </para>