Linear-Time Approximation Scheme for k-Means Clustering of Affine Subspaces

2021/06/27 by Kyungjin Cho, Cho, Kyungjin, Eunjin Oh +1
Computer Science · #Computational Geometry (cs.CG) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #cs.CG #cs.DS

paper · pdf · doi:10.48550/arxiv.2106.14176

arxiv created 2021/06/27 · arxiv updated 2021/06/29

Abstract

In this paper, we present a linear-time approximation scheme for k-means clustering of incomplete data points in d-dimensional Euclidean space. An incomplete data point with Δ>0 unspecified entries is represented as an axis-parallel affine subspaces of dimension Δ. The distance between two incomplete data points is defined as the Euclidean distance between two closest points in the axis-parallel affine subspaces corresponding to the data points. We present an algorithm for k-means clustering of axis-parallel affine subspaces of dimension Δ that yields an (1+ε)-approximate solution in O(nd) time. The constants hidden behind O(⋅) depend only on Δ, ε and k. This improves the O(n² d)-time algorithm by Eiben et al.[SODA'21] by a factor of n.

Related

• EPTAS for k-means Clustering of Affine Subspaces
• Greedy Subspace Clustering
• Dimensionality Reduction for k-Means Clustering and Low Rank Approximation
• The Bane of Low-Dimensionality Clustering
• Faster Coreset Construction for Projective Clustering via Low-Rank Approximation