# Randomized Dimensionality Reduction for Euclidean Maximization and Diversity Measures

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 19 of its 49 references that are in the map.
- First posted on arXiv 30 May 2025.

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

- [Reliable Fidelity and Diversity Metrics for Generative Models](https://mlsanity.com/paper/2002.09797/) (2020)
- [Turning Big data into tiny data: Constant-size coresets for k-means, PCA and projective clustering](https://mlsanity.com/paper/1807.04518/) (2018)
- [Do Not Let Privacy Overbill Utility: Gradient Embedding Perturbation for Private Learning](https://mlsanity.com/paper/2102.12677/) (2021)
- [Performance of Johnson-Lindenstrauss Transform for k-Means and k-Medians Clustering](https://mlsanity.com/paper/1811.03195/) (2018)
- [Dimensionality Reduction for k-Means Clustering and Low Rank Approximation](https://mlsanity.com/paper/1410.6801/) (2014)
- [Diversity in Machine Learning](https://mlsanity.com/paper/1807.01477/) (2018)
- [On the Local Structure of Stable Clustering Instances](https://mlsanity.com/paper/1701.08423/) (2017)
- [Dimensionality Reduction for Wasserstein Barycenter](https://mlsanity.com/paper/2110.08991/) (2021)
- [Efficiently Computing Similarities to Private Datasets](https://mlsanity.com/paper/2403.08917/) (2024)
- [Randomized Dimensionality Reduction for Facility Location and Single-Linkage Clustering](https://mlsanity.com/paper/2107.01804/) (2021)
- [The Johnson-Lindenstrauss Lemma for Clustering and Subspace Approximation: From Coresets to Dimension Reduction](https://mlsanity.com/paper/2205.00371/) (2022)
- [Core-sets for Fair and Diverse Data Summarization](https://mlsanity.com/paper/2310.08122/) (2023)
- [Improved Diversity Maximization Algorithms for Matching and Pseudoforest](https://mlsanity.com/paper/2307.04329/) (2023)
- [Streaming Euclidean Max-Cut: Dimension vs Data Reduction](https://mlsanity.com/paper/2211.05293/) (2022)
- [Moderate Dimension Reduction for k-Center Clustering](https://mlsanity.com/paper/2312.01391/) (2023)
- [Near-linear time approximation schemes for Steiner tree and forest in low-dimensional spaces](https://mlsanity.com/paper/1904.03611/) (2019)
- [Efficient PTAS for the Maximum Traveling Salesman Problem in a Metric Space of Fixed Doubling Dimension](https://mlsanity.com/paper/2012.08379/) (2020)
- [Intersecting diametral balls induced by a geometric graph](https://mlsanity.com/paper/2108.09795/) (2021)
- [Near-Optimal Dimension Reduction for Facility Location](https://mlsanity.com/paper/2411.05432/) (2024)

## Abstract (arXiv)

Randomized dimensionality reduction is a widely-used algorithmic technique for speeding up large-scale Euclidean optimization problems. In this paper, we study dimension reduction for a variety of maximization problems, including max-matching, max-spanning tree, max TSP, as well as various measures for dataset diversity. For these problems, we show that the effect of dimension reduction is intimately tied to the doubling dimension λX of the underlying dataset X -- a quantity measuring intrinsic dimensionality of point sets. Specifically, we prove that a target dimension of O(λX) suffices to approximately preserve the value of any near-optimal solution,which we also show is necessary for some of these problems. This is in contrast to classical dimension reduction results, whose dependence increases with the dataset size |X|. We also provide empirical results validating the quality of solutions found in the projected space, as well as speedups due to dimensionality reduction.