论文标题
使用最佳方向的线性歧管结合的可证明的聚类
Provable Clustering of a Union of Linear Manifolds Using Optimal Directions
论文作者
论文摘要
本文着重于基于矩阵分解的聚类（MFC）方法，该方法是子空间聚类问题的少数封闭形式算法之一。尽管在许多挑战性的情况下，MFC简单，封闭形式和计算有效的效果还是可以胜过其他复杂的子空间聚类方法。我们揭示了MFC与创新追踪（IPURSUIT）算法之间的连接，该算法被证明能够超越其他基于光谱聚类的方法具有明显的边距，尤其是当簇的跨度接近时。提出了一项新的理论研究，阐明了这两种算法（MFC/ipursuit）的关键性能因素，并且表明这两种算法对于簇之间的跨度之间的显着交集都可以鲁棒。重要的是，与其他算法的理论保证相反，这些算法强调子空间之间的距离是关键绩效因素，而在没有进行创新假设的情况下，这表明MFC/IPURSUIT的性能主要取决于簇的创新组件之间的距离。
This paper focuses on the Matrix Factorization based Clustering (MFC) method which is one of the few closed form algorithms for the subspace clustering problem. Despite being simple, closed-form, and computation-efficient, MFC can outperform the other sophisticated subspace clustering methods in many challenging scenarios. We reveal the connection between MFC and the Innovation Pursuit (iPursuit) algorithm which was shown to be able to outperform the other spectral clustering based methods with a notable margin especially when the span of clusters are close. A novel theoretical study is presented which sheds light on the key performance factors of both algorithms (MFC/iPursuit) and it is shown that both algorithms can be robust to notable intersections between the span of clusters. Importantly, in contrast to the theoretical guarantees of other algorithms which emphasized on the distance between the subspaces as the key performance factor and without making the innovation assumption, it is shown that the performance of MFC/iPursuit mainly depends on the distance between the innovative components of the clusters.
