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.
