Randomized Dimensionality Reduction for Euclidean Maximization and Diversity Measures
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} $\lambda_X$ of the underlying dataset $X$ -- a quantity measuring intrinsic dimensionality of point sets. Specifically, we prove that a target dimension of $O(\lambda_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.
Code (0)
등록된 구현이 없습니다.
Tasks
Dimensionality ReductionDiversitySimilar Papers 제목 키워드 기반
Linear Dimensionality Reduction in Linear Time: Johnson-Lindenstrauss-type Guarantees for Random Subspace
We consider the problem of efficient randomized dimensionality reduction with norm-preservation guarantees. Specifically we prove data-dependent Johnson-Lindenstrauss-type geometry preservation guarantees for Ho's random…
Dimensionality ReductionRandomized ICA and LDA Dimensionality Reduction Methods for Hyperspectral Image Classification
Dimensionality reduction is an important step in processing the hyperspectral images (HSI) to overcome the curse of dimensionality problem. Linear dimensionality reduction methods such as Independent component analysis (…
Dimensionality ReductionGeneral ClassificationHyperspectral Image Classificationimage-classification+1FibeRed: Fiberwise Dimensionality Reduction of Topologically Complex Data with Vector Bundles
Datasets with non-trivial large scale topology can be hard to embed in low-dimensional Euclidean space with existing dimensionality reduction algorithms. We propose to model topologically complex datasets using vector bu…
Dimensionality ReductionProbabilistic Geometric Principal Component Analysis with application to neural data
Dimensionality reduction is critical across various domains of science including neuroscience. Probabilistic Principal Component Analysis (PPCA) is a prominent dimensionality reduction method that provides a probabilisti…
Dimensionality ReductionnSimplex Zen: A Novel Dimensionality Reduction for Euclidean and Hilbert Spaces
Dimensionality reduction techniques map values from a high dimensional space to one with a lower dimension. The result is a space which requires less physical memory and has a faster distance calculation. These technique…
Dimensionality Reduction