Tucker Decomposition with Structured Core: Identifiability, Stability and Computability

Music City Center 

We consider the Tensor Tucker decomposition and show that it is uniquely identified up to sign and permutation of the columns of the component matrices, and is stable under small perturbations, when the core tensor satisfies certain structural support conditions. When affected by noise, we get stand-alone error bounds of each column, unaffected by the others. We show that if the core of a higher order tensor consists of random entries, the uniqueness and stability properties hold with high probability even when the elements of the core tensor are nonzero with probability close to but bounded away from one. We also furnish algorithms for performing tensor decompositions in these settings. From an application perspective, our results are useful in making inference about paired latent variable models and can be related to Kronecker-product dictionary learning.