On Tensors, Sparsity, and Nonnegative Factorizations


Tensors have found application in a variety of fields, ranging from chemometrics to signal processing and beyond. In this paper, we consider the problem of multilinear modeling of sparse count data. Our goal is to develop a descriptive tensor factorization model of such data, along with appropriate algorithms and theory. To do so, we propose that the random variation is best described via a Poisson distribution, which better describes the zeros observed in the data as compared to the typical assumption of a Gaussian distribution. Under a Poisson assumption, we fit a model to observed data using the negative log-likelihood score. We present a new algorithm for Poisson tensor factorization called CANDECOMP-PARAFAC alternating Poisson regression (CP-APR) that is based on a majorization-minimization approach. It can be shown that CP-APR is a generalization of the Lee-Seung multiplicative updates. We show how to prevent the algorithm from converging to non-KKT points and prove convergence of CP-APR under mild conditions. We also explain how to implement CP-APR for large-scale sparse tensors and present results on several data sets, both real and simulated.

SIAM Journal on Matrix Analysis and Applications
E. C. Chi, T. G. Kolda. On Tensors, Sparsity, and Nonnegative Factorizations. SIAM Journal on Matrix Analysis and Applications, Vol. 33, No. 4, pp. 1272-1299, 2012. https://doi.org/10.1137/110859063


nonnegative tensor factorization, nonnegative CANDECOMP-PARAFAC, Poisson tensor factorization, Lee-Seung multiplicative updates, majorization-minimization algorithms


author = {Eric C. Chi and Tamara G. Kolda}, 
title = {On Tensors, Sparsity, and Nonnegative Factorizations}, 
journal = {SIAM Journal on Matrix Analysis and Applications}, 
volume = {33}, 
number = {4}, 
pages = {1272-1299}, 
month = {December}, 
year = {2012},
doi = {10.1137/110859063},