English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
  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

Files

show Files

Locators

show

Creators

show
hide
 Creators:
Jegelka, S1, 2, Author              
Sra, S1, 2, Author              
Banerjee, A, Author
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              

Content

show
hide
Free keywords: -
 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.

Details

show
hide
Language(s):
 Dates: 2009-10
 Publication Status: Published in print
 Pages: -
 Publishing info: -
 Table of Contents: -
 Rev. Type: -
 Identifiers: DOI: 10.1007/978-3-642-04414-4_30
BibTex Citekey: 5916
 Degree: -

Event

show
hide
Title: 20th International Conference on Algorithmic Learning Theory (ALT 2009)
Place of Event: Porto, Portugal
Start-/End Date: 2009-10-03 - 2009-10-05

Legal Case

show

Project information

show

Source 1

show
hide
Title: Algorithmic Learning Theory: 20th International Conference, ALT 2009, Porto, Portugal, October 3-5, 2009
Source Genre: Proceedings
 Creator(s):
Gavalda, R, Editor
Lugosi, G, Editor
Zeugmann, T, Editor
Zilles, S, Editor
Affiliations:
-
Publ. Info: Berlin, Germany : Springer
Pages: - Volume / Issue: - Sequence Number: - Start / End Page: 368 - 383 Identifier: ISBN: 978-3-642-04413-7

Source 2

show
hide
Title: Lecture Notes in Computer Science
Source Genre: Series
 Creator(s):
Affiliations:
Publ. Info: -
Pages: - Volume / Issue: 5809 Sequence Number: - Start / End Page: - Identifier: -