betaFeedback

WorksComputer Science

L1L_1 versus L2L_2 Clustering: When Does the Choice of Norm Matter?

Abstract

We study how well approximation guarantees for clustering under one norm translate into guarantees under another. Specifically, we compare kk-clustering in Rd\mathbb{R}^d under the L1L_1 and L2L_2 objectives, defined as the sums of Manhattan and Euclidean distances, respectively. In the worst case, the elementary relationship between these norms yields a d\sqrt{d} approximation bound, which is already tight for k=2k=2. We therefore investigate whether stronger guarantees are possible in a natural average-case model, where the dataset is arbitrary but the coordinate system is chosen uniformly at random among all orthonormal bases. Our main result shows that, when d=Ω(log⁡k)d=Ω(\log k), with high probability over the random rotation, any ββ-approximate L1L_1 clustering, with optimally chosen centers for its clusters, is also an O(β)O(β)-approximation under the L2L_2 objective. We also establish an expected approximation ratio of O(βmin⁡{d,k2/d})O(β\min\{\sqrt{d},k^{2/d}\}), yielding a dimension-independent bound of O(βlog⁡k/log⁡log⁡k)O(β\sqrt{\log k/\log\log k}). We obtain analogous guarantees in the reverse direction, from L2L_2 to L1L_1. We complement these results with lower bounds of Ω(min⁡{d,k1/d})Ω(\min\{\sqrt{d},k^{1/d}\}) in both directions, showing that our dimension-independent guarantees have asymptotically optimal dependence on kk for constant ββ. Our proofs overcome the dependence of the algorithm's output on the random rotation using geometric projection arguments and small Euclidean coresets. In particular, our results provide guarantees for existing clustering algorithms without requiring their redesign.

Paper details

vlnc:W_xcjk8a99
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
arXiv nonexclusive license
Usage

views · 9

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

ChatGPT 5.6

View statement
Looking for related papers…