Timezone: »
Poster
Randomized Dimensionality Reduction for Facility Location and Single-Linkage Clustering
Shyam Narayanan · Sandeep Silwal · Piotr Indyk · Or Zamir
Random dimensionality reduction is a versatile tool for speeding up algorithms for high-dimensional problems. We study its application to two clustering problems: the facility location problem, and the single-linkage hierarchical clustering problem, which is equivalent to computing the minimum spanning tree. We show that if we project the input pointset $X$ onto a random $d = O(d_X)$-dimensional subspace (where $d_X$ is the doubling dimension of $X$), then the optimum facility location cost in the projected space approximates the original cost up to a constant factor. We show an analogous statement for minimum spanning tree, but with the dimension $d$ having an extra $\log \log n$ term and the approximation factor being arbitrarily close to $1$. Furthermore, we extend these results to approximating {\em solutions} instead of just their {\em costs}. Lastly, we provide experimental results to validate the quality of solutions and the speedup due to the dimensionality reduction. Unlike several previous papers studying this approach in the context of $k$-means and $k$-medians, our dimension bound does not depend on the number of clusters but only on the intrinsic dimensionality of $X$.
Author Information
Shyam Narayanan (Massachusetts Institute of Technology)
Sandeep Silwal (MIT)
Piotr Indyk (MIT)
Or Zamir (Tel Aviv University)
Related Events (a corresponding poster, oral, or spotlight)
-
2021 Spotlight: Randomized Dimensionality Reduction for Facility Location and Single-Linkage Clustering »
Thu. Jul 22nd 02:40 -- 02:45 PM Room
More from the Same Authors
-
2021 : Adversarial Robustness of Streaming Algorithms through Importance Sampling »
Vladimir Braverman · Avinatan Hasidim · Yossi Matias · Mariano Schain · Sandeep Silwal · Samson Zhou -
2023 : k-Means Clustering with Distance-Based Privacy »
Alessandro Epasto · Vahab Mirrokni · Shyam Narayanan · Peilin Zhong -
2023 Poster: Data Structures for Density Estimation »
Anders Aamand · Alexandr Andoni · Justin Chen · Piotr Indyk · Shyam Narayanan · Sandeep Silwal -
2022 Poster: Faster Fundamental Graph Algorithms via Learned Predictions »
Justin Chen · Sandeep Silwal · Ali Vakilian · Fred Zhang -
2022 Poster: Hardness and Algorithms for Robust and Sparse Optimization »
Eric Price · Sandeep Silwal · Samson Zhou -
2022 Spotlight: Hardness and Algorithms for Robust and Sparse Optimization »
Eric Price · Sandeep Silwal · Samson Zhou -
2022 Spotlight: Faster Fundamental Graph Algorithms via Learned Predictions »
Justin Chen · Sandeep Silwal · Ali Vakilian · Fred Zhang -
2022 Poster: Tight and Robust Private Mean Estimation with Few Users »
Shyam Narayanan · Vahab Mirrokni · Hossein Esfandiari -
2022 Oral: Tight and Robust Private Mean Estimation with Few Users »
Shyam Narayanan · Vahab Mirrokni · Hossein Esfandiari -
2022 Poster: Streaming Algorithms for Support-Aware Histograms »
Justin Chen · Piotr Indyk · Tal Wagner -
2022 Spotlight: Streaming Algorithms for Support-Aware Histograms »
Justin Chen · Piotr Indyk · Tal Wagner -
2021 : Contributed Talk #8 »
Sandeep Silwal -
2021 Poster: Faster Kernel Matrix Algebra via Density Estimation »
Arturs Backurs · Piotr Indyk · Cameron Musco · Tal Wagner -
2021 Spotlight: Faster Kernel Matrix Algebra via Density Estimation »
Arturs Backurs · Piotr Indyk · Cameron Musco · Tal Wagner -
2020 Poster: Scalable Nearest Neighbor Search for Optimal Transport »
Arturs Backurs · Yihe Dong · Piotr Indyk · Ilya Razenshteyn · Tal Wagner -
2019 Poster: Composable Core-sets for Determinant Maximization: A Simple Near-Optimal Algorithm »
Sepideh Mahabadi · Piotr Indyk · Shayan Oveis Gharan · Alireza Rezaei -
2019 Poster: Scalable Fair Clustering »
Arturs Backurs · Piotr Indyk · Krzysztof Onak · Baruch Schieber · Ali Vakilian · Tal Wagner -
2019 Oral: Scalable Fair Clustering »
Arturs Backurs · Piotr Indyk · Krzysztof Onak · Baruch Schieber · Ali Vakilian · Tal Wagner -
2019 Oral: Composable Core-sets for Determinant Maximization: A Simple Near-Optimal Algorithm »
Sepideh Mahabadi · Piotr Indyk · Shayan Oveis Gharan · Alireza Rezaei