  This paper considers the completion problem for a tensor (also referred to as
a multidimensional array) from limited sampling. Our greedy method is based on
extending the low-rank approximation pursuit (LRAP) method for matrix
completions to tensor completions. The method performs a tensor factorization
using the tensor singular value decomposition (t-SVD) which extends the
standard matrix SVD to tensors. The t-SVD leads to a notion of rank, called
tubal-rank here. We want to recreate the data in tensors from low resolution
samples as best we can here. To complete a low resolution tensor successfully
we assume that the given tensor data has low tubal-rank. For tensors of low
tubal-rank, we establish convergence results for our method that are based on
the tensor restricted isometry property (TRIP). Our result with the TRIP
condition for tensors is similar to low-rank matrix completions under the RIP
condition. The TRIP condition uses the t-SVD for low tubal-rank tensors, while
RIP uses the SVD for matrices. We show that a subgaussian measurement map
satisfies the TRIP condition with high probability and gives an almost optimal
bound on the number of required measurements. We compare the numerical
performance of the proposed algorithm with those for state-of-the-art
approaches on video recovery and color image recovery.
