Approximation algorithms for tensor clustering

Stefanie Jegelka, Suvrit Sra, Arindam Banerjee

Publikation: Beitrag in Buch/Bericht/KonferenzbandKonferenzbeitragBegutachtung

31 Zitate (Scopus)

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.

OriginalspracheEnglisch
TitelAlgorithmic Learning Theory - 20th International Conference, ALT 2009, Proceedings
Seiten368-383
Seitenumfang16
DOIs
PublikationsstatusVeröffentlicht - 2009
Extern publiziertJa
Veranstaltung20th International Conference on Algorithmic Learning Theory, ALT 2009 - Porto, Portugal
Dauer: 3 Okt. 20095 Okt. 2009

Publikationsreihe

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

Konferenz

Konferenz20th International Conference on Algorithmic Learning Theory, ALT 2009
Land/GebietPortugal
OrtPorto
Zeitraum3/10/095/10/09

Fingerprint

Untersuchen Sie die Forschungsthemen von „Approximation algorithms for tensor clustering“. Zusammen bilden sie einen einzigartigen Fingerprint.

Dieses zitieren