Approximation Algorithms for Tensor Clustering

Jegelka, S; Sra, S; Banerjee, A

doi:10.1007/978-3-642-04414-4_30

Lokale TagsFreigabegeschichteDetailsÜbersicht

Approximation Algorithms for Tensor Clustering

Jegelka, S., Sra, S., & Banerjee, A. (2009). Approximation Algorithms for Tensor Clustering. In R. Gavalda, G. Lugosi, T. Zeugmann, & S. Zilles (Eds.), Algorithmic Learning Theory: 20th International Conference, ALT 2009, Porto, Portugal, October 3-5, 2009 (pp. 368-383). Berlin, Germany: Springer.

Item is Freigegeben

einblenden: alle

Basisdaten

ausblenden:

Datensatz-Permalink: https://hdl.handle.net/11858/00-001M-0000-0013-C27A-7 Versions-Permalink: https://hdl.handle.net/21.11116/0000-0002-E346-F

Genre: Konferenzbeitrag

Dateien

einblenden: Dateien

Externe Referenzen

ausblenden:

externe Referenz:
https://link.springer.com/content/pdf/10.1007%2F978-3-642-04414-4_30.pdf (Verlagsversion) Open Access Status unbekannt

Beschreibung:
-

OA-Status:

Urheber

ausblenden:

Urheber:
Jegelka, S^{1, 2}, Autor
Sra, S^{1, 2}, Autor
Banerjee, A, Autor

Affiliations:
1Department Empirical Inference, Max Planck Institute for Biological Cybernetics, Max Planck Society, ou_1497795
2Max Planck Institute for Biological Cybernetics, Max Planck Society, Spemannstrasse 38, 72076 Tübingen, DE, ou_1497794

Inhalt

ausblenden:

Schlagwörter: -

Zusammenfassung: 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.

Details

ausblenden:

Sprache(n):

Datum: Erschienen: 2009-10

Publikationsstatus: Erschienen

Seiten: -

Ort, Verlag, Ausgabe: -

Inhaltsverzeichnis: -

Art der Begutachtung: -

Identifikatoren: DOI: 10.1007/978-3-642-04414-4_30
BibTex Citekey: 5916

Art des Abschluß: -

Veranstaltung

ausblenden:

Titel: 20th International Conference on Algorithmic Learning Theory (ALT 2009)

Veranstaltungsort: Porto, Portugal

Start-/Enddatum: 2009-10-03 - 2009-10-05

Entscheidung

einblenden:

Projektinformation

einblenden:

Quelle 1

ausblenden:

Titel: Algorithmic Learning Theory: 20th International Conference, ALT 2009, Porto, Portugal, October 3-5, 2009

Genre der Quelle: Konferenzband

Urheber:
Gavalda, R, Herausgeber
Lugosi, G, Herausgeber
Zeugmann, T, Herausgeber
Zilles, S, Herausgeber

Affiliations:
-

Ort, Verlag, Ausgabe: Berlin, Germany : Springer

Seiten: - Band / Heft: - Artikelnummer: - Start- / Endseite: 368 - 383 Identifikator: ISBN: 978-3-642-04413-7

Quelle 2

ausblenden:

Titel: Lecture Notes in Computer Science

Genre der Quelle: Reihe

Urheber:

Affiliations:

Ort, Verlag, Ausgabe: -

Seiten: - Band / Heft: 5809 Artikelnummer: - Start- / Endseite: - Identifikator: -