Innovation Pursuit: A New Approach to the Subspace Clustering Problem

Mostafa Rahmani, George Atia
Proceedings of the 34th International Conference on Machine Learning, PMLR 70:2874-2882, 2017.

Abstract

This paper presents a new scalable approach, termed Innovation Pursuit (iPursuit), to the problem of subspace clustering. iPursuit rests on a new geometrical idea whereby each subspace is identified based on its novelty with respect to the other subspaces. The subspaces are identified consecutively by solving a series of simple linear optimization problems, each searching for a direction of innovation in the span of the data. A detailed mathematical analysis is provided establishing sufficient conditions for the proposed approach to correctly cluster the data points. Moreover, the proposed direction search approach can be integrated with spectral clustering to yield a new variant of spectral-clustering-based algorithms. Remarkably, the proposed approach can provably yield exact clustering even when the subspaces have significant intersections. The numerical simulations demonstrate that iPursuit can often outperform the state-of-the-art subspace clustering algorithms – more so for subspaces with significant intersections – along with substantial reductions in computational complexity.

Cite this Paper

BibTeX
@InProceedings{pmlr-v70-rahmani17b, title = {Innovation Pursuit: A New Approach to the Subspace Clustering Problem}, author = {Mostafa Rahmani and George Atia}, booktitle = {Proceedings of the 34th International Conference on Machine Learning}, pages = {2874--2882}, year = {2017}, editor = {Precup, Doina and Teh, Yee Whye}, volume = {70}, series = {Proceedings of Machine Learning Research}, month = {06--11 Aug}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v70/rahmani17b/rahmani17b.pdf}, url = {https://proceedings.mlr.press/v70/rahmani17b.html}, abstract = {This paper presents a new scalable approach, termed Innovation Pursuit (iPursuit), to the problem of subspace clustering. iPursuit rests on a new geometrical idea whereby each subspace is identified based on its novelty with respect to the other subspaces. The subspaces are identified consecutively by solving a series of simple linear optimization problems, each searching for a direction of innovation in the span of the data. A detailed mathematical analysis is provided establishing sufficient conditions for the proposed approach to correctly cluster the data points. Moreover, the proposed direction search approach can be integrated with spectral clustering to yield a new variant of spectral-clustering-based algorithms. Remarkably, the proposed approach can provably yield exact clustering even when the subspaces have significant intersections. The numerical simulations demonstrate that iPursuit can often outperform the state-of-the-art subspace clustering algorithms – more so for subspaces with significant intersections – along with substantial reductions in computational complexity.} }
Endnote
%0 Conference Paper %T Innovation Pursuit: A New Approach to the Subspace Clustering Problem %A Mostafa Rahmani %A George Atia %B Proceedings of the 34th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2017 %E Doina Precup %E Yee Whye Teh %F pmlr-v70-rahmani17b %I PMLR %P 2874--2882 %U https://proceedings.mlr.press/v70/rahmani17b.html %V 70 %X This paper presents a new scalable approach, termed Innovation Pursuit (iPursuit), to the problem of subspace clustering. iPursuit rests on a new geometrical idea whereby each subspace is identified based on its novelty with respect to the other subspaces. The subspaces are identified consecutively by solving a series of simple linear optimization problems, each searching for a direction of innovation in the span of the data. A detailed mathematical analysis is provided establishing sufficient conditions for the proposed approach to correctly cluster the data points. Moreover, the proposed direction search approach can be integrated with spectral clustering to yield a new variant of spectral-clustering-based algorithms. Remarkably, the proposed approach can provably yield exact clustering even when the subspaces have significant intersections. The numerical simulations demonstrate that iPursuit can often outperform the state-of-the-art subspace clustering algorithms – more so for subspaces with significant intersections – along with substantial reductions in computational complexity.
APA
Rahmani, M. & Atia, G.. (2017). Innovation Pursuit: A New Approach to the Subspace Clustering Problem. Proceedings of the 34th International Conference on Machine Learning, in Proceedings of Machine Learning Research 70:2874-2882 Available from https://proceedings.mlr.press/v70/rahmani17b.html.

Related Material