Abstract: The recent framework of compressive statistical learning proposes to design tractable learning algorithms that use only a heavily compressed representation - or sketch - of massive datasets. Compressive K-Means (CKM) is such a method: It aims at estimating the centroids of data clusters from pooled, nonlinear, and random signatures of the learning examples.