Similarity matrix framework for data from union of subspaces

This paper presents a framework for finding similarity matrices for the segmentation of data W=[w1⋯wN]⊂RD drawn from a union U=⋃i=1MSi of independent subspaces {Si}i=1M of dimensions {di}i=1M. 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 ΞW. In other words, ΞW(i,j)≠0, when the columns wi and wj of W come from the same subspace, and ΞW(i,j)=0, when the columns wi and wj of W come from different subspaces. Furthermore, ΞW=Qdmax, where dmax=max⁡{di}i=1M and Q∈RN×N with Q(i,j)=|PTP(i,j)|. 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ΣVT 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∈Rr×r 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 PTP where P=A−1R provides a similarity matrix Ξ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.