Introduction
Estimating entropy in high-dimensional spaces is a cornerstone of information theory and data science, yet it remains notoriously difficult. Standard non-parametric methods often struggle as dimensionality increases due to the "curse of dimensionality." This paper introduces EC-kNN, a novel estimator designed to significantly reduce bias in high-dimensional entropy and mutual information estimation by fitting local ellipsoids to data and employing a robust bootstrap-style acceptance test.
The Problem: Spheres in High Dimensions
Entropy measures uncertainty in a distribution. While the k-Nearest Neighbor (kNN) estimator is the "gold standard" for non-parametric estimation, it relies on a "local uniformity" assumption. It assumes that within a tiny hypersphere (an $\epsilon$-ball) surrounding a data point, the probability density is constant.
As dimensionality ($D$) increases, this assumption frequently fails. High-dimensional data often exhibits "twisted" or stretched structures that a simple sphere cannot accurately capture, leading to significant systematic error or bias. Previous attempts to fix this using local Principal Component Analysis (PCA) often suffered from "over-correction," where random sampling noise was mistaken for meaningful structural patterns.
Methodology: The EC-kNN Estimator
The proposed kNN estimator with Ellipsoidal Correction (EC-kNN) addresses these issues through two primary innovations:
1. Local Ellipsoidal Correction
Instead of assuming a spherical neighborhood, EC-kNN performs a local PCA on the $k$ nearest neighbors of each point. By identifying the principal axes of the local distribution, the algorithm defines an ellipsoid. The widths of this ellipsoid are determined by the maximum distance to neighbors along each PCA axis, allowing the measurement volume to "stretch" or "shrink" to match the local data geometry.
2. Bootstrap Testing for Correction Acceptance
To prevent the model from over-fitting to random noise, the authors introduce a bootstrap safeguard. For every data point, a "reference" correction is generated by simulating a perfectly uniform distribution. The ellipsoidal correction is only applied if the empirical data shows a more significant "stretch" than this random reference. If the test fails, the algorithm falls back to the stable classical kNN estimate.
The final entropy is calculated by averaging these corrected local estimates, incorporating a logarithmic volume correction term derived from the ellipsoid's axes.
Experimental Results
The researchers evaluated EC-kNN against several alternatives, including classical kNN, kNN-bw (bandwidth), and LNC (Local Nonuniformity Correction), using three synthetic datasets: Symmetric Gaussian, Asymmetric Gaussian, and Mixture Gaussian.
The experiments tested these distributions across a range of dimensions up to $D=20$. The results demonstrate that EC-kNN is remarkably resilient to increasing dimensionality.
As shown in the figure above, while the Root Mean Square Error (RMSE) of other estimators (particularly kNN-bw) explodes as dimensions increase, EC-kNN (represented by the black line) remains stable and consistently achieves the lowest error. In the Asymmetric Gaussian case at $D=20$, the classical kNN's error was nearly triple that of EC-kNN.
Key Insights and Conclusion
The core contribution of this work is the recognition that high-dimensional bias is a geometric problem. By moving from spherical to ellipsoidal neighborhoods and protecting against noise with a bootstrap test, EC-kNN provides a more accurate and robust tool for information-theoretic analysis.
While the method is computationally more intensive due to the per-point PCA and bootstrap simulations, its superior accuracy in high-dimensional regimes makes it a powerful alternative for complex data analysis. Future work may involve optimizing the choice of $k$ and providing more formal variance bounds for the estimator.
Summary updated