【ICML2021】基于子空间的随机几何图并集的谱方法理论

谱方法是对子空间并集附近的数据点进行聚类的一种常用方法，称为子空间聚类。典型的用法是先构造一个随机几何图，然后用谱方法对图进行聚类，得到聚类结果。后一步被称为光谱聚类。据我们所知，尽管在基于谱方法的子空间聚类中这两个步骤都很重要，但现有的理论结果都集中在构建图的第一步，而忽略了通过谱聚类纠正错误连接的最后一步。本文首次建立了一个理论来证明这种方法的有效性，在此理论中，我们通过分析在广泛使用的半随机模型下的一个简化算法来论证谱聚类的机理。在此基础上，我们证明了子空间聚类在相当广泛的条件下的有效性。本文的见解和分析技术也可能对其他随机图问题有启示。

http://proceedings.mlr.press/v139/li21f/li21f.pdf