Exact tensor completion using t-SVD
This work addresses tensor completion for applications such as video data, providing a theoretically optimal method, though it is incremental as it extends matrix completion concepts to tensors using t-SVD.
The paper tackles the problem of completing multidimensional arrays (tensors) from limited sampling by using a convex optimization approach based on the tensor-SVD (t-SVD) factorization, guaranteeing recovery with overwhelming probability under order-wise optimal sample conditions. It demonstrates performance on real datasets and compares favorably to existing methods like tensor flattening and Tucker decomposition.
In this paper we focus on the problem of completion of multidimensional arrays (also referred to as tensors) from limited sampling. Our approach is based on a recently proposed tensor-Singular Value Decomposition (t-SVD) [1]. Using this factorization one can derive notion of tensor rank, referred to as the tensor tubal rank, which has optimality properties similar to that of matrix rank derived from SVD. As shown in [2] some multidimensional data, such as panning video sequences exhibit low tensor tubal rank and we look at the problem of completing such data under random sampling of the data cube. We show that by solving a convex optimization problem, which minimizes the tensor nuclear norm obtained as the convex relaxation of tensor tubal rank, one can guarantee recovery with overwhelming probability as long as samples in proportion to the degrees of freedom in t-SVD are observed. In this sense our results are order-wise optimal. The conditions under which this result holds are very similar to the incoherency conditions for the matrix completion, albeit we define incoherency under the algebraic set-up of t-SVD. We show the performance of the algorithm on some real data sets and compare it with other existing approaches based on tensor flattening and Tucker decomposition.