  Tensor decomposition methods are popular tools for analysis of multi-way
datasets from social media, healthcare, spatio-temporal domains, and others.
Widely adopted models such as Tucker and canonical polyadic decomposition (CPD)
follow a data-driven philosophy: they decompose a tensor into factors that
approximate the observed data well. In some cases side information is available
about the tensor modes. For example, in a temporal user-item purchases tensor a
user influence graph, an item similarity graph, and knowledge about seasonality
or trends in the temporal mode may be available. Such side information may
enable more succinct and interpretable tensor decomposition models and improved
quality in downstream tasks.
  We propose a framework for Multi-Dictionary Tensor Decomposition (MDTD) which
takes advantage of prior structural information about tensor modes in the form
of coding dictionaries to obtain sparsely encoded tensor factors. We derive a
general optimization algorithm for MDTD that handles both complete input and
input with missing values. Our framework handles large sparse tensors typical
to many real-world application domains. We demonstrate MDTD's utility via
experiments with both synthetic and real-world datasets. It learns more concise
models than dictionary-free counterparts and improves (i) reconstruction
quality ($60\%$ fewer non-zero coefficients coupled with smaller error); (ii)
missing values imputation quality (two-fold MSE reduction with up to orders of
magnitude time savings) and (iii) the estimation of the tensor rank. MDTD's
quality improvements do not come with a running time premium: it can decompose
$19GB$ datasets in less than a minute. It can also impute missing values in
sparse billion-entry tensors more accurately and scalably than state-of-the-art
competitors.
