Linear-Time Subspace Clustering via Bipartite Graph Modeling

We present a linear-time subspace clustering approach that combines sparse representations and bipartite graph modeling. The signals are modeled as drawn from a union of low-dimensional subspaces, and each signal is represented by a sparse combination of basis elements, termed atoms, which form the...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transaction on neural networks and learning systems 2015-10, Vol.26 (10), p.2234-2246
Main Authors: Adler, Amir, Elad, Michael, Hel-Or, Yacov
Format: Article
Language:English
Subjects:
Bipartite graph
Clustering
Clustering algorithms
Complexity
Complexity theory
Dictionaries
dictionary
face clustering
Graphs
Matrix decomposition
Neural networks
Optimization
Reduction
Representations
Segmentation
Sparse matrices
sparse representation
subspace clustering
Subspaces
temporal video segmentation
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We present a linear-time subspace clustering approach that combines sparse representations and bipartite graph modeling. The signals are modeled as drawn from a union of low-dimensional subspaces, and each signal is represented by a sparse combination of basis elements, termed atoms, which form the columns of a dictionary matrix. The sparse representation coefficients are arranged in a sparse affinity matrix, which defines a bipartite graph of two disjoint sets: (1) atoms and (2) signals. Subspace clustering is obtained by applying low-complexity spectral bipartite graph clustering that exploits the small number of atoms for complexity reduction. The complexity of the proposed approach is linear in the number of signals, thus it can rapidly cluster very large data collections. Performance evaluation of face clustering and temporal video segmentation demonstrates comparable clustering accuracies to state-of-the-art at a significantly lower computational load.
ISSN:2162-237X
2162-2388
DOI:10.1109/TNNLS.2014.2374631