Moderate Dimension Reduction for $k$-Center Clustering

Abstract

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 $\hat{I}\mu >0$, it reduces the dimension $d$ to $O(\log n)$ while preserving, with high probability, all the pairwise Euclidean distances within factor $1+\hat{I}\mu$. 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+\hat{I}\mu$. We propose to focus on another regime, of \emph{moderate dimension reduction}, where a problem's value is preserved within factor $\hat{I}\pm >1$ using target dimension $\log n/poly(\hat{I}\pm )$. We establish the viability of this approach and show that the famous $k$-center problem is $\hat{I}\pm$-approximated when reducing to dimension $O(\frac{\log n}{\hat{I}{\pm }^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(\hat{I}\pm )$-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(\hat{I}\pm )$-approximation using space $poly(kd{n}^{1/\hat{I}{\pm }^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.

30 pages, initial version appeared in SoCG 2024. v4: added references on robust coresets in section 3. v5: edited section 5 to use Kirszbraun extension theorem. v6: major revision. Main changes: added full description of the streaming algorithm in section 7, edited the section about assignment constraint (now section 5), and added on observation on all pairs alpha-approximation in section 2.1