Innovation Pursuit: A New Approach To The Subspace Clustering Problem

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.

Publication Date

1-1-2017

Publication Title

34th International Conference on Machine Learning, ICML 2017

Volume

6

Number of Pages

4398-4406

Document Type

Article; Proceedings Paper

Personal Identifier

scopus

Socpus ID

85048528861 (Scopus)

Source API URL

https://api.elsevier.com/content/abstract/scopus_id/85048528861

This document is currently not available here.

Share

COinS