One-sentence Summary

Researchers at Lancaster University introduce an efficient dimensionality reduction method that builds a matrix from nearest-neighbor pairs to capture local covariance, yielding a consistent estimator of the Density Information Matrix (a non-parametric analogue of the Fisher Information Matrix) that enables high-information projections for tasks such as cluster analysis and outlier detection, while avoiding the computational cost of previous surrogate-density-based estimators.

Key Contributions

• A dimensionality reduction method is proposed that constructs a projection from the spectral decomposition of a matrix encoding local covariance through pairs of nearest neighbors, designed to enhance nearest-neighbor relationships.
• Under standard regularity conditions, this matrix is a consistent estimator of the Density Information Matrix (DIM), a nonparametric analogue of the Fisher information, overcoming the high computational cost and surrogate-density limitation of previous DIM estimators.
• The method's practical utility is demonstrated in downstream cluster analysis and outlier detection tasks.

Introduction

Dimension reduction aims to preserve useful structure in multivariate data, either through global variance-based methods such as PCA or through local graph-based manifold learning. An alternative information-theoretic view treats projections with low entropy after accounting for scale as more informative, since multimodality and long-tailedness are associated with clusters and outliers. The Density Information Matrix provides a nonparametric analogue of the Fisher Information Matrix and has links to independent component analysis and departure from Gaussianity, but it is difficult to estimate directly. Prior work has largely estimated the DIM of a surrogate density proportional to the squared data density, which the authors find less effective in high-dimensional settings. The authors introduce a simple linear dimensionality reduction method based on a k-nearest neighbor estimator of the DIM. Their approach projects data onto leading eigenvectors of a local compactness matrix times the overall covariance, emphasising high-density local structure to produce low-entropy projections useful for clustering and outlier detection.

Method

The authors develop a nearest-neighbor-based estimator for the Density Information Matrix (DIM) and use it to construct a dimension reduction procedure. The core quantity is the matrix $I(\mathcal{X}, k)$I(X,k), which is computed from the $k$k-th and $(k+1)$(k+1)-th nearest neighbor distances and difference vectors within a sample $\mathcal{X}$X. For each point $X_i$Xi​, the $k$k-th and $(k+1)$(k+1)-th neighbors are identified, and the outer product of their difference is normalized by the squared distances. Summing over all points yields an estimate that, under regularity conditions, converges in probability to the population DIM $I(f_X)$I(fX​) as $n\to\infty$n→∞, provided $k(n)\to\infty$k(n)→∞ and $k(n)^{2-p/4}/n^{1-p/4}\to 0$k(n)2−p/4/n1−p/4→0.

The theoretical analysis proceeds in two stages. First, for a fixed point $\mathbf{x}$x, the conditional expectation of the normalized outer product of the $k$k-th and $(k+1)$(k+1)-th nearest neighbor differences is expanded. Using the conditional independence structure of order statistics and a Taylor expansion of the density, the authors show that

decomposes into a leading isotropic term involving $E[1/D_{\mathbf{x},n-1,(k)}^2 + 1/D_{\mathbf{x},n-1,(k+1)}^2]$E[1/Dx,n−1,(k)2​+1/Dx,n−1,(k+1)2​] and a term proportional to $\frac{1}{f_X(\mathbf{x})^2}\nabla f_X(\mathbf{x})\nabla f_X(\mathbf{x})^\prime$fX​(x)21​∇fX​(x)∇fX​(x)′, plus higher-order contributions from the Hessian. Averaging this expression over the sample and using properties of order statistics, the expectation of $I(\mathbf{X}_n, k)$I(Xn​,k) is shown to converge to $I(f_X)$I(fX​), while the variance vanishes under the rate condition on $k(n)$k(n). Lemma 2 provides uniform convergence of the ratio of consecutive neighbor distances, ensuring that the Hessian-dependent bias terms integrate to zero asymptotically.

To improve finite-sample performance, the authors introduce three practical modifications. First, variance is reduced by averaging $I(\mathcal{X}, k)$I(X,k) over a range of $k$k values, defining $I(\mathcal{X}, k_0, k_1) = \frac{1}{k_1 - k_0 + 1}\sum_{k=k_0}^{k_1} I(\mathcal{X}, k)$I(X,k0​,k1​)=k1​−k0​+11​∑k=k0​k1​​I(X,k). Provided both $k_0(n)$k0​(n) and $k_1(n)$k1​(n) satisfy the conditions of Theorem 1, this averaged estimator remains consistent.

Second, a bias adjustment is applied to the spectral decomposition of the averaged estimator. Let $I(\mathcal{X}, k_0, k_1) = \mathbf{U}\mathbf{D}\mathbf{U}^\prime$I(X,k0​,k1​)=UDU′. The diagonal entries of $\mathbf{D}$D are replaced by $\mathbf{D}_{ii}^* = \max\{\mathbf{D}_{ii}, (\mathbf{u}_i^\prime \Sigma_{\mathcal{X}} \mathbf{u}_i + \epsilon)^{-1}\}$Dii∗​=max{Dii​,(ui′​ΣX​ui​+ϵ)−1}, where $\Sigma_{\mathcal{X}}$ΣX​ is the sample covariance matrix and $\epsilon$ϵ a small constant. This correction exploits a known lower bound: for the population DIM, each eigenvalue $\Delta_{ii}$Δii​ satisfies $\Delta_{ii} \ge 1/\mathrm{Var}(\mathbf{v}_i^\prime X)$Δii​≥1/Var(vi′​X), where $\mathbf{v}_i$vi​ is the corresponding eigenvector. The adjusted matrix $I(\mathcal{X}, k_0, k_1)^*$I(X,k0​,k1​)∗ thus respects this bound and converges to $I(f_X)$I(fX​) as well.

Finally, the projection basis is obtained from the matrix product $I(\mathcal{X}, k_0, k_1)^* \Sigma_{\mathcal{X}}$I(X,k0​,k1​)∗ΣX​. Its eigenvectors are orthogonalised via singular value decomposition: if $\mathbf{W}$W contains the eigenvectors, the final projection directions are the columns of $\mathbf{W}^* = \mathbf{W}_u \mathbf{W}_v^\prime$W∗=Wu​Wv′​, where $\mathbf{W}_u$Wu​ and $\mathbf{W}_v$Wv​ are the left and right singular vectors of $\mathbf{W}$W. This step ensures that the projected data retain more of the total variance, improving downstream tasks such as clustering and outlier detection. The overall pipeline thus estimates the DIM from nearest neighbor statistics, refines it through averaging and bias correction, and produces an orthogonalised projection that preserves the structure captured by the DIM.

Experiment

The experiments evaluate the proposed nearest-neighbors DIM (nnDIM) against PCA, robust PCA, LPP, and kDIM as dimension reduction tools for clustering and outlier detection on 45 classification datasets, with estimation accuracy validated on Gaussian data. For clustering, nnDIM is the only method that consistently improves performance across all four clustering algorithms when applied to higher-dimensional data. In outlier detection, nnDIM pairs well with sLOF and Isolation Forest for datasets with one or two inlier classes, though improvements are less conclusive for single outlier class setups.