# Minimum-Distortion Embedding

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

## Key facts

- Cited by 26 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 3 Mar 2021.

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

- [Contrastive and Non-Contrastive Self-Supervised Learning Recover Global and Local Spectral Embedding Methods](https://mlsanity.com/paper/2205.11508/) (2022)
- [Generalized Shape Metrics on Neural Representations](https://mlsanity.com/paper/2110.14739/) (2021)
- [World-GAN: a Generative Model for Minecraft Worlds](https://mlsanity.com/paper/2106.10155/) (2021)
- [Distributional Reduction: Unifying Dimensionality Reduction and Clustering with Gromov-Wasserstein](https://mlsanity.com/paper/2402.02239/) (2024)
- [Asymptotics of Network Embeddings Learned via Subsampling](https://mlsanity.com/paper/2107.02363/) (2021)
- [TLDR: Twin Learning for Dimensionality Reduction](https://mlsanity.com/paper/2110.09455/) (2021)
- [Deep Networks Provably Classify Data on Curves](https://mlsanity.com/paper/2107.14324/) (2021)
- [Privacy-Preserving Diffusion Model Using Homomorphic Encryption](https://mlsanity.com/paper/2403.05794/) (2024)
- [Assessing and improving reliability of neighbor embedding methods: a map-continuity perspective](https://mlsanity.com/paper/2410.16608/) (2024)
- [The Shape of Attraction in UMAP: Exploring the Embedding Forces in Dimensionality Reduction](https://mlsanity.com/paper/2503.09101/) (2025)
- [WiCluster: Passive Indoor 2D/3D Positioning using WiFi without Precise Labels](https://mlsanity.com/paper/2107.01002/) (2021)
- [ChimeraMix: Image Classification on Small Datasets via Masked Feature Mixing](https://mlsanity.com/paper/2202.11616/) (2022)
- [ParaDime: A Framework for Parametric Dimensionality Reduction](https://mlsanity.com/paper/2210.04582/) (2022)
- [Relating tSNE and UMAP to Classical Dimensionality Reduction](https://mlsanity.com/paper/2306.11898/) (2023)
- [The VampPrior Mixture Model](https://mlsanity.com/paper/2402.04412/) (2024)
- [Graph Vertex Embeddings: Distance, Regularization and Community Detection](https://mlsanity.com/paper/2404.10784/) (2024)
- [ClimateSOM: A Visual Analysis Workflow for Climate Ensemble Datasets](https://mlsanity.com/paper/2508.06732/) (2025)
- [FloDR: An invertible dimensionality reduction method based on a normalising flow](https://mlsanity.com/paper/2607.26278/) (2026)
- [A Graphical Model for Fusing Diverse Microbiome Data](https://mlsanity.com/paper/2208.09934/) (2022)
- [Metric Embeddings Beyond Bi-Lipschitz Distortion via Sherali-Adams](https://mlsanity.com/paper/2311.17840/) (2023)
- [Preserving Angles Improves Feature Distillation](https://mlsanity.com/paper/2411.15239/) (2024)
- [Cross-Spectral Body Recognition with Side Information Embedding: Benchmarks on LLCM and Analyzing Range-Induced Occlusions on IJB-MDF](https://mlsanity.com/paper/2506.08953/) (2025)
- [Euclidean Embedding of Data Using Local Distances](https://mlsanity.com/paper/2605.19243/) (2026)
- [A Fixed-Radius Distance-Band Benchmark for Dimensionality-Reduction Fidelity](https://mlsanity.com/paper/2608.21779/) (2026)
- [A Peer-Relative Representation Learning Framework for Energy Inefficiency Identification in Mobile Network Sites](https://mlsanity.com/paper/2609.03809/) (2026)
- [GeoGAE: Scalable Graph-Level Autoencoding via Hyperball Cloud Representations](https://mlsanity.com/paper/2609.35527/) (2026)

## Abstract (arXiv)

We consider the vector embedding problem. We are given a finite set of items, with the goal of assigning a representative vector to each one, possibly under some constraints (such as the collection of vectors being standardized, i.e., having zero mean and unit covariance). We are given data indicating that some pairs of items are similar, and optionally, some other pairs are dissimilar. For pairs of similar items, we want the corresponding vectors to be near each other, and for dissimilar pairs, we want the corresponding vectors to not be near each other, measured in Euclidean distance. We formalize this by introducing distortion functions, defined for some pairs of the items. Our goal is to choose an embedding that minimizes the total distortion, subject to the constraints. We call this the minimum-distortion embedding (MDE) problem. The MDE framework is simple but general. It includes a wide variety of embedding methods, such as spectral embedding, principal component analysis, multidimensional scaling, dimensionality reduction methods (like Isomap and UMAP), force-directed layout, and others. It also includes new embeddings, and provides principled ways of validating historical and new embeddings alike. We develop a projected quasi-Newton method that approximately solves MDE problems and scales to large data sets. We implement this method in PyMDE, an open-source Python package. In PyMDE, users can select from a library of distortion functions and constraints or specify custom ones, making it easy to rapidly experiment with different embeddings. Our software scales to data sets with millions of items and tens of millions of distortion functions. To demonstrate our method, we compute embeddings for several real-world data sets, including images, an academic co-author network, US county demographic data, and single-cell mRNA transcriptomes.