Robust low-rank subspace segmentation with semidefinite guarantees

Yuzhao Ni, Ju Sun, Xiaotong Yuan, Shuicheng Yan, Loong Fah Cheong

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

46 Scopus citations

Abstract

Recently there is a line of research work proposing to employ Spectral Clustering (SC) to segment (group)1\ high-dimensional structural data such as those (approximately) lying on subspaces2 or low-dimensional manifolds. By learning the affinity matrix in the form of sparse reconstruction, techniques proposed in this vein often considerably boost the performance in subspace settings where traditional SC can fail. Despite the success, there are fundamental problems that have been left unsolved: the spectrum property of the learned affinity matrix cannot be gauged in advance, and there is often one ugly symmetrization step that post-processes the affinity for SC input. Hence we advocate to enforce the symmetric positive semi definite constraint explicitly during learning (Low-Rank Representation with Positive Semi Definite constraint, or LRR-PSD), and show that factually it can be solved in an exquisite scheme efficiently instead of general-purpose SDP solvers that usually scale up poorly. We provide rigorous mathematical derivations to show that, in its canonical form, LRR-PSD is equivalent to the recently proposed Low-Rank Representation (LRR) scheme[1], and hence offer theoretic and practical insights to both LRR-PSD and LRR, inviting future research. As per the computational cost, our proposal is at most comparable to that of LRR, if not less. We validate our theoretic analysis and optimization scheme by experiments on both synthetic and real data sets.

Original languageEnglish (US)
Title of host publicationProceedings - 10th IEEE International Conference on Data Mining Workshops, ICDMW 2010
Pages1179-1188
Number of pages10
DOIs
StatePublished - Dec 1 2010
Externally publishedYes
Event10th IEEE International Conference on Data Mining Workshops, ICDMW 2010 - Sydney, NSW, Australia
Duration: Dec 14 2010Dec 17 2010

Publication series

NameProceedings - IEEE International Conference on Data Mining, ICDM
ISSN (Print)1550-4786

Other

Other10th IEEE International Conference on Data Mining Workshops, ICDMW 2010
CountryAustralia
CitySydney, NSW
Period12/14/1012/17/10

Keywords

  • Affinity matrix learning
  • Eigenvalue thresholding
  • Rank minimization
  • Robust estimation
  • Spectral clustering

Fingerprint Dive into the research topics of 'Robust low-rank subspace segmentation with semidefinite guarantees'. Together they form a unique fingerprint.

Cite this