From K-means to higher-way co-clustering: Multilinear decomposition with sparse latent factors

Evangelos E. Papalexakis, Nicholas D. Sidiropoulos, Rasmus Bro

Research output: Contribution to journalArticlepeer-review

113 Scopus citations


Co-clustering is a generalization of unsupervised clustering that has recently drawn renewed attention, driven by emerging data mining applications in diverse areas. Whereas clustering groups entire columns of a data matrix, co-clustering groups columns over select rows only, i.e., it simultaneously groups rows and columns. The concept generalizes to data 'boxes' and higher-way tensors, for simultaneous grouping along multiple modes. Various co-clustering formulations have been proposed, but no workhorse analogous to $K$-means has emerged. This paper starts from $K$- means and shows how co-clustering can be formulated as a constrained multilinear decomposition with sparse latent factors. For three-and higher-way data, uniqueness of the multilinear decomposition implies that, unlike matrix co-clustering, it is possible to unravel a large number of possibly overlapping co-clusters. A basic multi-way co-clustering algorithm is proposed that exploits multilinearity using Lasso-type coordinate updates. Various line search schemes are then introduced to speed up convergence, and suitable modifications are proposed to deal with missing values. The imposition of latent sparsity pays a collateral dividend: it turns out that sequentially extracting one co-cluster at a time is almost optimal, hence the approach scales well for large datasets. The resulting algorithms are benchmarked against the state-of-art in pertinent simulations, and applied to measured data, including the ENRON e-mail corpus.

Original languageEnglish (US)
Article number6331561
Pages (from-to)493-506
Number of pages14
JournalIEEE Transactions on Signal Processing
Issue number2
StatePublished - 2013


  • Co-clustering
  • compressed sensing
  • factor analysis
  • k-means
  • multi-way analysis
  • sparsity
  • tensor decomposition
  • triclustering
  • unsupervised clustering


Dive into the research topics of 'From K-means to higher-way co-clustering: Multilinear decomposition with sparse latent factors'. Together they form a unique fingerprint.

Cite this