Noisy Tensor Completion for Tensors with a Sparse Canonical Polyadic Factor

The last decade has seen enormous progress in both the theory and practical solutions to the problem of matrix completion, in which the goal is to estimate missing elements of a matrix given measurements at some subset of its locations. Originally viewed from a combinatorial perspective [1], it is now usually approached from a statistical perspective in which additional structural assumptions (e.g., low-rank, sparse factors etc) not only make the problem tractable but allow for provable error bounds from noisy measurements [2]-[8]. Tensors, which we will view as multi-way arrays, naturally arise in slew of practical applications in the areas of signal processing, computer vision, neuroscience, etc. [9], [10]. Often in practice tensor data is collected in a noisy environment and suffers from missing observations. Given the success of matrix completion methods, it is no surprise that recently there has been a lot of interest in extending the successes of matrix completion to tensor completion problem [11]-[13]. In this work we consider the general problem of tensor completion.