# The Curse Revisited: When are Distances Informative for the Ground Truth in Noisy High-Dimensional Data?

arXiv: https://arxiv.org/abs/2109.10569 · HTML: https://mlsanity.com/paper/2109.10569/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 1 of its 39 references that are in the map.
- First posted on arXiv 22 Sep 2021.

## Builds on (most cited first, 1 of 1)

- [UMAP: Uniform Manifold Approximation and Projection for Dimension Reduction](https://mlsanity.com/paper/1802.03426/) (2018)

## Built on by (most cited first, 3 of 3)

- [Interpreting the Curse of Dimensionality from Distance Concentration and Manifold Effect](https://mlsanity.com/paper/2401.00422/) (2023)
- [Topologically Regularized Data Embeddings](https://mlsanity.com/paper/2110.09193/) (2021)
- [Topologically Regularized Data Embeddings](https://mlsanity.com/paper/2301.03338/) (2023)

## Abstract (arXiv)

Distances between data points are widely used in machine learning applications. Yet, when corrupted by noise, these distances -- and thus the models based upon them -- may lose their usefulness in high dimensions. Indeed, the small marginal effects of the noise may then accumulate quickly, shifting empirical closest and furthest neighbors away from the ground truth. In this paper, we exactly characterize such effects in noisy high-dimensional data using an asymptotic probabilistic expression. Previously, it has been argued that neighborhood queries become meaningless and unstable when distance concentration occurs, which means that there is a poor relative discrimination between the furthest and closest neighbors in the data. However, we conclude that this is not necessarily the case when we decompose the data in a ground truth -- which we aim to recover -- and noise component. More specifically, we derive that under particular conditions, empirical neighborhood relations affected by noise are still likely to be truthful even when distance concentration occurs. We also include thorough empirical verification of our results, as well as interesting experiments in which our derived 'phase shift' where neighbors become random or not turns out to be identical to the phase shift where common dimensionality reduction methods perform poorly or well for recovering low-dimensional reconstructions of high-dimensional data with dense noise.