Moderate Dimension Reduction for $k$-Center Clustering
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910027307024384 |
|---|---|
| author | Jiang, Shaofeng H. -C. Krauthgamer, Robert Sapir, Shay |
| author_facet | Jiang, Shaofeng H. -C. Krauthgamer, Robert Sapir, Shay |
| contents | The Johnson-Lindenstrauss (JL) Lemma introduced the concept of dimension reduction via a random linear map, which has become a fundamental technique in many computational settings. For a set of $n$ points in $\mathbb{R}^d$ and any fixed $ε>0$, it reduces the dimension $d$ to $O(\log n)$ while preserving, with high probability, all the pairwise Euclidean distances within factor $1+ε$. Perhaps surprisingly, the target dimension can be lower if one only wishes to preserve the optimal value of a certain problem on the pointset, e.g., Euclidean max-cut or $k$-means. However, for some notorious problems, like diameter (aka furthest pair), dimension reduction via the JL map to below $O(\log n)$ does not preserve the optimal value within factor $1+ε$.
We propose to focus on another regime, of \emph{moderate dimension reduction}, where a problem's value is preserved within factor $α>1$ using target dimension $\tfrac{\log n}{poly(α)}$. We establish the viability of this approach and show that the famous $k$-center problem is $α$-approximated when reducing to dimension $O(\tfrac{\log n}{α^2}+\log k)$. Along the way, we address the diameter problem via the special case $k=1$. Our result extends to several important variants of $k$-center (with outliers, capacities, or fairness constraints), and the bound improves further with the input's doubling dimension.
While our $poly(α)$-factor improvement in the dimension may seem small, it actually has significant implications for streaming algorithms, and easily yields an algorithm for $k$-center in dynamic geometric streams, that achieves $O(α)$-approximation using space $poly(kdn^{1/α^2})$. This is the first algorithm to beat $O(n)$ space in high dimension $d$, as all previous algorithms require space at least $\exp(d)$. Furthermore, it extends to the $k$-center variants mentioned above. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2312_01391 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Moderate Dimension Reduction for $k$-Center Clustering Jiang, Shaofeng H. -C. Krauthgamer, Robert Sapir, Shay Data Structures and Algorithms The Johnson-Lindenstrauss (JL) Lemma introduced the concept of dimension reduction via a random linear map, which has become a fundamental technique in many computational settings. For a set of $n$ points in $\mathbb{R}^d$ and any fixed $ε>0$, it reduces the dimension $d$ to $O(\log n)$ while preserving, with high probability, all the pairwise Euclidean distances within factor $1+ε$. Perhaps surprisingly, the target dimension can be lower if one only wishes to preserve the optimal value of a certain problem on the pointset, e.g., Euclidean max-cut or $k$-means. However, for some notorious problems, like diameter (aka furthest pair), dimension reduction via the JL map to below $O(\log n)$ does not preserve the optimal value within factor $1+ε$. We propose to focus on another regime, of \emph{moderate dimension reduction}, where a problem's value is preserved within factor $α>1$ using target dimension $\tfrac{\log n}{poly(α)}$. We establish the viability of this approach and show that the famous $k$-center problem is $α$-approximated when reducing to dimension $O(\tfrac{\log n}{α^2}+\log k)$. Along the way, we address the diameter problem via the special case $k=1$. Our result extends to several important variants of $k$-center (with outliers, capacities, or fairness constraints), and the bound improves further with the input's doubling dimension. While our $poly(α)$-factor improvement in the dimension may seem small, it actually has significant implications for streaming algorithms, and easily yields an algorithm for $k$-center in dynamic geometric streams, that achieves $O(α)$-approximation using space $poly(kdn^{1/α^2})$. This is the first algorithm to beat $O(n)$ space in high dimension $d$, as all previous algorithms require space at least $\exp(d)$. Furthermore, it extends to the $k$-center variants mentioned above. |
| title | Moderate Dimension Reduction for $k$-Center Clustering |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2312.01391 |