mlsanityData to 14 Oct 2026

Randomized Dimensionality Reduction for Euclidean Maximization and Diversity Measures

arXiv 2506.00165 ↗First posted 30 May 2025cs.DS cs.LGcited by 0

Not on the map. Why?

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.

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

19 of 49 references.

References · 19

  1. 2020Reliable Fidelity and Diversity Metrics for Generative Modelscited by 434
  2. 2018Turning Big data into tiny data: Constant-size coresets for k-means, PCA and projective clusteringcited by 94
  3. 2021Do Not Let Privacy Overbill Utility: Gradient Embedding Perturbation for Private Learningcited by 86
  4. 2018Performance of Johnson-Lindenstrauss Transform for k-Means and k-Medians Clusteringcited by 53
  5. 2014Dimensionality Reduction for k-Means Clustering and Low Rank Approximationcited by 48
  6. 2018Diversity in Machine Learningcited by 48
  7. 2017On the Local Structure of Stable Clustering Instancescited by 13
  8. 2021Dimensionality Reduction for Wasserstein Barycentercited by 13
  9. 2024Efficiently Computing Similarities to Private Datasetscited by 9
  10. 2021Randomized Dimensionality Reduction for Facility Location and Single-Linkage Clusteringcited by 6
  11. 2022The Johnson-Lindenstrauss Lemma for Clustering and Subspace Approximation: From Coresets to Dimension Reductioncited by 5
  12. 2023Core-sets for Fair and Diverse Data Summarizationcited by 4
7 more
  1. 2023Improved Diversity Maximization Algorithms for Matching and Pseudoforestcited by 3
  2. 2022Streaming Euclidean Max-Cut: Dimension vs Data Reductioncited by 2
  3. 2023Moderate Dimension Reduction for k-Center Clusteringcited by 2
  4. 2019Near-linear time approximation schemes for Steiner tree and forest in low-dimensional spacescited by 1
  5. 2020Efficient PTAS for the Maximum Traveling Salesman Problem in a Metric Space of Fixed Doubling Dimensioncited by 1
  6. 2021Intersecting diametral balls induced by a geometric graphcited by 1
  7. 2024Near-Optimal Dimension Reduction for Facility Locationcited by 1

Built on by

Not cited yet.