On coreset construction for K-means clustering of flats and hyperplanes

Abstract

Coreset is an important tool to effectively extract information from large amount of data by sampling only a few elements from it, without any substantial loss of the actual information. An -coreset is defined as a weighted set C obtained from an universe X, so that for any solution set Q for a problem (referred to as a query in coreset literature), jCost(X;Q) 􀀀 Cost(C;Q)j Cost(X;Q). Our work is an attempt to generalize the solution provided in the paper “k- Means Clustering of Lines for Big Data” (Marom and Feldman, NIPS, 2019), and explore if it is possible to extend to k-flats in Rd as well. Following the approach used in the paper mentioned, we will attempt at building a deterministic algorithm to compute an -coreset whose size is near logarithmic of the input size for a j-dimensional affine subspace in Rd.