Robust tensor decomposition via t-SVD: Near-optimal statistical guarantee and scalable algorithms

Aiming at recovering a signal tensor from its mixture with outliers and noises, robust tensor decomposition (RTD) arises frequently in many real-world applications. Recently, the low-tubal-rank model has shown more powerful performances than traditional tensor low-rank models in several tensor recovery tasks. Assuming the underlying tensor to be low-tubal-rank and the outliers sparse, this paper first proposes a penalized least squares estimator for RTD. Specifically, we adopt the tubal nuclear norm (TNN) and a sparsity inducing norm to regularize the underlying tensor and the outliers, respectively. Then, from a statistical standpoint, non-asymptotic upper bounds on the estimation error are established and proved to be near-optimal in a minimax sense. Further, two algorithms, namely, an ADMM-based algorithm and a Frank-Wolfe (FW) based algorithm are proposed to efficiently solve the proposed estimator from a computational standpoint. The sharpness of the proposed upper bound is verified on synthetic datasets. The superiority and efficiency of the proposed algorithms is demonstrated in experiments on real datasets. (C) 2019 Elsevier B.V. All rights reserved.