Provable Clustering of a Union of Linear Manifolds Using Optimal Directions
This provides theoretical insights for researchers in machine learning and data analysis, though it appears incremental as it builds on existing algorithms.
The paper tackles the subspace clustering problem by analyzing the Matrix Factorization based Clustering (MFC) and Innovation Pursuit (iPursuit) algorithms, showing they outperform other methods in challenging scenarios and are robust to intersections between clusters, with performance depending on the distance between innovative components rather than subspace distance.
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.