# Dimensionality Reduction has Quantifiable Imperfections: Two Geometric Bounds

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 31 Oct 2018.

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

- [Theoretical Foundations of t-SNE for Visualizing High-Dimensional Clustered Data](https://mlsanity.com/paper/2105.07536/) (2021)

## Abstract (arXiv)

In this paper, we investigate Dimensionality reduction (DR) maps in an information retrieval setting from a quantitative topology point of view. In particular, we show that no DR maps can achieve perfect precision and perfect recall simultaneously. Thus a continuous DR map must have imperfect precision. We further prove an upper bound on the precision of Lipschitz continuous DR maps. While precision is a natural measure in an information retrieval setting, it does not measure `how' wrong the retrieved data is. We therefore propose a new measure based on Wasserstein distance that comes with similar theoretical guarantee. A key technical step in our proofs is a particular optimization problem of the L2-Wasserstein distance over a constrained set of distributions. We provide a complete solution to this optimization problem, which can be of independent interest on the technical side.