The Johnson-Lindenstrauss Lemma for Clustering and Subspace Approximation: From Coresets to Dimension Reduction
Moses Charika, Erik Waingarten · Society for Industrial and Applied Mathematics eBooks · 2025
We study the effect of Johnson-Lindenstrauss transforms in various projective clustering problems, generalizing results which only applied to center-based clustering [40]. We ask the general question: for a Euclidean optimization problem and an accuracy parameter ε ∈ (0,1), what is the smallest target dimension t ∈ ℕ such that a Johnson-Lindenstrauss transform Π : ℝd → ℝ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: