Similarity matrix framework for data from union of subspaces

Aldroubi A., Sekmen A., Koku A. B. , Cakmak A. F.

APPLIED AND COMPUTATIONAL HARMONIC ANALYSIS, vol.45, no.2, pp.425-435, 2018 (Journal Indexed in SCI) identifier identifier

  • Publication Type: Article / Article
  • Volume: 45 Issue: 2
  • Publication Date: 2018
  • Doi Number: 10.1016/j.acha.2017.08.006
  • Page Numbers: pp.425-435
  • Keywords: Subspace segmentation, Union of subspaces, Data clustering, Similarity matrix, Shape interaction matrix, Skeleton decomposition, SEGMENTATION


This paper presents a framework for finding similarity matrices for the segmentation of data W = [w(1)...w(N)] subset of R-D drawn from a union U = boolean OR(M)(i=1) S-i, of independent subspaces {S-i}(i=1)(M), of dimensions {d(i)}(i=1)(M). It is shown that any factorization of W = BP, where columns of B form a basis for data W and they also come from U, can be used to produce a similarity matrix Xi w. In other words, Xi w(i, j) not equal 0, when the columns w(i) and w(j) of W come from the same subspace, and Xi w(i, j) = 0, when the columns w(i) and w(j), of W come from different subspaces. Furthermore, Xi w = Q(dmax), where d(max) = max {d(i)}(i=1)(M), and Q is an element of R-NxN with Q(i, j) = vertical bar P-T(i, j)vertical bar. It is shown that a similarity matrix obtained from the reduced row echelon form of W is a special case of the theory. It is also proven that the Shape Interaction Matrix defined as VVT, where W = U Sigma V-T is the skinny singular value decomposition of W, is not necessarily a similarity matrix. But, taking powers of its absolute value always generates a similarity matrix. An interesting finding of this research is that a similarity matrix can be obtained using a skeleton decomposition of W. 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 matrix R corresponding to the rows of W that contain A is constructed. Finally, a power of the matrix (PP)-P-T where P = A(-1) R provides a similarity matrix Xi w. Since most of the data matrices are low-rank in many subspace segmentation problems, this is computationally efficient compared to other constructions of similarity matrices. (C) 2017 Elsevier Inc. All rights reserved.