Low-Rank Approximation and Completion of Positive Tensors

Understand

Unlike the matrix case, computing low-rank approximations of tensors is NP-hard and numerically ill-posed in general.

• Even the best rank-1 approximation of a tensor is NP-hard.
• In this paper, we use convex optimization to develop polynomial-time algorithms for low-rank approximation and completion of positive tensors.
• Our approach is to use algebraic topology to define a new (numerically well-posed) decomposition for positive tensors, which we show is equivalent to the standard tensor decomposition in important cases.