Randomized Dimensionality Reduction for Euclidean Maximization and Diversity Measures
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910977779302400 |
|---|---|
| author | Gao, Jie Jayaram, Rajesh Kolbe, Benedikt Sapir, Shay Schwiegelshohn, Chris Silwal, Sandeep Waingarten, Erik |
| author_facet | Gao, Jie Jayaram, Rajesh Kolbe, Benedikt Sapir, Shay Schwiegelshohn, Chris Silwal, Sandeep Waingarten, Erik |
| contents | 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 \emph{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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_00165 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Randomized Dimensionality Reduction for Euclidean Maximization and Diversity Measures Gao, Jie Jayaram, Rajesh Kolbe, Benedikt Sapir, Shay Schwiegelshohn, Chris Silwal, Sandeep Waingarten, Erik Data Structures and Algorithms Machine Learning 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 \emph{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. |
| title | Randomized Dimensionality Reduction for Euclidean Maximization and Diversity Measures |
| topic | Data Structures and Algorithms Machine Learning |
| url | https://arxiv.org/abs/2506.00165 |