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.
翻译:在分析几何数据集时,有两个重要的优化问题是组合和草图。在这里,组合是指将某些输入量度空间(mm-space)分割成 k 类组的问题,将某些目标函数 f. 切入,另一方面是将某些毫米- 空间相近的问题,由一组 k 点支持的较小空间相近的问题。具体地说,我们定义某些毫米- 空间M 的K- sketch 是一组 k-point mm- space 中M 的近邻, 在一组毫米- 空间的某种距离函数下 。在本文中,我们显示了将某些输入量度空间的量度空间空间(mm- space) 分割成 km- 空间(mm- space) 的问题。我们展示了将某些输入量度空间的普通类别和草图问题之间的双重性。我们提出了一种一般性的方法,将一个组合问题解决方案转化为一个草图问题的解决方案,而反之,成本大致相同。更具体地说,我们得到了以下的组合目标的K- 。 对于量组的目标,我们认为,不同的素描图目标之间的比比比比比似乎比比比比都在一个硬化。