0-sparse subspace clustering

Yingzhen Yang, Jiashi Feng, Nebojsa Jojic, Jianchao Yang, Thomas S. Huang

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Subspace clustering methods with sparsity prior, such as Sparse Subspace Clustering (SSC) [1], are effective in partitioning the data that lie in a union of subspaces. Most of those methods require certain assumptions, e.g. independence or disjointness, on the subspaces. These assumptions are not guaranteed to hold in practice and they limit the application of existing sparse subspace clustering methods. In this paper, we propose ℓ0-induced sparse subspace clustering (ℓ0-SSC). In contrast to the required assumptions, such as independence or disjointness, on subspaces for most existing sparse subspace clustering methods, we prove that subspace-sparse representation, a key element in subspace clustering, can be obtained by ℓ0-SSC for arbitrary distinct underlying subspaces almost surely under the mild i.i.d. assumption on the data generation. We also present the "no free lunch" theorem that obtaining the subspace representation under our general assumptions can not be much computationally cheaper than solving the corresponding ℓ0 problem of ℓ0-SSC. We develop a novel approximate algorithm named Approximate ℓ0-SSC (Aℓ0-SSC) that employs proximal gradient descent to obtain a sub-optimal solution to the optimization problem of ℓ0-SSC with theoretical guarantee, and the sub-optimal solution is used to build a sparse similarity matrix for clustering. Extensive experimental results on various data sets demonstrate the superiority of Aℓ0-SSC compared to other competing clustering methods.

Original languageEnglish (US)
Title of host publicationComputer Vision - 14th European Conference, ECCV 2016, Proceedings
EditorsBastian Leibe, Nicu Sebe, Max Welling, Jiri Matas
PublisherSpringer-Verlag
Pages731-747
Number of pages17
ISBN (Print)9783319464749
DOIs
StatePublished - Jan 1 2016
Event14th European Conference on Computer Vision, ECCV 2016 - Amsterdam, Netherlands
Duration: Oct 11 2016Oct 14 2016

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume9906 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other14th European Conference on Computer Vision, ECCV 2016
CountryNetherlands
CityAmsterdam
Period10/11/1610/14/16

Keywords

  • Proximal gradient descent
  • Sparse subspace clustering

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'ℓ<sup>0</sup>-sparse subspace clustering'. Together they form a unique fingerprint.

  • Cite this

    Yang, Y., Feng, J., Jojic, N., Yang, J., & Huang, T. S. (2016). 0-sparse subspace clustering. In B. Leibe, N. Sebe, M. Welling, & J. Matas (Eds.), Computer Vision - 14th European Conference, ECCV 2016, Proceedings (pp. 731-747). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9906 LNCS). Springer-Verlag. https://doi.org/10.1007/978-3-319-46475-6_45