Date

2018-09-01

Author

Aldroubi, Akram
Sekmen, Ali
Koku, Ahmet Buğra
Cakmak, Ahmet Faruk

Metadata

Show full item record

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Item Usage Stats

293
views

0
downloads

Cite This

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.

Subject Keywords

Skeleton decomposition, Shape interaction matrix, Similarity matrix, Data clustering, Union of subspaces, Subspace segmentation

URI

https://hdl.handle.net/11511/42591

Collections

Department of Mechanical Engineering, Article