Fast Subspace Clustering Based on the Kronecker Product
  Subspace clustering is a useful technique for many computer vision
applications in which the intrinsic dimension of high-dimensional data is often
smaller than the ambient dimension. Spectral clustering, as one of the main
approaches to subspace clustering, often takes on a sparse representation or a
low-rank representation to learn a block diagonal self-representation matrix
for subspace generation. However, existing methods require solving a large
scale convex optimization problem with a large set of data, with computational
complexity reaches O(N^3) for N data points. Therefore, the efficiency and
scalability of traditional spectral clustering methods can not be guaranteed
for large scale datasets. In this paper, we propose a subspace clustering model
based on the Kronecker product. Due to the property that the Kronecker product
of a block diagonal matrix with any other matrix is still a block diagonal
matrix, we can efficiently learn the representation matrix which is formed by
the Kronecker product of k smaller matrices. By doing so, our model
significantly reduces the computational complexity to O(kN^{3/k}). Furthermore,
our model is general in nature, and can be adapted to different regularization
based subspace clustering methods. Experimental results on two public datasets
show that our model significantly improves the efficiency compared with several
state-of-the-art methods. Moreover, we have conducted experiments on synthetic
data to verify the scalability of our model for large scale datasets.
