论文标题
k-subspaces方法的汇聚和恢复保证，用于子空间群集
Convergence and Recovery Guarantees of the K-Subspaces Method for Subspace Clustering
论文作者
论文摘要
K-Subspaces（KSS）方法是用于子空间聚类的K-均值方法的概括。在这项工作中，我们介绍了KSS的本地收敛分析和恢复保证，假设数据是由Semirandom的子空间模型生成的，其中$ n $点是从$ k \ ge 2 $重叠子空间随机采样的。我们表明，如果KSS方法的初始分配位于真实聚类的邻域内，则其收敛速度，并在$θ（\ log \ log \ log n）$迭代范围内找到正确的聚类，具有很高的可能性。此外，我们提出了一种基于阈值的基于内部产品的光谱方法来初始化，并证明它在该邻域中产生了一个点。我们还提出了研究方法的数值结果，以支持我们的理论发展。
The K-subspaces (KSS) method is a generalization of the K-means method for subspace clustering. In this work, we present local convergence analysis and a recovery guarantee for KSS, assuming data are generated by the semi-random union of subspaces model, where $N$ points are randomly sampled from $K \ge 2$ overlapping subspaces. We show that if the initial assignment of the KSS method lies within a neighborhood of a true clustering, it converges at a superlinear rate and finds the correct clustering within $Θ(\log\log N)$ iterations with high probability. Moreover, we propose a thresholding inner-product based spectral method for initialization and prove that it produces a point in this neighborhood. We also present numerical results of the studied method to support our theoretical developments.
