Tensor Clustering and Error Bounds

Date: Monday, May 4, 2009
Time: 3:00pm - 4:00pm
Location:LBNL Bldg. 50F, Room 1647

Speaker:
Chris Ding
Department of Computer Science & Engineering
University of Texas at Arlington

Abstract:

Tensor decompositions become increasingly important in analyzing
high-dimensional and multi-index data, such as the wind velocity
distribution on longitude, latitude, vertical coordinates over time.
So far, tensor decompositions are mainly used for dimension
reduction and compression. Here we demonstrate that widely used
tensor decompositions such as HOSVD and ParaFac have clustering
capabilities. More precisely, we prove that HOSVD/ParaFac objective
functions are equivalent to relaxed K-means clustering, in the same
framework that nonnegative matrix factors and PCA relate to K-means
clustering. Error analysis provides insights to tensor
decompositions. We derive tight error bounds for both HOSVD and
ParaFac, generalizing Eckart-Young Theorem for SVD to these tensor
decompositions. We present experiments on several real-life datasets
to demonstrate thes usefulness of these new theoretical results.

Host of Seminar:

    Michael Wehner