Skeleton Decomposition Analysis for Subspace Clustering

Sekmen A., Aldroubi A., Koku A. B.

4th IEEE International Conference on Big Data (Big Data), Washington, Kiribati, 5 - 08 December 2016, pp.1841-1848 identifier identifier

  • Publication Type: Conference Paper / Full Text
  • Doi Number: 10.1109/bigdata.2016.7840802
  • City: Washington
  • Country: Kiribati
  • Page Numbers: pp.1841-1848
  • Middle East Technical University Affiliated: Yes


This paper provides a comprehensive analysis of skeleton decomposition used for segmentation of data W = [w(1) center dot center dot center dot w(N)] subset of R-D drawn from a union u = U-i=1(M) S-i of linearly independent subspaces {Si}(M)(i=1) of dimensionsof {di}(M)(i=1). Our previous work developed a generalized theoretical framework for computing similarity matrices by matrix factorization. Skeleton decomposition is a special case of this general theory. First, a square sub-matrix A is an element of R-rxr of W with the same rank r as W is found. Then, the corresponding row restriction R of W is constructed. This leads to P= A(-1)R and corresponding similarity matrix SW = ((PP)-P-T)(dmax), where d(max) is the maximum subspace dimension. Since most of the data matrices are low-rank in many subspace segmentation problems, this is computationally efficient compared to the other constructions of similarity matrices. It is also shown (with some limitations) that center-of-mass based sorting of data columns in SW can be used to quickly assess clustering performance while algorithm development in both noisy or noise-free cases.