[BANANA] LA/Opt seminar TODAY (Evrim Acar)

[Michael A. Saunders]

REMINDER: Seminar this afternoon.
This is the last seminar of spring quarter


    Linear Algebra and Optimization Seminar (CME 510)
    iCME, Stanford University
    http://icme.stanford.edu/seminars/seminars.php

    4:15pm Wed May 27, 2009
    Terman 332

    Dr Evrim Acar Ataman
    Sandia National Laboratories, Livermore
    eacarat at sandia.gov
    http://csmr.ca.sandia.gov/~eacarat/

    An Optimization Approach for Fitting a CANDECOMP/PARAFAC Model
    and Its Applications in Social Network Analysis

Tensor decompositions are higher-order analogues of matrix
decompositions and have proven to be powerful tools for data analysis.
In particular, we are interested in the CANDECOMP/PARAFAC (CP) model,
which expresses a tensor as the sum of rank-one tensors and has been
widely used in different disciplines including chemometrics,
neuroscience, and signal processing.  The task of fitting the CP model
to large-scale datasets is known to be computationally challenging.
The traditional approach for fitting a CP model is based on
alternating least squares (ALS) optimization.  The ALS approach is
generally fast but is not robust to over-factoring (i.e., ALS does not
recover the true components when more than that number is specified in
the model).  Previously, nonlinear least squares (NLS) methods have
also been recommended and are robust to over-factoring; however, these
methods do not scale to large problem sizes.

To address these issues, we propose the use of gradient-based
optimization (OPT) methods for fitting the CP model.  We discuss the
mathematical calculation of the derivatives and show that they can be
computed efficiently, at the same cost as one iteration of ALS.
Numerical experiments are conducted on both simulated and real
datasets.  We show that gradient-based optimization methods are more
accurate than ALS and much faster than NLS.  To demonstrate
scalability, we use the proposed OPT algorithm for the analysis of
large social network data and obtain promising performance in terms of
link prediction.

This is joint work with Tamara G. Kolda and Daniel M. Dunlavy.