Spectral clustering using multilinear SVD: Analysis, approximations and applications

Spectral clustering, a graph partitioning technique, has gained immense popularity in machine learning in the context of unsupervised learning. This is due to con-vincing empirical studies, elegant approaches involved and the theoretical guarantees provided in the litera-ture. To tackle some challenging problems that arose in computer vision etc., recently, a need to develop spec-tral methods that incorporate multi-way similarity mea-sures surfaced. This, in turn, leads to a hypergraph par-titioning problem. In this paper, we formulate a cri-terion for partitioning uniform hypergraphs, and show that a relaxation of this problem is related to the mul-tilinear singular value decomposition (SVD) of sym-metric tensors. Using this, we provide a spectral tech-nique for clustering based on higher order affinities, and derive a theoretical bound on the error incurred by this method. We also study the complexity of the algo-rithm and use Nyström’s method and column sampling techniques to develop approximate methods with sig-nificantly reduced complexity. Experiments on geomet-ric grouping and motion segmentation demonstrate the practical significance of the proposed methods