  Two important optimization problems in the analysis of geometric data sets
are clustering and sketching. Here, clustering refers to the problem of
partitioning some input metric measure space (mm-space) into k clusters,
minimizing some objective function f. Sketching, on the other hand, is the
problem of approximating some mm-space by a smaller one supported on a set of k
points. Specifically, we define the k-sketch of some mm-space M to be the
nearest neighbor of M in the set of k-point mm-spaces, under some distance
function \rho on the set of mm-spaces. In this paper, we demonstrate a duality
between general classes of clustering and sketching problems. We present a
general method for efficiently transforming a solution for a clustering problem
to a solution for a sketching problem, and vice versa, with approximately equal
cost. More specifically, we obtain the following results. 1. For metric spaces,
we consider the case where the clustering objective is minimizing the maximum
cluster diameter. We show that the ratio between the sketching and clustering
objectives is constant over compact metric spaces. 2. We extend these results
to the setting of metric measure spaces where we prove that the ratio of
sketching to clustering objectives is bounded both above and below by some
universal constants. In this setting, the clustering objective involves
minimizing various notions of the l_p-diameters} of the clusters. 3. We
consider two competing notions of sketching for mm-spaces, with one of them
being more demanding than the other. These notions arise from two different
definitions of p-Gromov-Wasserstein distance that have appeared in the
literature. We then prove that whereas the gap between these can be arbitrarily
large, in the case of doubling metric spaces the resulting sketching objectives
are polynomially related.
