  There is growing interest to extend low-rank matrix decompositions to
multi-way arrays, or tensors. One fundamental low-rank tensor decomposition is
the canonical polyadic decomposition (CPD). The challenge of fitting a
low-rank, nonnegative CPD model to Poisson-distributed count data is of
particular interest. Several popular algorithms use local search methods to
approximate the global maximum likelihood estimator from local minima.
Simultaneously, a recent trend in theoretical computer science and numerical
linear algebra leverages randomization to solve very large, hard problems. The
typical approach is to use randomization for a fast approximation and
determinism for refinement to yield effective algorithms with theoretical
guarantees. Two popular algorithms for Poisson CPD reflect that emergent
dichotomy: CP Alternating Poisson Regression is a deterministic algorithm and
Generalized Canonical Polyadic decomposition makes use of stochastic algorithms
in several variants. This work extends recent work to develop two new methods
that leverage randomized and deterministic algorithms for improved accuracy and
performance.
