Approximation algorithms for tensor clustering

Stefanie Jegelka, Suvrit Sra, Arindam Banerjee

Research output: Chapter in Book/Report/Conference proceedingConference contribution

25 Scopus citations

Abstract

We present the first (to our knowledge) approximation algorithm for tensor clustering - a powerful generalization to basic 1D clustering. Tensors are increasingly common in modern applications dealing with complex heterogeneous data and clustering them is a fundamental tool for data analysis and pattern discovery. Akin to their 1D cousins, common tensor clustering formulations are NP-hard to optimize. But, unlike the 1D case, no approximation algorithms seem to be known. We address this imbalance and build on recent co-clustering work to derive a tensor clustering algorithm with approximation guarantees, allowing metrics and divergences (e.g., Bregman) as objective functions. Therewith, we answer two open questions by Anagnostopoulos et al. (2008). Our analysis yields a constant approximation factor independent of data size; a worst-case example shows this factor to be tight for Euclidean co-clustering. However, empirically the approximation factor is observed to be conservative, so our method can also be used in practice.

Original languageEnglish (US)
Title of host publicationAlgorithmic Learning Theory - 20th International Conference, ALT 2009, Proceedings
Pages368-383
Number of pages16
DOIs
StatePublished - 2009
Event20th International Conference on Algorithmic Learning Theory, ALT 2009 - Porto, Portugal
Duration: Oct 3 2009Oct 5 2009

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume5809 LNAI
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other20th International Conference on Algorithmic Learning Theory, ALT 2009
Country/TerritoryPortugal
CityPorto
Period10/3/0910/5/09

Fingerprint

Dive into the research topics of 'Approximation algorithms for tensor clustering'. Together they form a unique fingerprint.

Cite this