  We consider the problem of computing the k-means centers for a large
high-dimensional dataset in the context of edge-based machine learning, where
data sources offload machine learning computation to nearby edge servers.
k-Means computation is fundamental to many data analytics, and the capability
of computing provably accurate k-means centers by leveraging the computation
power of the edge servers, at a low communication and computation cost to the
data sources, will greatly improve the performance of these analytics. We
propose to let the data sources send small summaries, generated by joint
dimensionality reduction (DR) and cardinality reduction (CR), to support
approximate k-means computation at reduced complexity and communication cost.
By analyzing the complexity, the communication cost, and the approximation
error of k-means algorithms based on state-of-the-art DR/CR methods, we show
that: (i) it is possible to achieve a near-optimal approximation at a
near-linear complexity and a constant or logarithmic communication cost, (ii)
the order of applying DR and CR significantly affects the complexity and the
communication cost, and (iii) combining DR/CR methods with a properly
configured quantizer can further reduce the communication cost without
compromising the other performance metrics. Our findings are validated through
experiments based on real datasets.
