Multi-Way Clustering Using Super-Symmetric Non-Negative Tensor Factorization

Abstract

We consider the problem of clustering data into k ≥ 2 clusters given complex relations — going beyond pairwise — between the data points. The complex n -wise relations are modeled by an n -way array where each entry corresponds to an affinity measure over an n -tuple of data points. We show that a probabilistic assignment of data points to clusters is equivalent, under mild conditional independence assumptions, to a super-symmetric non-negative factorization of the closest hyper-stochastic version of the input n -way affinity array. We derive an algorithm for finding a local minimum solution to the factorization problem whose computational complexity is proportional to the number of n -tuple samples drawn from the data. We apply the algorithm to a number of visual interpretation problems including 3D multi-body segmentation and illumination-based clustering of human faces.