Abstract
This paper provides a comprehensive analysis of skeleton decomposition used for segmentation of data W = [w1 ···WN] ⊂ ℝd drawn from a union U = ∪i=1M Si of linearly independent subspaces {Si}i=1M of dimensions of {di}i=1M. 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 ϵ ℝr×r 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ℝ and corresponding similarity matrix SW = (pTp)dmax, where dmax 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.