Home News About Us Contact Contributors Disclaimer Privacy Policy Help FAQ

Home
Search
Quick Search
Advanced
Fulltext
Browse
Collections
Persons
My eDoc
Session History
Login
Name:
Password:
Documentation
Help
Support Wiki
Direct access to
document ID:


          Institute: MPI für biologische Kybernetik     Collection: Biologische Kybernetik     Display Documents



ID: 461777.0, MPI für biologische Kybernetik / Biologische Kybernetik
Approximation Algorithms for Tensor Clustering
Authors:Jegelka, S.; Sra, S.; Banerjee, A.
Editors:Gavalda, R.; Lugosi, G.; Zeugmann, T.; Zilles, S.
Date of Publication (YYYY-MM-DD):2009-10
Title of Proceedings:Algorithmic Learning Theory: 20th International Conference (ALT 2009)
Start Page:368
End Page:383
Physical Description:16
Audience:Not Specified
Intended Educational Use:No
Abstract / Description:We present the first (to our knowledge) approximation algo-
rithm 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.
External Publication Status:published
Document Type:Conference-Paper
Communicated by:Holger Fischer
Affiliations:MPI für biologische Kybernetik/Empirical Inference (Dept. Schölkopf)
Identifiers:LOCALID:5916
URL:http://www-alg.ist.hokudai.ac.jp/~thomas/ALT09/alt...
The scope and number of records on eDoc is subject to the collection policies defined by each institute - see "info" button in the collection browse view.