# Tensor Robust Principal Component Analysis via Non-Convex Low Rank Approximation
## 1 Introduction  
An array of numbers arranged on a regular grid with a variable number of axes is described as a tensor. As the dimensionality reaches beyond 3D, conventional data representations such as vector-based and matrix-based become insufficient, and highly dimensional data sets are usually formulated as tensors [1; 2; 3]. Robust Principal Component Analysis (RPCA) [4; 5; 6; 7; 8], aiming to recover the low-rank and sparse matrices both accurately and efficiently, has been widely studied in data compressed sensing and computer vision. It is of great use when we try to solve the problem of subspace learning or Principal Component Analysis (PCA) in the presence of outliers [9]. Especially RPCA is a very useful tool in foreground detection, which is the first step in video surveillance system to detect moving objects [10; 11]. Tensor Robust Principal Component Analysis (TRPCA) extends the RPCA from matrix to the tensor case, that is, to recover a low-rank tensor and a sparse (noise entries) tensor. Tensor rank [12] essentially characterizes the intrinsic \"dimension\" or \"degree of freedom\" for highly dimensional data sets. In order to make the rank characteristic be more transparent, one can make use of tensor Singular Value Decomposition (t-SVD) developed recently by [PERSON] and [PERSON] [13], rendering the tensor rank approximation approachable. The key for their framework is the well-defined t-product that leads to the 3 rd-order tensor space to be an inner product space so that approximation becomes more effective such as in image processing [14; 15]. t-SVD allows to define tensor tubal-rank, which appears to be much more approachable such as in the study of image analysisthan previous rank definitions [16; 17; 18]. The characteristic of a low tensor tubal-rank implies that a 3 rd-order tensor can be significantly compressed (Theorem 4.3 of [13]), which is particularly important in applications. Mathematically, TRPCA based on t-SVD [19; 20] aims to recover the low tubal rank component \(\mathcal{L}_{0}\) and sparse component \(\mathcal{E}_{0}\) from noisy observations \(\mathcal{X}=\mathcal{L}_{0}+\mathcal{E}_{0}\) of size \(N_{1}\times N_{2}\times N_{3}\) by convex optimization  
\[\min_{\mathcal{L},\mathcal{E}} \|\mathcal{L}\|_{TNN}+\lambda\|\mathcal{E}\|_{\ell_{1}}\] (1) s.t. \[\mathcal{X}=\mathcal{L}+\mathcal{E}. \tag{2}\]  
\(\lambda\) is a Lagrange multiplier, \(\mathcal{E}\) is sparse if the tensor \(\ell_{1}\) norm \(\|\mathcal{E}\|_{\ell_{1}}\) is small. It is well-known that the t-SVD-based tensor nuclear norm (TNN, III.B of [21]) has been proven to be the tightest convex relaxation to \(\ell_{1}\)-norm of the tensor multi-rank (Theorem 2.4.1 in [15] or Theorem 3.1 in [19]). However, TNN treats the singular values in t-SVD equally to pursue the convexity of the objective function, while the singular values associated with a practical image may emphasize its different properties and should be handled differently, in particular, when some singular values are very large. Due to the gap between the tensor rank function and its lower convex envelop, the adoption of tensor nuclear norm may lead to the approximation of the corresponding tensor tubal-rank being inaccurate. Therefore, a new development of tensor tubal-rank approximation becomes necessary to reflect these fundamental characteristics. To make the the necessity of a new tensor tubal-rank approximation instead of TNN more transparent, we consider the the matrix RPCA [4] first. Now the goal becomes to recover a low-rank matrix \(L\) from highly corrupted observations \(X=L+S\), by minimizing \(\|L\|_{*}+\lambda\|S\|_{\ell_{1}}\). Here \(\|L\|_{*}\) is the summation of the singular values of \(L\). It is easy to see that  
\[1+\frac{\sigma_{2}}{\sigma_{1}}+\cdots+\frac{\sigma_{N}}{\sigma_{1}}=\frac{1}{ \sigma_{1}}\|L\|_{*}\leq\text{rank}(L).\]  
Hence, when \(\sigma_{1}\) is very large, for example, and the rest are relatively small, we may have \(\frac{1}{\sigma_{1}}\|L\|_{*}<<\text{rank}(L)\).