  In this paper, we investigate the sample size requirement for a general class
of nuclear norm minimization methods for higher order tensor completion. We
introduce a class of tensor norms by allowing for different levels of
coherence, which allows us to leverage the incoherence of a tensor. In
particular, we show that a $k$th order tensor of rank $r$ and dimension
$d\times\cdots\times d$ can be recovered perfectly from as few as
$O((r^{(k-1)/2}d^{3/2}+r^{k-1}d)(\log(d))^2)$ uniformly sampled entries through
an appropriate incoherent nuclear norm minimization. Our results demonstrate
some key differences between completing a matrix and a higher order tensor:
They not only point to potential room for improvement over the usual nuclear
norm minimization but also highlight the importance of explicitly accounting
for incoherence, when dealing with higher order tensors.
