# Accelerated Tensor Robust Principal Component Analysis via Factorized Tensor Norm Minimization
## 1 Introduction  
Robust principal component analysis (RPCA) has been extensively studied to address the issue of extreme outliers contained in data, which causes significant degradation of the performance when applying classical principal component analysis [1]. Specifically, RPCA aims to separate outliers from the true data by reconstructing a low-rank matrix \(L\in\mathbb{R}^{m\times n}\) from an observed matrix \(X\), which is contaminated by sparse noise \(S\) of arbitrary magnitude, such that  
\[X=L+S. \tag{1}\]  
This RPCA model arises in numerous real-world applications, including image denoising, video background subtraction, subspace clustering, or feature selection in bioinformatics [2, 3, 4, 5, 6]. However, identifying the locations of sparse noise, i.e., the nonzero entries of \(S\), is often challenging. Under the assumptions that \(L\) is low-rank and \(S\) is sufficiently sparse, it has been shown that one can accurately recover \(L\) by solving the following convex problem:  
\[\min\lVert L\rVert_{*}+\lambda\lVert S\rVert_{1}\text{, s.t. }X=L+S, \tag{2}\]where \(\|\cdot\|_{*}\) denotes the nuclear norm, \(\|\cdot\|_{1}\) denotes the \(l_{1}\) norm, and \(\lambda\) is a regularization parameter [1]. A typical algorithm for solving the problem (2) is to apply singular value thresholding, which modifies the singular values of a matrix by applying a threshold operator [7]. However, as the data structure become increasingly complex, the matrix representation may no longer be sufficient for capturing the intricacies of real-world data. Since tensors can represent higher-order data while preserving spatio-temporal and multi-dimensional correlations, it is natural to extend RPCA to tensor setting. This motivates the extension of the RPCA model in (2) to the tensor RPCA (TRPCA) formulation, where the input is an \(n\)-th order tensor \(\mathcal{X}\in\mathbf{R}^{l_{1}\times\ldots\times l_{n}}\). The optimization problem of TRPCA is formulated as follows:  
\[\min\lvert\mathcal{L}\rvert\rvert_{*}+\lambda\lvert\lvert\mathcal{S}\rvert \rvert_{1},\text{ s.t. }\mathcal{X}=\mathcal{L}+\mathcal{S}, \tag{3}\]  
where \(\mathcal{L}\) denotes a low-rank tensor, \(\mathcal{S}\) is a sparse tensor, and \(\lambda\) is a regularization parameter. However, this extension introduces new challenges, particularly due to the lack of a unified definition of tensor rank and tensor nuclear norm, unlike in the matrix case. For example, under Canonical Polyadic Decomposition (CPD), the tensor rank is defined as the minimum number of rank-1 tensors whose sum reconstructs the given tensor [8]. However the rank minimization problem with CP rank is generally NP-hard [9]. Another widely used definition is the Tucker rank, which consists of a tuple of ranks obtained by unfolding the tensor along each mode. Its convex surrogate can be formulated by summing the nuclear norms of the mode-wide unfoldings, leveraging ideas from matrix convex optimization [10]. More recently, tensor singular value decomposition (T-SVD) and tensor-tensor product (T-product) frameworks introduced by [PERSON] et al. [11] led to definitions such as tensor multi-rank and tensor tubal rank. These ranks provide a more structured and compact representation of tensors and avoid the loss of structural information that typically occurs during tensor matricization. They are particularly useful for preserving the inherent low-rank structure in tensor data. Nevertheless, it should be noted that computing the T-SVD-based tensor ranks can be computationally demanding as the size of the tensor increases. In this paper, we propose a novel and computationally efficient TRPCA algorithm based on tensor average rank minimization. Specifically, our main contribution is the further relaxation of the tensor nuclear norm--a convex envelope of the tensor average norm defined in (3)--into an optimization problem involving the sum of Frobenius norms of factor tensors.