  The low-tubal-rank tensor model has been recently proposed for real-world
multidimensional data. In this paper, we study the low-tubal-rank tensor
completion problem, i.e., to recover a third-order tensor by observing a subset
of its elements selected uniformly at random. We propose a fast iterative
algorithm, called {\em Tubal-Alt-Min}, that is inspired by a similar approach
for low-rank matrix completion. The unknown low-tubal-rank tensor is
represented as the product of two much smaller tensors with the low-tubal-rank
property being automatically incorporated, and Tubal-Alt-Min alternates between
estimating those two tensors using tensor least squares minimization. First, we
note that tensor least squares minimization is different from its matrix
counterpart and nontrivial as the circular convolution operator of the
low-tubal-rank tensor model is intertwined with the sub-sampling operator.
Second, the theoretical performance guarantee is challenging since
Tubal-Alt-Min is iterative and nonconvex in nature. We prove that 1)
Tubal-Alt-Min guarantees exponential convergence to the global optima, and 2)
for an $n \times n \times k$ tensor with tubal-rank $r \ll n$, the required
sampling complexity is $O(nr^2k \log^3 n)$ and the computational complexity is
$O(n^2rk^2 \log^2 n)$. Third, on both synthetic data and real-world video data,
evaluation results show that compared with tensor-nuclear norm minimization
(TNN-ADMM), Tubal-Alt-Min improves the recovery error dramatically (by orders
of magnitude). It is estimated that Tubal-Alt-Min converges at an exponential
rate $10^{-0.4423 \text{Iter}}$ where $\text{Iter}$ denotes the number of
iterations, which is much faster than TNN-ADMM's $10^{-0.0332 \text{Iter}}$,
and the running time can be accelerated by more than $5$ times for a $200
\times 200 \times 20$ tensor.
