# Accelerated Tensor Robust Principal Component Analysis via Factorized Tensor Norm Minimization
## 2 Notations and Preliminaries  
We first summarize the symbols and terminologies consistently used throughout this paper. Capital calligraphy letters, e.g., \(\mathcal{A}\), and capital letters, e.g., \(A\), are used to denote tensors and matrices, respectively. Boldface lowercase letters, e.g., \(\mathbf{a}\), and lowercase letters \(a\) represent vectors and scalars, respectively. For a third-order tensor \(\mathcal{A}\), we adopt MATLAB-style notation: \(\mathcal{A}(i,:,:)\), \(\mathcal{A}(:,i,:)\), and \(\mathcal{A}(:,:,i)\) denote the \(i\)-th horizontal, lateral, and frontal slices of \(\mathcal{A}\), respectively. For convenience, we abbreviate the \(i\)-th frontal slice \(\mathcal{A}(:,:,i)\) as \(\mathcal{A}(i)\). The MATLAB functions \(\bar{\mathcal{A}}=\text{fft}(\mathcal{A},\left\lVert,3\right\rangle\) and \(\mathcal{A}=\text{fft}(\bar{\mathcal{A}},\left\lVert,3\right\rangle\) are used to compute the Discrete Fourier Transform (DFT) and its inverse along the third dimension of \(\mathcal{A}\), respectively, yielding \(\bar{\mathcal{A}}\) and reconstructing \(\mathcal{A}\). Additionally, we define the function \(\bar{A}=\text{bdiag}(\bar{\mathcal{A}})\) as  
\[\bar{A}=\text{bdiag}(\bar{\mathcal{A}})=\left( \begin{array}{cccc}\bar{ \mathcal{A}}(1)&&&\\ &\mathcal{A}(2)&&\\ &&\ddots&\\ &&&\bar{\mathcal{A}}(n_{3})\end{array} \right), \tag{4}\]  
which rearranges the frontal slices of the tensor \(\bar{\mathcal{A}}\in\mathbf{R}^{n_{1}\times n_{2}\times n_{3}}\) to the block diagonal matrix \(\bar{A}\in\mathbf{R}^{n_{1}n_{3}\times n_{2}n_{3}}\). The function \(\text{bcirc}(\cdot)\) reconstructs the block circulant matrix \(B\in\mathbf{R}^{n_{1}n_{3}\times n_{2}n_{3}}\) from the tensor \(\mathcal{B}\in\mathbf{R}^{n_{1}\times n_{2}\times n_{2}}\) as follows:  
\[\text{bcirc}(\mathcal{B})=\left( \begin{array}{cccc}\mathcal{B}(1)& \mathcal{B}(n_{3})&\cdots&\mathcal{B}(2)\\ \mathcal{B}(2)&\mathcal{B}(1)&\cdots&\mathcal{B}(3)\\ \vdots&\vdots&\ddots&\vdots\\ \mathcal{B}(n_{3})&\mathcal{B}(n_{3}-1)&\cdots&\mathcal{B}(1)\end{array}  \right). \tag{5}\]  
A function \(D=\text{unfold}(\mathcal{D})\) transforms the tensor \(\mathcal{D}\in\mathbf{R}^{n_{1}\times n_{2}\times n_{3}}\) into the matrix \(D\in\mathbf{R}^{n_{1}n_{3}\times n_{2}}\), where \(D=[D(1);D(2);\cdots;D(n_{3})]\). Conversely, the function \(\mathcal{D}=\text{fold}(D)\) transforms the matrix \(D\) to the tensor \(\mathcal{D}\). These functions satisfy the identity \(\text{fold}(\text{unfold}(\mathcal{D}))=\mathcal{D}\). Based on these notations, we now define several important concepts of tensor algebra used in this paper. **Definition 1** ((T-product) [11]). : _Let \(\mathcal{A}\in\mathbf{R}^{n_{1}\times n_{2}\times n_{3}}\) and \(\mathcal{B}\in\mathbf{R}^{n_{2}\times n\times n_{3}}\) be two third-order tensors. The T-product \(A\ast B\) produces a tensor of size \(n_{1}\times n\times n_{3}\), defined as_  
\[A\ast B=\text{fold}(\text{bcirc}(\mathcal{A})\cdot\text{unfold}(\mathcal{B})). \tag{6}\]  
_Additionally, the result of the T-product defined in (6) is equivalent to matrix multiplication in the Fourier domain. Therefore, it can be computed efficiently as_  
\[\mathcal{A}\ast\mathcal{B}=\text{ifft}\text{ fold }(\text{bdiag}(\bar{ \mathcal{A}}),\text{unfold}(\bar{\mathcal{B}}),[],3),\]  
_where \(\bar{\mathcal{A}}=\text{fft}(\mathcal{A},[],3)\) and \(\bar{\mathcal{B}}=\text{fft}(\mathcal{B},[],3)\)._  
**Definition 2** ((Identity tensor) [11]). : _The identity tensor \(\mathcal{I}\in\mathbf{R}^{n\times n\times n_{3}}\) is defined such that \(\mathcal{I}(1)\) is the identity matrix, and \(\mathcal{I}(i)=0\) for all \(2\leq i\leq n_{3}\)._  
**Definition 3** ((Orthogonal tensor) [11]). : _A tensor \(\mathcal{P}\in\mathbf{R}^{n\times n\times n_{3}}\) is said to be orthogonal if it satisfies_  
\[\mathcal{P}^{\text{T}}\ast\mathcal{P}=\mathcal{P}\ast\mathcal{P}^{\text{T}}= \mathcal{I}. \tag{7}\]  
**Definition 4** ((Inverse tensor)). : _Assume that all frontal slices of a Tensor \(\mathcal{A}\in\mathbf{R}^{n\times n\times n_{3}}\) are invertible.