# Provable Clustering of a Union of Linear Manifolds Using Optimal Directions

arXiv: https://arxiv.org/abs/2201.02745 · HTML: https://mlsanity.com/paper/2201.02745/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 16 of its 45 references that are in the map.
- First posted on arXiv 8 Jan 2022.

## Builds on (most cited first, 16 of 16)

- [Deep Subspace Clustering Networks](https://mlsanity.com/paper/1709.02508/) (2017)
- [Learning Latent Subspaces in Variational Autoencoders](https://mlsanity.com/paper/1812.06190/) (2018)
- [Scalable Sparse Subspace Clustering by Orthogonal Matching Pursuit](https://mlsanity.com/paper/1507.01238/) (2015)
- [Noisy Sparse Subspace Clustering](https://mlsanity.com/paper/1309.1233/) (2013)
- [Robust Subspace Clustering via Thresholding](https://mlsanity.com/paper/1307.4891/) (2013)
- [Greedy Feature Selection for Subspace Clustering](https://mlsanity.com/paper/1303.4778/) (2013)
- [Greedy Subspace Clustering](https://mlsanity.com/paper/1410.8864/) (2014)
- [CapProNet: Deep Feature Learning via Orthogonal Projections onto Capsule Subspaces](https://mlsanity.com/paper/1805.07621/) (2018)
- [Correlation Adaptive Subspace Segmentation by Trace Lasso](https://mlsanity.com/paper/1501.04276/) (2015)
- [Innovation Pursuit: A New Approach to Subspace Clustering](https://mlsanity.com/paper/1512.00907/) (2015)
- [Subspace Clustering using Ensembles of K-Subspaces](https://mlsanity.com/paper/1709.04744/) (2017)
- [Hyperplane Clustering Via Dual Principal Component Pursuit](https://mlsanity.com/paper/1706.01604/) (2017)
- [Subspace Clustering via Optimal Direction Search](https://mlsanity.com/paper/1706.03860/) (2017)
- [Certifying Global Optimality of Graph Cuts via Semidefinite Relaxation: A Performance Guarantee for Spectral Clustering](https://mlsanity.com/paper/1806.11429/) (2018)
- [Subspace clustering without knowing the number of clusters: A parameter free approach](https://mlsanity.com/paper/1909.04406/) (2019)
- [Provable Data Clustering via Innovation Search](https://mlsanity.com/paper/2108.06888/) (2021)

## Abstract (arXiv)

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.