Innovation Pursuit: A New Approach to Subspace Clustering

Abstract

In subspace clustering, a group of data points belonging to a union of subspaces are assigned membership to their respective subspaces. This paper presents a new approach dubbed Innovation Pursuit (iPursuit) to the problem of subspace clustering using a new geometrical idea whereby subspaces are identified based on their relative novelties. We present two frameworks in which the idea of innovation pursuit is used to distinguish the subspaces. Underlying the first framework is an iterative method that finds the subspaces consecutively by solving a series of simple linear optimization problems, each searching for a direction of innovation in the span of the data potentially orthogonal to all subspaces except for the one to be identified in one step of the algorithm. A detailed mathematical analysis is provided establishing sufficient conditions for iPursuit to correctly cluster the data. The proposed approach can provably yield exact clustering even when the subspaces have significant intersections. It is shown that the complexity of the iterative approach scales only linearly in the number of data points and subspaces, and quadratically in the dimension of the subspaces. The second framework integrates iPursuit with spectral clustering to yield a new variant of spectral-clustering-based algorithms. The numerical simulations with both real and synthetic data demonstrate that iPursuit can often outperform the state-of-the-art subspace clustering algorithms, more so for subspaces with significant intersections, and that it significantly improves the state-of-the-art result for subspace-segmentation-based face clustering.

References in corpus (7)

• Coherence Pursuit: Fast, Simple, and Robust Principal Component Analysis
• Exact Recovery of Sparsely-Used Dictionaries
• Randomized Robust Subspace Recovery for High Dimensional Data Matrices
• Greedy Subspace Clustering
• Innovation Pursuit: A New Approach to Subspace Clustering
• Spatial Random Sampling: A Structure-Preserving Data Sketching Tool
• Subspace Clustering via Optimal Direction Search

Cited by in corpus (21)

• Coherence Pursuit: Fast, Simple, and Robust Principal Component Analysis
• Non-Intrusive Energy Disaggregation Using Non-negative Matrix Factorization with Sum-to-k Constraint
• An Overview of Robust Subspace Recovery
• Randomized Robust Subspace Recovery for High Dimensional Data Matrices
• Robust Subspace Clustering with Compressed Data
• Sketched Subspace Clustering
• Innovation Pursuit: A New Approach to Subspace Clustering
• Simultaneous Subspace Clustering and Cluster Number Estimating based on Triplet Relationship
• Subspace clustering without knowing the number of clusters: A parameter free approach
• Evolutionary Self-Expressive Models for Subspace Clustering
• Subspace Clustering via Optimal Direction Search
• Closed-Form, Provable, and Robust PCA via Leverage Statistics and Innovation Search
• Low Rank Matrix Recovery with Simultaneous Presence of Outliers and Sparse Corruption
• Revisiting data augmentation for subspace clustering
• Minimal Sample Subspace Learning: Theory and Algorithms
• Outlier Detection and Data Clustering via Innovation Search
• Robust and Scalable Column/Row Sampling from Corrupted Big Data
• Low-Rank Subspace Representation from Optimal Coded-Aperture for Unsupervised Classification of Hyperspectral Imagery
• Joint Dictionary Learning for Example-based Image Super-resolution
• Image Segmentation Using Overlapping Group Sparsity
• Provable Data Clustering via Innovation Search