Randomized Dimensionality Reduction for Euclidean Maximization and Diversity Measures

Abstract

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.

Tasks

Reproductions