Weighted k-NN graphs for Rényi entropy estimation in high dimensions

Rényi entropy is an information-theoretic measure of randomness which is fundamental to several applications. Several estimators of Rényi entropy based on k-nearest neighbor (k-NN) based distances have been proposed in literature. For d-dimensional densities f, the variance of these Rényi entropy estimators of f decay as 0(M^-1), where M is the sample size drawn from f. On the other hand, the bias, because of the curse of dimensionality, decays as 0(M^-1/d). As a result the bias dominates the mean square error (MSE) in high dimensions. To address this large bias in high dimensions, we propose a weighted k-NN estimator where the weights serve to lower the bias to 0(M^-1/2), which then ensures convergence of the weighted estimator at the parametric rate of 0(M^-1/2). These weights are determined by solving a convex optimization problem. We subsequently use the weighted estimator to perform anomaly detection in wireless sensor networks.