# Provable Data Clustering via Innovation Search

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 10 of its 33 references that are in the map.
- First posted on arXiv 16 Aug 2021.

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

- [Deep Subspace Clustering Networks](https://mlsanity.com/paper/1709.02508/) (2017)
- [Scalable Sparse Subspace Clustering by Orthogonal Matching Pursuit](https://mlsanity.com/paper/1507.01238/) (2015)
- [Oracle Based Active Set Algorithm for Scalable Elastic Net Subspace Clustering](https://mlsanity.com/paper/1605.02633/) (2016)
- [Noisy Sparse Subspace Clustering](https://mlsanity.com/paper/1309.1233/) (2013)
- [Robust Subspace Clustering via Thresholding](https://mlsanity.com/paper/1307.4891/) (2013)
- [Coherence Pursuit: Fast, Simple, and Robust Principal Component Analysis](https://mlsanity.com/paper/1609.04789/) (2016)
- [Innovation Pursuit: A New Approach to Subspace Clustering](https://mlsanity.com/paper/1512.00907/) (2015)
- [Subspace Clustering via Optimal Direction Search](https://mlsanity.com/paper/1706.03860/) (2017)
- [Recovery of Coherent Data via Low-Rank Dictionary Pursuit](https://mlsanity.com/paper/1404.4032/) (2014)
- [Subspace Clustering through Sub-Clusters](https://mlsanity.com/paper/1811.06580/) (2018)

## Built on by (most cited first, 1 of 1)

- [Provable Clustering of a Union of Linear Manifolds Using Optimal Directions](https://mlsanity.com/paper/2201.02745/) (2022)

## Abstract (arXiv)

This paper studies the subspace clustering problem in which data points collected from high-dimensional ambient space lie in a union of linear subspaces. Subspace clustering becomes challenging when the dimension of intersection between subspaces is large and most of the self-representation based methods are sensitive to the intersection between the span of clusters. In sharp contrast to the self-representation based methods, a recently proposed clustering method termed Innovation Pursuit, computed a set of optimal directions (directions of innovation) to build the adjacency matrix. This paper focuses on the Innovation Pursuit Algorithm to shed light on its impressive performance when the subspaces are heavily intersected. It is shown that in contrast to most of the existing methods which require the subspaces to be sufficiently incoherent with each other, Innovation Pursuit only requires the innovative components of the subspaces to be sufficiently incoherent with each other. These new sufficient conditions allow the clusters to be strongly close to each other. Motivated by the presented theoretical analysis, a simple yet effective projection based technique is proposed which we show with both numerical and theoretical results that it can boost the performance of Innovation Pursuit.