  This paper conducts a rigorous analysis for provable estimation of
multidimensional arrays, in particular third-order tensors, from a random
subset of its corrupted entries. Our study rests heavily on a recently proposed
tensor algebraic framework in which we can obtain tensor singular value
decomposition (t-SVD) that is similar to the SVD for matrices, and define a new
notion of tensor rank referred to as the tubal rank. We prove that by simply
solving a convex program, which minimizes a weighted combination of tubal
nuclear norm, a convex surrogate for the tubal rank, and the $\ell_1$-norm, one
can recover an incoherent tensor exactly with overwhelming probability,
provided that its tubal rank is not too large and that the corruptions are
reasonably sparse. Interestingly, our result includes the recovery guarantees
for the problems of tensor completion (TC) and tensor principal component
analysis (TRPCA) under the same algebraic setup as special cases. An
alternating direction method of multipliers (ADMM) algorithm is presented to
solve this optimization problem. Numerical experiments verify our theory and
real-world applications demonstrate the effectiveness of our algorithm.
