Randomized Dimensionality Reduction for Euclidean Maximization and Diversity Measures
Jie Gao, Rajesh Jayaram, Benedikt Kolbe, Shay Sapir, Chris Schwiegelshohn, Sandeep Silwal, Erik Waingarten
Abstract
Randomized dimensionality reduction is a widelyused algorithmic technique for speeding up largescale 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.
Ask Lune
Know this paper in minutes, not an afternoon.
Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.
Lineage
Builds on11
- Reliable Fidelity and Diversity Metrics for Generative ModelsMuhammad Ferjad Naeem, Seong Joon Oh, Youngjung Uh, Yunjey Choi et al.ICML 2020 · 553 citations
- Do not Let Privacy Overbill Utility: Gradient Embedding Perturbation for Private LearningDa Yu, Huishuai Zhang, Wei Chen, Tie-Yan LiuICLR 2021 · 133 citations
- Dimensionality Reduction for Wasserstein BarycenterZachary Izzo, Sandeep Silwal, Samson ZhouNeurIPS 2021 · 25 citations
- Core-sets for Fair and Diverse Data SummarizationSepideh Mahabadi, Stojan TrajanovskiNeurIPS 2023 · 16 citations
- Randomized Dimensionality Reduction for Facility Location and Single-Linkage ClusteringShyam Narayanan, Sandeep Silwal, Piotr Indyk, Or ZamirICML 2021 · 16 citations
Related papers
- Streaming Euclidean Max-Cut: Dimension vs Data ReductionXiaoyu Chen, Shaofeng H.-C. Jiang, Robert KrauthgamerSTOC 2023 · 4 citations
- Dimensionality Reduction for the Sum-of-Distances MetricZhili Feng, Praneeth Kacham, David P. WoodruffICML 2021 · 12 citations
- Graph-Based Algorithms for Diverse Similarity SearchPiyush Anand, Piotr Indyk, Ravishankar Krishnaswamy, Sepideh Mahabadi et al.ICML 2025
- Embedding Probability Distributions into Low Dimensional ℓ1: Tree Ising Models via Truncated MetricsMoses Charikar, Spencer Compton, Chirag PabbarajuSODA 2025
- Random-projection ensemble dimension reductionWenxing Zhou, Timothy I. CanningsICLR 2026
