The Johnson-Lindenstrauss Lemma for Clustering and Subspace Approximation: From Coresets to Dimension Reduction

We study the effect of Johnson-Lindenstrauss transforms in various projective clustering problems, generalizing recent results which only applied to center-based clustering [MMR19]. We ask the general question: for a Euclidean optimization problem and an accuracy parameter ε ∈ (0, 1), what is the smallest target dimension t ∈ N such that a Johnson-Lindenstrauss transform Π : R d → R t preserves the cost of the optimal solution up to a (1+ε)-factor. We give a new technique which uses coreset constructions to analyze the effect of the Johnson-Lindenstrauss transform. Our technique, in addition applying to center-based clustering, improves on (or is the first to address) other Euclidean optimization problems, including:

• For (k, z)-subspace approximation: we show that t = Õ(zk 2 /ε 3 ) suffices, whereas the prior best bound, of O(k/ε 2 ), only applied to the case z = 2 [CEM + 15].

• For (k, z)-flat approximation: we show t = Õ(zk 2 /ε 3 ) suffices, completely removing the dependence on n from the prior bound Õ(zk 2 log n/ε 3 ) of [KR15].

• For (k, z)-line approximation: we show t = O((k log log n + z + log(1/ε))/ε 3 ) suffices, and ours is the first to give any dimension reduction result.