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 $\Theta(\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.
翻译:K子空间( KSS) 方法是子空间群集K 值法的概括化方法。 在这项工作中, 我们提出本地趋同分析和KSS的回收保证, 假设数据是由子空间半随机结合模型生成的, 该模型的点数随机抽样来自$K\ge 2美元重叠的子空间。 我们显示, 如果KSS 方法的初始分配是在真实集聚的附近, 它会以超级线性速率聚合, 发现在$\theta(\log\log\log nlog)$的迭代中找到正确的组合值, 概率很高。 此外, 我们提出了基于内产品光谱的临界方法, 用于初始化, 并证明它在这个附近产生点 。 我们还介绍了所研究方法的数值结果, 以支持我们的理论发展 。