Robust Low-tubal-rank Tensor Completion

Real multi-way data may suffer from missing entries, noise and outliers simultaneously. The recently proposed tubal nuclear norm (TNN) has shown its superiority in tensor completion. However, statistical analysis of TNN based models is still deficient. This paper aims to robustly recover a polluted incomplete tensor with rigorous statistical guarantee. Specifically, an estimator based on a weighed variant of TNN is proposed to complete a low-tubal-rank tensor corrupted by element sparse errors or slice sparse sample outliers from partial noisy observations. Non-asymptotic upper bounds on the estimation error are established and further proved to be minimax optimal up to a log factor. Sharpness of the upper bounds is verified on synthetic datasets and superiority of the proposed estimator is demonstrated through robust video inpainting.