# Tensor Robust Principal Component Analysis via Non-Convex Low Rank Approximation
## 3 Notations and Definitions  
Throughout this paper, all boldface Euler script letters (\(\mathcal{X}\)) denote tensors, uppercase characters (\(X\)) denote matrices, and lowercase letters (\(a\)) denote scalars. The field of real numbers is denoted as \(\mathbb{R}\). We denote \(N_{i},i=1,2,3\) as the index set associated with a given tensor. For 3 rd-order tensors \(\mathcal{X}=[a_{ijk}]\in\mathbb{R}^{N_{1}\times N_{2}\times N_{3}}\), we use \(\mathcal{X}(i,:,:)\), \(\mathcal{X}(:,i,:)\), \(\mathcal{X}(:,:,i)\) to denote the \(i\)-th horizontal, lateral, and frontal slice, respectively. For simplicity, we denote the frontal slice \(\mathcal{X}(:,:,i)\) as \(X_{i}\). The inner product between \(\mathcal{X}\) and \(\mathcal{Y}\) of size \(N_{1}\times N_{2}\times N_{3}\) is defined as \(\left\langle\mathcal{X},\mathcal{Y}\right\rangle=\sum_{i=1}^{N_{3}}\text{tr} (X_{i}^{T}Y_{i})\). The Frobenius norm of a tensor is defined as \(\left\|\mathcal{X}\right\|_{\ell_{1}}=\sum_{i,j,k}\left|a_{ijk}\right|\). In this paper, the adopted basic definitions and notations follow the references [13; 21; 37] for the purpose of an easier comparison. **Definition 1** (Transpose p. 10 of [13]). : _For \(\mathcal{X}\in\mathbb{R}^{N_{1}\times N_{2}\times N_{3}}\), the transpose tensor \(\mathcal{X}^{\text{T}}\) is an \(N_{2}\times N_{1}\times N_{3}\) tensor obtained by transposing each frontal slice of \(\mathcal{X}\) and then reversing the order of the transposed frontal slices 2 through \(N_{3}\)._  
Similar to matrices whose elements can be grouped by rows or by columns, higher dimensional tensors can be viewed forming by slices along the third mode. For \(\mathcal{X}=[X_{1}|\cdots|X_{N_{3}}]\in\mathbb{R}^{N_{1}\times N_{2}\times N_{ 3}}\) with \(N_{1}\times N_{2}\) frontal slices \(X_{1},\ldots,X_{N_{3}}\). Then the block circulant is created from the frontal slices in a form of \[\mathrm{bcirc}(\mathcal{X})= \begin{bmatrix}X_{1}&X_{N_{3}}&X_{N_{3}-1}&\cdots&X_{2 }\\ X_{2}&X_{1}&X_{N_{3}}&\cdots&X_{3}\\ \vdots&\vdots&\vdots&\vdots&\vdots\\ X_{N_{3}}&X_{N_{3}-1}&\cdots&X_{2}&X_{1}\end{bmatrix} ,\]  
where \(X_{i}=\mathcal{X}(:,:,i)\) for \(i=1,\ldots,N_{3}\). It is important to notice that the block circulant matrix \(\mathrm{bcirc}(\mathcal{X})\) keeps the order of frontal slices of \(\mathcal{X}\) in an appropriate way, and thus it better maintains \(\mathcal{X}\)'s structure in terms of the frontal direction, compared with the direct tensor unfolding along the third mode. **Definition 2** (t-product p. 11 of [13]). : _Let \(\mathcal{X}\in\mathbb{R}^{N_{1}\times N_{2}\times N_{3}}\), we define the matvec and fold operators as \(\text{matvec}(\mathcal{X})= \begin{bmatrix}X_{1};X_{2},\cdots;X_{N_{3}}\end{bmatrix} \) is an \(N_{1}N_{3}\times N_{2}\) matrix and \(\text{fold}(\text{matvec}(\mathcal{X}))=\mathcal{X}\)._  
_Let \(\mathcal{A}\in\mathbb{R}^{N_{1}\times N_{4}\times N_{3}}\), and \(\mathcal{B}\in\mathbb{R}^{N_{4}\times N_{2}\times N_{3}}\). Then the t-product of 3 rd-order tensors is defined as_  
\[\mathcal{A}*\mathcal{B}=\text{fold}(\text{bcirc}(\mathcal{A})\text{matvec}( \mathcal{B}))\]  
_which is a tensor of size \(N_{1}\times N_{2}\times N_{3}\)._  
**Definition 3** (Identity, orthogonal and diagonal tensor p.10 of [13]). : _The identity tensor \(\mathcal{I}\in\mathbb{R}^{N_{1}\times N_{1}\times N_{3}}\) is a tensor whose first frontal slice is the \(N_{1}\times N_{1}\) identity matrix and all other frontal slices are zero. A tensor \(\mathcal{Q}\in\mathbb{R}^{N_{1}\times N_{1}\times N_{3}}\) is orthogonal if \(\mathcal{Q}^{\mathsf{T}}*\mathcal{Q}=\mathcal{Q}*\mathcal{Q}^{\mathsf{T}}= \mathcal{I}\), where \(*\) is the t-product. A tensor is called f-diagonal if each of its frontal slices is diagonal matrix._  
It is well known that circulant matrices can be diagonalized by the FFT (21.11 of [38]), similarly, block-circulant matrices can also block-diagonalized as  
\[