  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.
