  This paper studies tensor-based Robust Principal Component Analysis (RPCA)
using atomic-norm regularization. Given the superposition of a sparse and a
low-rank tensor, we present conditions under which it is possible to exactly
recover the sparse and low-rank components. Our results improve on existing
performance guarantees for tensor-RPCA, including those for matrix RPCA. Our
guarantees also show that atomic-norm regularization provides better recovery
for tensor-structured data sets than other approaches based on matricization.
  In addition to these performance guarantees, we study a nonconvex formulation
of the tensor atomic-norm and identify a class of local minima of this
nonconvex program that are globally optimal. We demonstrate the strong
performance of our approach in numerical experiments, where we show that our
nonconvex model reliably recovers tensors with ranks larger than all of their
side lengths, significantly outperforming other algorithms that require
matricization.
