Abstract. Robust tensor recovery plays an instrumental role in robustifying tensor decompositions for multilinear data analysis against outliers, gross corruptions and missing values and has a diverse array of applications. In this paper, we study the problem of robust low-rank tensor recovery in a convex optimization framework, drawing upon recent advances in robust Principal Component Analysis and tensor completion. We propose tailored optimization algorithms with global convergence guarantees for solving both the constrained and the Lagrangian formulations of the problem. These algorithms are based on the highly efficient alternating direction augmented Lagrangian and accelerated proximal gradient methods. We also propose a nonconvex model that can often improve the recovery results from the convex models. We investigate the empirical recoverability properties of the convex and nonconvex formulations and compare the computational performance of the algorithms on simulated data. We demonstrate through a number of real applications the practical effectiveness of this convex optimization framework for robust low-rank tensor recovery. Key words. low-rank tensors, higher-order robust PCA, Tucker rank, tensor decompositions, alternating direction augmented Lagrangian, variable-splitting AMS subject classifications. 15A69, 90C25, 90C30, 65K10 1. Introduction. The rapid advance in modern computer technology has given rise to the wide presence of multidimensional data (tensor data). Traditional matrix-based data analysis is inherently two-dimensional, which limits its usefulness in extracting information from a multidimensional perspective. On the other hand, tensor-based multilinear data analysis has shown that tensor models are capable of taking full advantage of the multilinear structures to provide better understanding and more precision. At the core of multilinear data analysis lies tensor decomposition, which commonly takes two forms: CANDECOMP/PARAFAC (CP) decomposition [10, 22] and Tucker decomposition [48] . Having originated in the fields of psychometrics and chemometrics, these decompositions are now widely used in other application areas such as computer vision [49] , web data mining [18, 42] , and signal processing [1] . Tensor decomposition faces three major challenges: arbitrary outliers, missing data/partial observations, and computational efficiency. Tensor decomposition resembles Principal Component Analysis (PCA) for matrices in many ways. In fact, Tucker decomposition is also known as higherorder SVD (HOSVD) [11] . It is well-known that PCA is sensitive to outliers and gross corruptions (non-Gaussian noise). Since the CP and Tucker decompositions are also based on least-squares approximation, they are prone to these problems as well. Algorithms based on non-convex formulations have been proposed to robustify tensor decompositions against outliers [15, 36] and missing data [2] . However, they suffer from the lack of global optimality guarantees. In practice, the underlying tensor data is often low-rank, even though the actual data may not be due to outliers and arbitrary errors. In other words, the major part of the variation in the data is often governed by a relatively small number of latent factors. It is thus possible to robustify tensor decompositions by reconstructing the low-rank part of the noisy data. Besides its importance to tensor decompositions, robust low-rank tensor recovery also has many applications in its own right, e.g., shadow/occulsion removal in image processing. Motivated by the aforementioned challenges and opportunities, we study the problem of low-rank tensor recovery that is robust to gross corruptions and missing values in a convex optimization framework. Our work in this paper is built upon two major lines of previous work: Principal Component Pursuit (PCP) for Robust PCA [9] and Tensor Completion [20, 32, 46] . The main advantages of the convex formulation that we use are that it removes outliers or corrects corruptions based on the global structure of the tensor, and its solution can be obtained by efficient convergent convex optimization algorithms that are easy to implement. Moreover, this solution naturally leads to a robust Tucker decomposition, and the CP decomposition can also be obtained by applying a simple heuristic [46] .
In REF , MRPCA is also called as robust low-rank tensor recovery.
Robust Low-rank Tensor Recovery: Models and Algorithms
Computer Science Mathematics