通过降低维度加速大规模欧氏优化，关键依赖数据内在维度。
Randomized Dimensionality Reduction for Euclidean Maximization and Diversity Measures
- 基于数据集的加倍维数设计降维方案，更精准控制精度损失。
- 目标维度仅需 O(λ_X) 即可近似保持最优解值，且对部分问题必要。
- 适用于大数据集的匹配、生成树、旅行商等最大值问题，适合算法工程师。
随机降维是加速大规模欧氏优化问题的常用技术。本文研究了多种最大化问题（如最大匹配、最大生成树、最大TSP）及数据集多样性度量中的降维效果。我们发现，降维性能与数据集X的加倍维数λ_X密切相关——该指标衡量点集的内在维度。具体而言，我们证明目标维度O(λ_X)足以近似保持任意近似最优解的值，且对某些问题此下界必要。这与经典降维结果（依赖|X|增长）形成对比。我们还提供了实证结果，验证投影空间中解的质量及降维带来的提速效果。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。