论文标题
草图半决赛程序，以更快的聚类
Sketching semidefinite programs for faster clustering
论文作者
论文摘要
许多聚类问题通过半决赛编程享受解决方案。这种静脉的理论结果经常考虑使用种植的聚类和信号强度概念的数据，以便在信号强度足够大的情况下，半决赛程序可以精确地恢复种植的聚类。在实践中，众所周知，半决赛程序很慢，因此欢迎加速。在本文中，我们展示了如何绘制一个流行的半聚集问题，称为最小分配问题，我们的分析支持一个元主张，即当有更多信号时，群集任务在计算方面较小。
Many clustering problems enjoy solutions by semidefinite programming. Theoretical results in this vein frequently consider data with a planted clustering and a notion of signal strength such that the semidefinite program exactly recovers the planted clustering when the signal strength is sufficiently large. In practice, semidefinite programs are notoriously slow, and so speedups are welcome. In this paper, we show how to sketch a popular semidefinite relaxation of a graph clustering problem known as minimum bisection, and our analysis supports a meta-claim that the clustering task is less computationally burdensome when there is more signal.
