Exact Low Tubal Rank Tensor Recovery from Gaussian Measurements
  The recent proposed Tensor Nuclear Norm (TNN) [Lu et al., 2016; 2018a] is an
interesting convex penalty induced by the tensor SVD [Kilmer and Martin, 2011].
It plays a similar role as the matrix nuclear norm which is the convex
surrogate of the matrix rank. Considering that the TNN based Tensor Robust PCA
[Lu et al., 2018a] is an elegant extension of Robust PCA with a similar tight
recovery bound, it is natural to solve other low rank tensor recovery problems
extended from the matrix cases. However, the extensions and proofs are
generally tedious. The general atomic norm provides a unified view of
low-complexity structures induced norms, e.g., the $\ell_1$-norm and nuclear
norm. The sharp estimates of the required number of generic measurements for
exact recovery based on the atomic norm are known in the literature. In this
work, with a careful choice of the atomic set, we prove that TNN is a special
atomic norm. Then by computing the Gaussian width of certain cone which is
necessary for the sharp estimate, we achieve a simple bound for guaranteed low
tubal rank tensor recovery from Gaussian measurements. Specifically, we show
that by solving a TNN minimization problem, the underlying tensor of size
$n_1\times n_2\times n_3$ with tubal rank $r$ can be exactly recovered when the
given number of Gaussian measurements is $O(r(n_1+n_2-r)n_3)$. It is order
optimal when comparing with the degrees of freedom $r(n_1+n_2-r)n_3$. Beyond
the Gaussian mapping, we also give the recovery guarantee of tensor completion
based on the uniform random mapping by TNN minimization. Numerical experiments
verify our theoretical results.
