Tensor Robust Principal Component Analysis via Hybrid Truncation Norm

Yujie Luan¹, Wei Jiang²

¹School of Mathematics, Liaoning Normal University, Dalian, China.
²College of Computer Science and Artificial Intelligence, Wenzhou University, Wenzhou, China.

DOI: 10.4236/oalib.1109412                

Abstract

This paper mainly studies the problem of tensor robust principal component analysis (TRPCA), in order to accurately recover the low rank and sparse components from the observed signals. Most of the existing robust principal component analysis (RPCA) methods are based on nuclear norm minimizationss. These methods minimize all singular values at the same time, so they can not approach the rank well in practice. In this paper, the idea of truncated nuclear norm regularization is extended to RPCA. At the same time, in order to improve the stability of the model, the tensor truncated Frobenius norm is newly defined. Truncated nuclear norm and truncated Frobenius norm are considered at the same time called hybrid truncated model of tensor. This method minimizes min singular values. In addition, this paper also gives an effective method to determine the contraction operator, and develops an effective iterative algorithm based on alternating direction to solve this optimization problem. Experimental results show the effectiveness and accuracy of this method.

Keywords

Tensor Robust Principal Component Analysis (TRPCA), Hybrid Truncation Norm , Alternating Direction Multiplier Method (ADMM)

1. Introduction

Tensor is a multidimensional extension of matrix and an important data format, which can express the internal structure of more complex high-order data. In fact, tensor is also the natural form of high-dimensional and multi-way real-world data. For example, in the field of image processing [1], a color image is a 3-order tensor of height × weight × channel and a multispectral image is a 3-order tensor of height × weight × channel. Therefore, tensor analysis has important practical significance and application value in the fields of machine learning [2], computer vision [3], data mining [4], and so on. The tensor, we interest, is frequently low-rank, or approximately so [5] and hence has a much lower-dimensional structure. This has stimulated the problem of low rank tensor estimation and recovery, which has attracted great attention in many different fields. The classical principal component analysis (PCA) [6] is the most widely used method for data analysis and dimensionality reduction. For the data slightly damaged by small noise, it has the characteristics of high computational efficiency and powerful function. However, a major problem with principal component analysis is that it is easily affected by seriously damaged or bizarre observations, which are ubiquitous in real-world data. So far, many principal component analysis models [7] [8] have been proposed, but almost all of them have high computational cost.

RPCA is the first polynomial time algorithm with strong performance guarantee. Suppose that we are given an observed $X\in {ℝ}^{m\times n}$ , which can be decomposed as $X=L_0+E_0$ , where $L_0$ is low-rank and $E_0$ is sparse. [6] shows that if the singular vector of $L_0$ satisfies some incoherent conditions, such as $L_0$ is low rank and $E_0$ is sparse enough, $L_0$ and $E_0$ can be recovered accurately with high probability by solving the convex problem (1):

$\underset{L,E}{\min }{\Vert L\Vert }_{\ast }+\lambda {\Vert E\Vert }_1$ (1)

where ${\Vert L\Vert }_{\ast }$ denotes the nuclear norm (sum of the singular values of $L$ ), and ${\Vert E\Vert }_1$ denotes the ${\mathcal{l}}_1$ -norm (sum of the absolute values of all the entries of $E$ ). The parameter $\lambda$ is suggested to be set as $1/\sqrt{\max \left(n_1,n_2\right)}$ which works well in practice. In terms of algorithm, (1) can be solved by efficient algorithm, and the cost will not be much higher than PCA. This method and its generalization have been successfully applied to the fields of background modeling [9], subspace clustering [10], video compression sensing [11] and so on.

A major disadvantage of RPCA is that it can only process two-dimensional (matrix) data. However, real data is usually multi-dimensional in nature-the information is stored in multi-way arrays known as tensors [5]. To use RPCA, we must first convert the high-dimensional data into a matrix. However, such preprocessing usually leads to information loss, resulting in performance degradation. In order to alleviate this problem, a common method is to use the multidimensional structure of tensor data to deal with it.

In this paper, tensor robust principal component analysis (TRPCA) is studied in order to accurately recover the low rank tensor damaged by sparse noise. Suppose that we are given an observed $\mathcal{X}$ , which can be decomposed as $\mathcal{X}={\mathcal{L}}_0+{\mathcal{E}}_0$ , where ${\mathcal{L}}_0$ is low-rank and ${\mathcal{E}}_0$ is sparse, and both components are of arbitrary magnitudes. Note that we do not know the locations of the nonzero elements of ${\mathcal{E}}_0$ , not even how many there are. Now we consider a similar problem to RPCA. This is the problem of tensor RPCA studied in this work.

It is not easy to generalize RPCA to tensor. The main problem of low rank tensor estimation is the definition of tensor rank [12]. At present, several definitions of tensor rank and its convex relaxation have been proposed, but each rank has its limitations. The CANDECOMP/PARAFAC (CP) rank of tensor [5] is defined as the minimum number of tensor rank 1 decomposition, which is NP-hard to calculate. Because of its unclear convex envelope, the recovery of low CP rank tensor is challenging [13]. A robust tensor CP decomposition problem is studied. Although the recovery is guaranteed, the algorithm is nonconvex. To avoid this problem, Tucker et al. presented the tractable Tucker rank [14], and its convex relaxation has also been widely used. For a k-way tensor $\mathcal{X}$ , The Tucker rank is a vector defined as $ran{k}_{tc}\left(\mathcal{X}\right)\mathrm{<mo>\; :\; </mo>}=\left(rank\left(X^{\left\{1\right\}}\right)\mathrm{,}rank\left(X^{\left\{2\right\}}\right)\mathrm{,}\cdots \mathrm{,}rank\left(X^{\left\{k\right\}}\right)\right)$ . Motivated by the fact that the nuclear norm is the convex envelope of the matrix rank within the unit ball of the spectral norm, the Sum of Nuclear Norms (SNN) [15], defined as ${\displaystyle {\sum }_i}{\Vert X^{\left(i\right)}\Vert }_{\ast }$ , is used as a convex surrogate of ${\displaystyle {\sum }_i}rank\left(X^{\left\{i\right\}}\right)$ . [16] gives a TRPCA model based on SNN:

$\begin{array}{l}\underset{\mathcal{L},\mathcal{E}}{\min }{\displaystyle \underset{i=1}{\overset{k}{\sum }}}{\lambda }_i{\Vert L^{\left\{i\right\}}\Vert }_{\ast }+{\Vert E\Vert }_1\\ \text{s}\text{.t}\text{.}\mathcal{X}=\mathcal{L}+\mathcal{E}\mathrm{.}\end{array}$ (2)

[17] fully studied the effectiveness of this method. However, SNN is still not the tightest convex relaxation of Tucker rank. In other words, the model (2) is basically suboptimal. Recently, with the introduction of tensor product (T-product) [18] and tensor singular value decomposition (T-SVD), Kilmer et al. [15] proposed the definitions of tensor multi rank and tubal rank. Then a new tensor nuclear norm appears and is applied to tensor completion [19] and tensor robust principal component analysis [20]. In [21], the author realized that tensor product is based on convolution like operation, which can be realized by using discrete Fourier transform (DFT). Soon after, a more general definition of tensor product was proposed, which was based on arbitrary reversible linear transformation. Lu et al. [22] accurately recover the low rank and sparse components by solving a weighted combined convex programming of tensor nuclear norm and tensor ${\mathcal{l}}_1$ -norm that is:

$\begin{array}{l}\underset{\mathcal{L},\mathcal{E}}{\min }{\Vert \mathcal{L}\Vert }_{\ast }+{\Vert \mathcal{E}\Vert }_1\\ \text{s}\text{.t}\text{.}\mathcal{X}=\mathcal{L}+\mathcal{E}\mathrm{.}\end{array}$ (3)

However, due to the nuclear norm considers each singular value of the tensor, and each singular value has different influence on the results. Therefore, [23] proposed the partial sum of tensor tube nuclear norm (PSTNN), and established a minimization model based on PSTNN to solve the tensor RPCA problem. Although the truncated nuclear norm can be used as a convex alternative to the rank function, the model lacks strong stability. The high stability of the model means that the elements of the output data set do not change significantly. [24] proposed a hybrid model of truncated nuclear norm and truncated Frobenius norm for matrix completion. In this model, nuclear norm controls low rank attribute and Frobenius norm controls stability.

Inspired by [24], we propose a new tensor robust principal component analysis method, trying to establish a more stable and ideal model. The main contributions are summarized as follows.

1) We propose two new regularization terms, tensor truncated nuclear norm (T-TNN) and tensor truncated Frobenius norm (T-TFN). Respectively, T-TNN is defined as the sum of the last min $\left(m\mathrm{,}n\right)-r$ singular values of all frontal slices of $\bar{\mathcal{A}}$ . T-TFN is defined as the square root of the square sum of the last min $\left(m\mathrm{,}n\right)-r$ singular values of all frontal slices of $\bar{\mathcal{A}}$ . Based on these two new definitions, a tensor hybrid truncated norm (T-HTN) regularization model is proposed, which uses the combination of T-TNN and T-TFN to achieve tensor TRPCA. The model not only improves the stability, but also effectively improves the accuracy of recovery accuracy.

2) A simple two-step iterative algorithm is designed to solve the proposed T-HTN model. Then the convergence of the method is deduced to ensure the feasibility of the algorithm. In order to reduce the cost of computation, we allow the quadratic penalty parameters to change adaptively according to some update rules.

3) A large number of experiments are carried out on synthetic data and real images. The experimental results show the advantages of this method in effectiveness and stability.

The rest of this paper is organized as follows. Section II introduces some notations, and presents some new tensor norm induced by the transform-based T-product. In Section III, we propose the T-HTN regularization model and give the optimization method to solve it. The Section IV gives the experimental results of synthetic and real data. The Section V draws a conclusion.

2. Preliminaries

2.1. Notations

In this section, we give some notations used in this paper. We denote scalars by lowercase letters, e.g., $a$ , vectors by boldface lowercase letters, e.g., $a$ , matrices by boldface capital letters, e.g., $A$ , and tensors by boldface Euler script letters, e.g., $\mathcal{A}$ . Respectively, the field of real number and complex number are denoted as $ℝ$ and $ℂ$ . For a 3-way tensor $\mathcal{A}\in {ℂ}^{n_1\times n_2\times n_3}$ , we denote its $\left(i\mathrm{,}j\mathrm{,}k\right)$ -th entry as ${\mathcal{A}}_{ijk}$ or $a_{ijk}$ and use the MATLAB notation $\mathcal{A}\left(i\mathrm{,\; <mo>\; :\; </mo>,\; <mo>\; :\; </mo>}\right)$ , $\mathcal{A}\left(\mathrm{<mo>\; :\; </mo>,}i\mathrm{,\; <mo>\; :\; </mo>}\right)$ , $\mathcal{A}\left(\mathrm{<mo>\; :\; </mo>,\; <mo>\; :\; </mo>,}i\right)$ to denote separately the i-th horizontal, lateral and frontal slice [25]. Ordinarily, the frontal slice $\mathcal{A}\left(\mathrm{<mo>\; :\; </mo>,\; <mo>\; :\; </mo>,}i\right)$ is denoted as $A^{\left(i\right)}$ . The $\left(i\mathrm{,}j\right)$ -th tube of $\mathcal{A}$ is denoted by $\mathcal{A}\left(i\mathrm{,}j\mathrm{,\; <mo>\; :\; </mo>}\right)$ , which is a vector of length $n_3$ . For two matrices $A$ and $B$ in ${ℂ}^{n_1\times n_2}$ , we represent their inner product as $\langle A\mathrm{,}B\rangle =\text{Tr}\left(A^{\text{T}}B\right)$ , where $\text{Tr}(\cdot )$ stands for the trace, and $A^{\text{T}}$ is the conjugate transpose of $A$ . The $n\times n$ identity matrix is denoted by $I_n$ . Moreover, for any two tensors $\mathcal{A}$ and $\mathcal{B}$ in ${ℂ}^{n_1\times n_2\times n_3}$ , $\langle \mathcal{A}\mathrm{,}\mathcal{B}\rangle ={\displaystyle {\sum }_{i=1}^{n_3}}\langle A^{\left(i\right)}\mathrm{,}{B}^{\left(i\right)}\rangle$ . Some norms of tensor are also used. The Frobenius norm of a tensor is defined as ${\Vert \mathcal{A}\Vert }_F=\sqrt{{\displaystyle {\sum }_{ijk}}{\left|{\mathcal{A}}_{ijk}\right|}^2}$ and the ${\mathcal{l}}_1$ norm is defined as ${\Vert \mathcal{A}\Vert }_1={\displaystyle {\sum }_{ijk}}\left|{\mathcal{A}}_{ijk}\right|$ . The above norms are also defined in this way in a vector or matrix.

Let $L\mathrm{<mo>\; :\; </mo>}{ℝ}^{n_1\times n_2\times n_3}\to {ℂ}^{n_1\times n_2\times n_3}$ be invertible linear transform on tensor space. $L^{-1}$ is the inverse transform of L. $\bar{\mathcal{A}}$ is obtained via linear transform L on each tube fiber of $\mathcal{A}$ , i.e., $\bar{\mathcal{A}}=L\left(\mathcal{A}\right)$ , and $\mathcal{A}=L^{-1}\left(\bar{\mathcal{A}}\right)$ .

We define a block diagonal matrix based on frontal slice as

$\bar{A}=\text{bdiag}\left(\bar{\mathcal{A}}\right)=\left[\begin{array}{cccc}{\bar{A}}^{\left(1\right)}& & & \\ & {\bar{A}}^{\left(2\right)}& & \\ & & \ddots & \\ & & & {\bar{A}}^{\left(n_3\right)}\end{array}\right]\mathrm{,}$ (4)

where the $\text{bidiag}(\cdot )$ is an operator, maps the tensor $\bar{\mathcal{A}}$ to the block diagonal matrix $\bar{A}$ size $n_1{n}_3\times n_2{n}_3$ . On the contrary, $\text{unbdiag}(\cdot )$ maps the block diagonal matrix into a tensor:

$\text{unbdiag}\left(\text{bdiag}\left(\bar{\mathcal{A}}\right)\right)=\bar{\mathcal{A}}\mathrm{.}$ (5)

where $\text{unbdiag}(\cdot )$ denotes the inverse operator of $\text{bdiag}(\cdot )$ .

The block circulant matrix $\text{bcirc}\left(\mathcal{A}\right)\in {ℝ}^{n_1\times n_2\times n_3}$ of $\mathcal{A}$ is defined as

$\text{bcirc}\left(\mathcal{A}\right)=\left[\begin{array}{cccc}{A}^{\left(1\right)}& A^{\left(n_3\right)}& \cdots & A^{\left(2\right)}\\ A^{\left(2\right)}& A^{\left(1\right)}& \cdots & A^{\left(3\right)}\\ ⋮& ⋮& \ddots & ⋮\\ A^{\left(n_3\right)}& A^{\left(n_3-1\right)}& \cdots & A^{\left(1\right)}\end{array}\right]$

Lemma 1 Given any real vector $v\in {ℝ}^n$ , the associated $v$ satisfies $v_1\in {ℝ}^n$ and

$\text{conj}\left({\bar{v}}_i\right)={\bar{v}}_{n-i+2},i=2,\cdots ,\lfloor \frac{n+1}{2}\rfloor .$ (6)

Conversely, for any given complex $\bar{v}\in {ℂ}^n$ , [6] is established.

By using Lemma 1, we have

$\{\begin{array}{l}{\bar{A}}^{\left(1\right)}\in {ℝ}^{n_1\times n_2}\hfill \\ \text{conj}\left({\bar{A}}^{\left(i\right)}\right)={\bar{A}}^{\left(n_{\text{3}}-i+2\right)}\mathrm{,}i=\mathrm{2,}\cdots \mathrm{,}\lfloor \frac{n_3+1}{2}\rfloor \hfill \end{array}$ (7)

2.2. Preliminaries

In this part, we will give relevant definitions and theorems.

Now, a pair of folding operators are defined as follows. For a tensor $\mathcal{A}\in {ℝ}^{n_1\times n_2\times n_3}$ , we define

$\text{unfold}\left(\mathcal{A}\right)=\left[\begin{array}{c}{A}^{\left(1\right)}\\ A^{\left(2\right)}\\ ⋮\\ A^{\left(n_3\right)}\end{array}\right]\mathrm{,}\text{fold}\left(\text{unfold}\left(\mathcal{A}\right)\right)=\mathcal{A}\mathrm{.}$

where the operator maps the tensor $\mathcal{A}$ to a matrix of size $n_1{n}_3\times n_2$ and fold is its inverse operator.

Definition 1 (T-product) [26] Consider that L is an arbitrary invertible linear transform. The T-product between tensor $\mathcal{A}\in {ℝ}^{n_1\times n_2\times n_3}$ and $\mathcal{B}\in {ℝ}^{n_2\times n_4\times n_3}$ based on L is defined as

$\mathcal{C}=\mathcal{A}{\ast }_L\mathcal{B}=L^{-1}\left(\text{unbdiag}\left(\text{bdiag}\left(\bar{\mathcal{A}}\right)\times \text{bdiag}\left(\bar{\mathcal{B}}\right)\right)\right)$ (8)

where $L^{-1}$ is the inverse transform of L, and × denotes the standard matrix product.

T-product is similar as matrix product, except that cyclic convolution is used to replace the multiplication between elements. When $n_3=1$ , the T-product simplifies to the standard matrix product.

Definition 2 (Tensor transpose) [26] Let L be an arbitrary invertible linear transform. For a tensor $\mathcal{A}\in {ℝ}^{n_1\times n_2\times n_3}$ , the tensor transpose of $\mathcal{A}$ is defined as ${\mathcal{A}}^{\text{T}}$ , satisfies $L{\left({\mathcal{A}}^{\text{T}}\right)}^{\left(i\right)}={\left(L{\left(\mathcal{A}\right)}^{\left(i\right)}\right)}^{\text{T}}\mathrm{,}i=\mathrm{1,}\cdots \mathrm{,}{n}_3$ .

Definition 3 (Identity tensor) Suppose that L is any invertible linear transform. Tensor $\mathcal{I}\in {ℝ}^{n\times n\times n_3}$ is an identity tensor if the first frontal slice of $L\left(\mathcal{I}\right)$ is a $n\times n$ sized identity matrix and whose other frontal slices being all zeros.

It is clear that $\mathcal{A}{\ast }_L\mathcal{I}=\mathcal{A}$ and $\mathcal{I}{\ast }_L\mathcal{A}=\mathcal{A}$ given the appropriate dimensions. The tensor $\bar{\mathcal{I}}=fft\left(\mathcal{I}\mathrm{,}\left[\right]\mathrm{,3}\right)$ is a tensor that each frontal slice being the identity matrix.

Definition 4 (Orthogonal tensor) Consider that L is any invertible linear transform. Tensor $\mathcal{Q}\in {ℝ}^{n\times n\times n_3}$ is orthogonal if it satisfies ${\mathcal{Q}}^{\text{T}}{\ast }_L\mathcal{Q}=\mathcal{Q}{\ast }_L{\mathcal{Q}}^{\text{T}}=\mathcal{I}$ .

Definition 5 (F-diagonal tensor) Tensor $\mathcal{A}\in {ℝ}^{n_1\times n_2\times n_3}$ is said to be an F-diagonal tensor if each frontal slice of $L\left(\mathcal{A}\right)$ is a diagonal matrix via an arbitrary invertible linear transform L.

Definition 6 (Inverse tensor) A frontal square tensor $\mathcal{A}$ of size $n\times n\times n_3$ has an inverse tensor $\mathcal{B}={\mathcal{A}}^{-1}$ provided.

$\mathcal{A}{\ast }_L\mathcal{B}=\mathcal{I}$ and $\mathcal{B}{\ast }_L\mathcal{A}=\mathcal{I}$ . (9)

Theorem 1 (T-SVD) Suppose that L is an arbitrary invertible linear transform and $\mathcal{A}\in {ℝ}^{n_1\times n_2\times n_3}$ . Then, T-SVD of $\mathcal{A}$ is given by

$\mathcal{A}=\mathcal{U}{\ast }_L\mathcal{S}{\ast }_L{\mathcal{V}}^{\text{T}}\mathrm{,}$ (10)

where $\mathcal{U}{\ast }_L{\mathcal{U}}^{\text{T}}=\mathcal{I}$ , $\mathcal{V}{\ast }_L{\mathcal{V}}^{\text{T}}=\mathcal{I}$ , and $\mathcal{S}\in {ℝ}^{n_2\times n_2\times n_3}$ is an F-diagonal tensor.

The specific process will be presented in algorithm 1

Definition 7 (Tensor multi-rank and tubal rank) For $\mathcal{A}\in {ℝ}^{n_1\times n_2\times n_3}$ , let L be an arbitrary invertible linear transform satisfying $L^{\text{T}}L=L{L}^{\text{T}}=\mathcal{l}{I}_{n_3}$ with $\mathcal{l}>0$ being a constant. The tensor multi-rank is a vector denoted as $ran{k}_m\left(\mathcal{A}\right)={\left(rank{\left(\bar{A}\right)}^{\left(1\right)}\mathrm{,}\cdots \mathrm{,}rank{\left(\bar{A}\right)}^{\left(n_3\right)}\right)}^{\text{T}}$ . The tensor tubal rank is defined as the number of nonzero singular tubes of $\mathcal{S}$ , i.e.,

$ran{k}_t\left(\mathcal{A}\right)=\mathrm{<mo>\; \#\; </mo>}\left\{i\mathrm{,}\mathcal{S}\left(i\mathrm{,}i\mathrm{,\; <mo>\; :\; </mo>}\right)\ne 0\right\}=\mathrm{<mo>\; \#\; </mo>}\left\{i\mathrm{,}\mathcal{S}\left(i\mathrm{,}i\mathrm{,1}\right)\ne 0\right\}\mathrm{.}$ (11)

Definition 8 (TNN) Assume that $\mathcal{A}\in {ℝ}^{n_1\times n_2\times n_3}$ with corresponding T-SVD $\mathcal{A}=\mathcal{U}{\ast }_L\mathcal{S}{\ast }_L{\mathcal{V}}^{\text{T}}$ ; its tensor nuclear norm is defined as the sum of the singular values of all frontal slices of $\bar{\mathcal{A}}$ , i.e.

${\Vert \mathcal{A}\Vert }_{\ast }={\displaystyle \underset{i=1}{\overset{r}{\sum }}}\mathcal{S}\left(i\mathrm{,}i\mathrm{,1}\right)=\langle \mathcal{S}\mathrm{,}\mathcal{I}\rangle =\frac{1}{n_3}{\Vert \bar{A}\Vert }_{\ast }\mathrm{,}$ (12)

Theorem 2 (Tensor Singular Value Thresholding) For any $\tau >0$ and $\mathcal{Y}\in {ℝ}^{n_1\times n_2\times n_3}$ , the solution of the problem

$\underset{\mathcal{X}}{\min }\tau {\Vert \mathcal{X}\Vert }_{\ast }+\frac{1}{2}{\Vert \mathcal{X}-\mathcal{Y}\Vert }_F^2\mathrm{,}$ (13)

is given by ${\mathcal{D}}_{\tau }\left(\mathcal{Y}\right)$ , which is defined as

${\mathcal{D}}_{\tau }\left(\mathcal{Y}\right)=\mathcal{U}{\ast }_L{\mathcal{S}}_{\tau }{\ast }_L{\mathcal{V}}^{\text{T}}\mathrm{,}$ (14)

where ${\mathcal{S}}_{\tau }=L^{-1}\left({\left(\bar{\mathcal{S}}-\tau \right)}_{+}\right)$ with $x_{+}=\text{max}\left(x\mathrm{,0}\right)$ .

Definition 9 (Tensor Frobenius norm (TFN)) For any $\mathcal{A}\in {ℝ}^{n_1\times n_2\times n_3}$ , the tensor Frobenius norm of $\mathcal{A}$ is defined as

${\Vert \mathcal{A}\Vert }_F=\sqrt{\langle \mathcal{A}\mathrm{,}\mathcal{A}\rangle }=\frac{1}{\sqrt{n_3}}{\Vert \bar{A}\Vert }_F\mathrm{.}$ (15)

2.3. Background

In this section, we briefly review the early work related to RPCA, and then discuss some recent developments of TRPCA and its application in computer vision.

RPCA tries to separate a low rank matrix $L\in {ℝ}^{n_1\times n_2}$ and a sparse matrix $E\in {ℝ}^{n_1\times n_2}$ from their sum $M=L+E$ . As shown in [2], when the underlying tensor $L$ satisfies the matrix incoherence conditions, the solution of the following problem:

$\begin{array}{l}\underset{L,E}{\min }{\Vert L\Vert }_{\ast }+\lambda {\Vert E\Vert }_1\\ \text{s}\text{.t}\mathrm{.}L+E=M\end{array}$ (16)

can highly recover $L$ and $E$ with high probability with parameter $\lambda =1/\sqrt{\max \left(n_1,n_2\right)}$ . In order to solve (16), various methods have been proposed [27]. Among them, Alternating Direction Method of Multipliers (ADMM, or also known as inexact augmented Lagrange multiplier) are widely used. In addition, Zhou et al. and Agarwal et al. [1] proved that even under small noise measurements, convex approximation by nuclear norm can still achieve bounded and stable results.

Unlike the matrix case, it is very difficult to define tensor rank. Many versions of tensor rank are proposed [5] [28]. Using the matricization, converting the tensor into matrix, Lu et al. [14] introduced the tensor nuclear norm as ${\Vert \mathcal{A}\Vert }_{\ast }=\frac{1}{n_3}{\Vert \bar{A}\Vert }_{\ast }$ , where $\mathcal{A}\in {ℝ}^{n_1\times n_2\times n_3}$ . Then, TRPCA is then given by

$\begin{array}{l}\underset{\mathcal{L},\mathcal{E}}{\min }{\Vert \mathcal{L}\Vert }_{\ast }+{\Vert \mathcal{E}\Vert }_1\\ \text{s}\text{.t}\text{.}\mathcal{X}=\mathcal{L}+\mathcal{E}\mathrm{.}\end{array}$

But the rank function may not be well approximated by nuclear norm. To overcome this problem, the T-TNN method was proposed in [29], which proposes a new definition of tensor nuclear norm, extends the truncated nuclear norm from the matrix case to the tensor case:

${\Vert \mathcal{A}\Vert }_{\ast }=Tr\left(\mathcal{S}\right)=Tr\left({\bar{\mathcal{S}}}^{\left(1\right)}\right)={\Vert {\bar{A}}^{\left(1\right)}\Vert }_{\ast }$

Afterwards, Jiang et al. [2] propose the partial sum of the tubal nuclear norm (PSTNN) of a tensor.

${\Vert \mathcal{A}\Vert }_{\text{PSTNN}}={\displaystyle \underset{i=1}{\overset{n_3}{\sum }}}{\Vert {\hat{\mathcal{A}}}^{\left(i\right)}\Vert }_{P=N}$

The tensor RPCA model using PSTNN was formulated as

$\begin{array}{l}\underset{\mathcal{L},\mathcal{E}}{\min }{\Vert \mathcal{L}\Vert }_{\text{PSTNN}}+{\Vert \mathcal{E}\Vert }_1\\ \text{s}\text{.t}\text{.}\mathcal{O}=\mathcal{L}+\mathcal{E}\mathrm{.}\end{array}$

The PSTNN is a surrogate of the tensor tubal multi-rank. Though PSTNN is a better approximation to the rank function, the stability issue is still challenging.

3. Tensor Robust Principal Component Analysis Based on Mixed Truncated Norm (T-HTN)

In this section, we mainly introduce the tensor truncated nuclear norm(T-TNN) and tensor truncated Frobenius norm (T-TFN) newly defined in this paper, and propose a tensor hybrid truncated norm(T-HTN) regularization model to improve effectiveness and stability. In addition, the iterative strategy is given.

3.1. T-HTN Model

As mentioned earlier, T-TNN is a better approximation of the rank function, which only considers the last min $\left(m\mathrm{,}n\right)-r$ singular value [30]. Since Frobenius norm can improve stability, we consider using Frobenius norm term to enhance stability, but the traditional Frobenius norm still needs to consider all singular values, which will make our T-TNN ineffective, which urges us to only consider the last min $\left(m\mathrm{,}n\right)-r$ singular values for enhancing stability in the definition of Frobenius norm. Based on these analyses, we will construct a more reasonable regularization term called “tensor truncated Frobenius norm (T-TFN)” to replace the original Frobenius norm and match it with T-TNN. Firstly, we give the T-TNN and T-TFN defined in this paper:

Definition 10 (Tensor truncated nuclear norm (T-TNN)) For $\mathcal{A}\in {ℝ}^{n_1\times n_2\times n_3}$ , the tensor truncated nuclear norm ${\Vert \mathcal{A}\Vert }_{r,\ast }$ is defined as the sum of the last min $\left(m\mathrm{,}n\right)-r$ singular values of all frontal slices of $\bar{\mathcal{A}}$ , i.e.,

$\begin{array}{c}{\Vert \mathcal{A}\Vert }_{r,\ast }=\frac{1}{n_3}{\displaystyle \underset{i=1}{\overset{n_3}{\sum }}}{\displaystyle \underset{j=r+1}{\overset{\min \left(n_1,n_2\right)}{\sum }}}\left({\sigma }_j\left({\bar{A}}^{\left(i\right)}\right)\right)\\ ={\Vert \mathcal{A}\Vert }_{\ast }-\frac{1}{n_3}{\displaystyle \underset{i=1}{\overset{n_3}{\sum }}}{\displaystyle \underset{j=1}{\overset{r}{\sum }}}\left({\sigma }_j\left({\bar{A}}^{\left(i\right)}\right)\right)\end{array}$ (17)

where ${\sigma }_j\left({\bar{A}}^{\left(i\right)}\right)$ denotes the j-th largest singular value of ${\bar{A}}^{\left(i\right)}\in {ℝ}^{n_1\times n_2}$ .

Definition 11 (Tensor truncated Frobenius norm (T-TFN)) Given a tensor $\mathcal{A}\in {ℝ}^{n_1\times n_2\times n_3}$ , the tensor truncated Frobenius norm (T-TFN) nuclear norm ${\Vert \mathcal{A}\Vert }_{r\mathrm{,}F}$ is defined as the square root of the square sum of the last min $\left(m\mathrm{,}n\right)-r$ singular values of all frontal slices of $\bar{\mathcal{A}}$ , i.e.,

${\Vert \mathcal{A}\Vert }_{r\mathrm{,}F}=\frac{1}{\sqrt{n_3}}{\displaystyle \underset{i=1}{\overset{n_3}{\sum }}}\sqrt{{\displaystyle \underset{j=1}{\overset{\min \left(n_1\mathrm{,}{n}_2\right)}{\sum }}}{\left({\sigma }_j\left({\bar{A}}^{\left(i\right)}\right)\right)}^2-{\displaystyle \underset{j=1}{\overset{r}{\sum }}}{\left({\sigma }_j\left({\bar{A}}^{\left(i\right)}\right)\right)}^2}\mathrm{.}$ (18)

Therefore, ${\Vert \mathcal{A}\Vert }_{r_{r}F}^2$ can be defined as

$\begin{array}{c}{\Vert \mathcal{A}\Vert }_{r\mathrm{,}F}^2=\frac{1}{n_3}{\displaystyle \underset{i=1}{\overset{n_j}{\sum }}}{\displaystyle \underset{j=r+1}{\overset{\min \left(n_1,n_2\right)}{\sum }}}{\left({\sigma }_j\left({\bar{A}}^{\left(i\right)}\right)\right)}^2\\ ={\Vert \mathcal{A}\Vert }_F^2-\frac{1}{n_3}{\displaystyle \underset{i=1}{\overset{n_3}{\sum }}}{\displaystyle \underset{j=1}{\overset{r}{\sum }}}{\left({\sigma }_j\left({\bar{A}}^{\left(i\right)}\right)\right)}^2\end{array}$ (19)

Evidently, T-TFN could perfectly correspond to T-TNN as they both only concern the influence of the last min $\left(m\mathrm{,}n\right)-r$ singular values. Therefore, the two can be combined to establish a more effective hybrid truncated tensor robust principal component model (T-HTN):

$\begin{array}{l}\underset{\mathcal{L},\mathcal{E}}{\min }\mathrm{<mo>\; :\; </mo>}{\Vert \mathcal{L}\Vert }_{r,\ast }+\gamma {\Vert \mathcal{L}\Vert }_{r\mathrm{,}F}^2+\lambda {\Vert \mathcal{E}\Vert }_1\\ \text{s}\text{.t}\text{.}\mathcal{X}=\mathcal{L}+\mathcal{E}\mathrm{.}\end{array}$ (20)

Since ${\Vert \mathcal{L}\Vert }_{r,\ast }+\gamma {\Vert \mathcal{L}\Vert }_{r\mathrm{,}F}^2$ is nonconvex, it is not easy to solve the model (19). To this end, we establish the following theorems.

Theorem 3 For any $\mathcal{L}\in {ℝ}^{n_1\times n_2\times n_3}$ with corresponding T-SVD $\mathcal{L}=\mathcal{A}{\ast }_L\mathcal{S}{\ast }_L{\mathcal{B}}^{\text{T}}$ , the following formula holds:

${\Vert \mathcal{L}\Vert }_{r,\ast }={\Vert \mathcal{L}\Vert }_{\ast }-\underset{\begin{array}{l}\mathcal{A}{\ast }_L{\mathcal{A}}^{\text{T}}=\mathcal{I}\\ {\mathcal{B}}^{\text{T}}{\ast }_L\mathcal{B}=\mathcal{I}\end{array}}{\max }Tr\left(\mathcal{A}{\ast }_L\mathcal{S}{\ast }_L{\mathcal{B}}^{\text{T}}\right)$ (21)

Theorem 4 For any $\mathcal{L}\in {ℝ}^{n_1\times n_2\times n_3}$ with corresponding T-SVD $\mathcal{L}=\mathcal{A}{\ast }_L\mathcal{S}{\ast }_L{\mathcal{B}}^{\text{T}}$ , the following formula holds:

${\Vert \mathcal{L}\Vert }_{r\mathrm{,}F}^2={\Vert \mathcal{L}\Vert }_F^2-\underset{\mathcal{A}{\ast }_L{\mathcal{A}}^{\text{T}}=\mathcal{I}}{\max }{\Vert \mathcal{A}{\ast }_L\mathcal{L}\Vert }_F^2$ (22)

Through the above theorems, Equation (19) can be rewritten as

$\begin{array}{l}\underset{\mathcal{L},\mathcal{E}}{\min }\mathrm{<mo>\; :\; </mo>}{\Vert \mathcal{L}\Vert }_{\ast }-\underset{\begin{array}{l}\mathcal{A}{\ast }_L{\mathcal{A}}^{\text{T}}=\mathcal{I}\\ {\mathcal{B}}^{\text{T}}{\ast }_L\mathcal{B}=\mathcal{I}\end{array}}{\max }Tr\left(\mathcal{A}{\ast }_L\mathcal{L}{\ast }_L{\mathcal{B}}^{\text{T}}\right)\\ +\gamma \left({\Vert \mathcal{L}\Vert }_F^2-\underset{{\mathcal{A}}^{\text{T}}\mathcal{A}=\mathcal{I}}{\max }{\Vert \mathcal{A}{\ast }_L\mathcal{L}\Vert }_F^2\right)+\lambda {\Vert \mathcal{E}\Vert }_1\\ \text{s}\text{.t}\text{.}\mathcal{X}=\mathcal{L}+\mathcal{E}\end{array}$ (23)

3.2. Solving Scheme

In order to solve the optimization problem (22), we will exploit an efficient iterative approach, which is divided into two steps. Firstly, we define ${\mathcal{L}}_0=\mathcal{O}$ as the initial value of $\mathcal{L}$ . At the l-th iteration, fix ${\mathcal{L}}_l$ and perform the T-SVD with ${\mathcal{L}}_l=\mathcal{U}{\ast }_L\mathcal{Q}{\ast }_L{\mathcal{V}}^{\text{T}}$ , where $\mathcal{U}\in {ℝ}^{n_1\times r\times n_3}$ , $\mathcal{V}\in {ℝ}^{n_2\times r\times n_3}$ , $\mathcal{Q}\in {ℝ}^{n_1\times n_2\times n_3}$ , we set ${\mathcal{A}}_l=\mathcal{U}{\left(\mathrm{<mo>\; :\; </mo>,1\; <mo>\; :\; </mo>}r\mathrm{,\; <mo>\; :\; </mo>}\right)}^{\text{T}}\in {ℝ}^{r\times n_1\times n_3}$ , ${\mathcal{B}}_l=\mathcal{V}{\left(:,1:r,:\right)}^{\text{T}}\in {ℝ}^{r\times n_2\times n_3}$ . Then fixing ${\mathcal{A}}_l$ and ${\mathcal{B}}_l$ , we can update ${\mathcal{L}}_{l+1}$ and ${\mathcal{E}}_{l+1}$ by solving the next convex optimization problem:

$\begin{array}{l}\underset{\mathcal{L},\mathcal{E}}{\min }\mathrm{<mo>\; :\; </mo>}{\Vert \mathcal{L}\Vert }_{\ast }-Tr\left({\mathcal{A}}_l{\ast }_L\mathcal{L}{\ast }_L{\mathcal{B}}_l^{\text{T}}\right)+\gamma \left({\Vert \mathcal{L}\Vert }_F^2-{\Vert {\mathcal{A}}_l{\ast }_L\mathcal{L}\Vert }_F^2\right)+\lambda {\Vert \mathcal{E}\Vert }_1\\ \text{s}\text{.t}\text{.}\mathcal{X}=\mathcal{L}+\mathcal{E}\end{array}$ (24)

In short, we implement these two steps and alternate between them until the iterative scheme meets the tolerance error. Algorithm 2 outlines the complete procedure for (22). Now the remaining key issue is how to solve the model (23), which will be discussed in the next subsection.

3.3. Optimization

In this section, an efficient iterative optimization scheme is created to optimize (23). According to the augmented Lagrangian multiplier method, the commonly used strategy is to approximately minimize the augmented Lagrangian function by adopting an alternating scheme, which we use to solve the model (23). To make the variables separable, we introduce the auxiliary variable $\mathcal{Z}$ , thus (23) is equivalent to the following form:

$\begin{array}{l}\underset{\mathcal{L},\mathcal{E}}{\min }\mathrm{<mo>\; :\; </mo>}{\Vert \mathcal{L}\Vert }_{\ast }-Tr\left({\mathcal{A}}_l{\ast }_L\mathcal{L}{\ast }_L{\mathcal{B}}_l^{\text{T}}\right)+\gamma \left({\Vert \mathcal{L}\Vert }_F^2-{\Vert {\mathcal{A}}_l{\ast }_L\mathcal{L}\Vert }_F^2\right)+\lambda {\Vert \mathcal{E}\Vert }_1\\ \text{s}\text{.t}\text{.}\mathcal{L}=\mathcal{Z}\mathcal{X}=\mathcal{L}+\mathcal{E}\end{array}$ (25)

The augmented Lagrange function of (24) can be written as:

$\begin{array}{l}L\left(\mathcal{L}\mathrm{,}\mathcal{Z}\mathrm{,}\mathcal{E}\mathrm{,}\mathcal{Y}\mathrm{,}\mathcal{W}\right)\\ ={\Vert \mathcal{L}\Vert }_{\ast }-Tr\left({\mathcal{A}}_l{\ast }_L\mathcal{Z}{\ast }_L{\mathcal{B}}_l^{\text{T}}\right)+\gamma \left({\Vert \mathcal{L}\Vert }_F^2-{\Vert {\mathcal{A}}_l{\ast }_L\mathcal{L}\Vert }_F^2\right)+\lambda {\Vert \mathcal{E}\Vert }_1\\ +\langle \mathcal{W}\mathrm{,}\mathcal{L}-\mathcal{Z}\rangle +\frac{\alpha }{2}{\Vert \mathcal{L}-\mathcal{Z}\Vert }_F^2+\langle \mathcal{Y}\mathrm{,}\mathcal{X}-\mathcal{L}-\mathcal{E}\rangle +\frac{\beta }{2}{\Vert \mathcal{X}-\mathcal{L}-\mathcal{E}\Vert }_F^2\end{array}$ (26)

where $\mathcal{Y}\mathrm{,}\mathcal{W}$ is the Lagrange multiplier matrix and $\alpha ,\beta >0$ is the penalty parameter. So, we can adopt the alternating iteration strategy, i.e., fix some variables and solve the remaining one.

Step 1: Keep ${\mathcal{L}}_k\mathrm{,}{\mathcal{Z}}_k\mathrm{,}\mathcal{E}\mathrm{,}{\mathcal{Y}}_k\mathrm{,}{\mathcal{W}}_k$ unchanged and update ${\mathcal{E}}_{k+1}$ through $L\left({\mathcal{L}}_k\mathrm{,}{\mathcal{Z}}_k\mathrm{,}\mathcal{E}\mathrm{,}{\mathcal{Y}}_k\mathrm{,}{\mathcal{W}}_k\right)$

$\begin{array}{c}{\mathcal{E}}_{k+1}=\underset{\epsilon }{\arg \min }L\left({\mathcal{L}}_k\mathrm{,}{\mathcal{Z}}_k\mathrm{,}\mathcal{E}\mathrm{,}{\mathcal{Y}}_k\mathrm{,}{\mathcal{W}}_k\right)\\ =\underset{\epsilon }{\arg \min }\lambda {\Vert \mathcal{E}\Vert }_1+\langle {\mathcal{Y}}_k\mathrm{,}{\mathcal{X}}_k-{\mathcal{L}}_k-\mathcal{E}\rangle +\frac{\beta }{2}{\Vert {\mathcal{X}}_k-{\mathcal{L}}_k-\mathcal{E}\Vert }_F^2\\ =\underset{\epsilon }{\arg \min }\lambda {\Vert \mathcal{E}\Vert }_1+\frac{\beta }{2}{\Vert \mathcal{E}-\left({\mathcal{X}}_k-{\mathcal{L}}_k+{\beta }^{-1}{\mathcal{Y}}_k\right)\Vert }_F^2\\ ={\mathcal{S}}_{\lambda \mathrm{,}{\beta }^{-1}}\left({\mathcal{X}}_k-{\mathcal{L}}_k+{\beta }^{-1}{\mathcal{Y}}_k\right)\end{array}$ (27)

Step 2: Keep $\mathcal{L}\mathrm{,}{\mathcal{Z}}_k\mathrm{,}{\mathcal{E}}_{k+1}\mathrm{,}{\mathcal{Y}}_k\mathrm{,}{\mathcal{W}}_k$ unchanged and update ${\mathcal{L}}_{k+1}$ through $L\left(\mathcal{L}\mathrm{,}{\mathcal{Z}}_k\mathrm{,}{\mathcal{E}}_{k+1}\mathrm{,}{\mathcal{Y}}_k\mathrm{,}{\mathcal{W}}_k\right)$

$\begin{array}{c}{\mathcal{L}}_{k+1}=\underset{\mathcal{L}}{\arg \min }L\left(\mathcal{L}\mathrm{,}{\mathcal{Z}}_k\mathrm{,}{\mathcal{E}}_{k+1}\mathrm{,}{\mathcal{Y}}_k\mathrm{,}{\mathcal{W}}_k\right)\\ =\underset{\mathcal{L}}{\arg \min }{\Vert \mathcal{L}\Vert }_{\ast }+\gamma \left({\Vert \mathcal{L}\Vert }_F^2-{\Vert {\mathcal{A}}_l{\ast }_L\mathcal{L}\Vert }_F^2\right)+\langle {\mathcal{W}}_k\mathrm{,}\mathcal{L}-{\mathcal{Z}}_k\rangle \\ +\frac{\alpha }{2}{\Vert \mathcal{L}-{\mathcal{Z}}_k\Vert }_F^2+\langle {\mathcal{Y}}_k\mathrm{,}{\mathcal{X}}_k-\mathcal{L}-{\mathcal{E}}_{k+1}\rangle +\frac{\beta }{2}{\Vert {\mathcal{X}}_k-\mathcal{L}-{\mathcal{E}}_{k+l}\Vert }_F^2\\ =\underset{\mathcal{L}}{\arg \min }{\Vert \mathcal{L}\Vert }_{\ast }+\gamma \left({\Vert \mathcal{L}\Vert }_F^2-{\Vert {\mathcal{A}}_l{\ast }_L\mathcal{L}\Vert }_F^2\right)+\frac{\alpha }{2}{\Vert \mathcal{L}-{\mathcal{Z}}_k+{\alpha }^{-1}{\mathcal{W}}_k\Vert }_F^2\\ +\frac{\beta }{2}{\Vert \mathcal{L}-{\mathcal{X}}_k+{\mathcal{E}}_{k+1}-{\beta }^{-1}{\mathcal{Y}}_k\Vert }_F^2\end{array}$ (28)

Obviously, Equation (27) is a quadratic function about $\mathcal{L}$ . Let

$\begin{array}{c}G\left(\mathcal{L}\right)=\gamma \left({\Vert \mathcal{L}\Vert }_F^2-{\Vert {\mathcal{A}}_l{\ast }_L\mathcal{L}\Vert }_F^2\right)+\frac{\alpha }{2}{\Vert \mathcal{L}-{\mathcal{Z}}_k+{\alpha }^{-1}{\mathcal{W}}_k\Vert }_F^2\\ +\frac{\beta }{2}{\Vert \mathcal{L}-{\mathcal{X}}_k+{\mathcal{E}}_{k+1}-{\beta }^{-1}{\mathcal{Y}}_k\Vert }_F^2\end{array}$

be a function with respect to $\mathcal{L}$ , then $G\left(\mathcal{L}\right)$ can be approximated by the linearization at ${\mathcal{L}}_k$ :

$\begin{array}{l}G\left(\mathcal{L}\right)=G\left({\mathcal{L}}_k\right)+\nabla G\left({\mathcal{L}}_k\right)\left(\mathcal{L}-{\mathcal{L}}_k\right)+\frac{\tau }{2}{\Vert \mathcal{L}-{\mathcal{L}}_k\Vert }_F^2\mathrm{.}\hfill \end{array}$

where $\tau$ is a parameter, and

$\begin{array}{c}\nabla G\left({\mathcal{L}}_k\right)=\left[\left(2\gamma +\alpha +\beta \right)\mathcal{I}-2\gamma {\mathcal{A}}_l{\ast }_L{\mathcal{A}}_l^{\text{T}}\right]{\ast }_L\mathcal{L}\\ +{\mathcal{W}}_k-{\mathcal{Y}}_k+\beta \left({\mathcal{E}}_{k+1}-{\mathcal{X}}_k\right)-\alpha {\mathcal{Z}}_k\end{array}$

denotes the gradient of the function $G(\cdot )$ at ${\mathcal{L}}_k$ . Thus, (27) with respect to $\mathcal{L}$ can be reformulated as:

${\mathcal{L}}_{k+1}=\underset{\mathcal{L}}{\arg \min }{\Vert \mathcal{L}\Vert }_{\ast }+\frac{\tau }{2}{\Vert \mathcal{L}-{\mathcal{L}}_k+{\tau }^{-1}\nabla G\left({\mathcal{L}}_k\right)\Vert }_F^2$ (29)

By Theorem 1 and Theorem 2, this could be solved as

${\mathcal{L}}_{k+1}={\mathcal{S}}_{{\tau }^{-1}}-\left({\mathcal{L}}_k-\frac{\nabla G\left({\mathcal{L}}_k\right)}{\tau }\right)$ (30)

Step 3: Keep ${\mathcal{L}}_{k+1}\mathrm{,}\mathcal{Z}\mathrm{,}{\mathcal{E}}_{k+1}\mathrm{,}{\mathcal{Y}}_k\mathrm{,}{\mathcal{W}}_k$ unchanged and update ${\mathcal{Z}}_{k+1}$ through $L\left({\mathcal{L}}_{k+1}\mathrm{,}\mathcal{Z}\mathrm{,}{\mathcal{E}}_{k+1}\mathrm{,}{\mathcal{Y}}_k\mathrm{,}{\mathcal{W}}_k\right)$

$\begin{array}{c}{\mathcal{Z}}_{k+1}=\underset{\mathcal{Z}}{\arg \min }L\left({\mathcal{L}}_{k+1}\mathrm{,}\mathcal{Z}\mathrm{,}{\mathcal{E}}_{k+1}\mathrm{,}{\mathcal{Y}}_k\mathrm{,}{\mathcal{W}}_k\right)\\ =\underset{\mathcal{Z}}{\arg \min }\langle {\mathcal{W}}_k\mathrm{,}{\mathcal{L}}_{k+1}-\mathcal{Z}\rangle +\frac{\alpha }{2}{\Vert {\mathcal{L}}_{k+1}-\mathcal{Z}\Vert }_F^2-Tr\left({\mathcal{A}}_l{\ast }_L\mathcal{Z}{\ast }_L{\mathcal{B}}^{\text{T}}\right)\end{array}$ (31)

Obviously, the objective function of (30) is a quadratic function. Through a simple derivation operation, we get

$-{\mathcal{A}}_l^{\text{T}}{\ast }_L{\mathcal{B}}_l-{\mathcal{W}}_k-\alpha {\mathcal{L}}_{k+1}+\alpha \mathcal{Z}=0$

This means that

${\mathcal{Z}}_{k+1}={\mathcal{L}}_{k+1}+{\alpha }^{-1}\left({\mathcal{A}}_l^{\text{T}}{\ast }_L{\mathcal{B}}_l+{\mathcal{W}}_k\right)$ (32)

Step 4: Update Lagrange multipliers ${\mathcal{Y}}_{k+1}$ , ${\mathcal{W}}_{k+1}$ :

$\begin{array}{l}{\mathcal{Y}}_{k+1}={\mathcal{Y}}_k+\beta \left({\mathcal{X}}_{k+1}-{\mathcal{L}}_{k+l}-{\mathcal{E}}_{k+1}\right)\\ {\mathcal{W}}_{k+1}={\mathcal{W}}_k+\alpha \left({\mathcal{L}}_{k+1}-{\mathcal{Z}}_{k+l}\right)\end{array}$ (33)

To sum up, algorithm 3 gives a complete program.

3.4. Adaptive Parameter

Previous studies have shown that the computational cost could increase significantly, since the algorithm may converge slowly when the fixed penalty parameter $\alpha$ and $\beta$ are chosen too small or large [28] [29], and we need to constantly try different values to pick a good value of $\alpha$ and $\beta$ . It is not easy to choose the optimal $\alpha$ and $\beta$ . Accordingly, a dynamical $\alpha$ and $\beta$ may be required to accelerate convergence in real applications. With the aid of the way in [31], the following adaptive update criterion is used:

${\alpha }_{k+1}=\min \left({\alpha }_{\max },{\rho }_1{\alpha }_k\right)$ (34)

${\beta }_{k+1}=\min \left({\beta }_{\max },{\rho }_2{\beta }_k\right)$ (35)

where ${\alpha }_{\max }$ and ${\beta }_{\max }$ is an upper bound of ${\alpha }_k$ and ${\beta }_k$ , and $\rho$ is defined as:

${\rho }_1=(\begin{array}{ll}{\rho }_0\mathrm{,}\hfill & \text{if}\frac{{\alpha }_k\max \left({\Vert {\mathcal{L}}^{k+1}-{\mathcal{L}}^k\Vert }_F\mathrm{,}{\Vert {\mathcal{Z}}^{k+1}-{\mathcal{Z}}^k\Vert }_F\right)}{{\Vert \mathcal{Y}\Vert }_F}<k\hfill \\ \mathrm{1,}\hfill & \text{otherwise}\hfill \end{array}$ (36)

${\rho }_2=(\begin{array}{ll}{\rho }_0\mathrm{,}\hfill & \text{if}\frac{{\beta }_k\max \left({\Vert {\mathcal{L}}^{k+1}-{\mathcal{L}}^k\Vert }_F\mathrm{,}{\Vert {\mathcal{Z}}^{k+1}-{\mathcal{Z}}^k\Vert }_F\right)}{{\Vert \mathcal{Y}\Vert }_F}<k\hfill \\ \mathrm{1,}\hfill & \text{otherwise}\hfill \end{array}$ (37)

where ${\rho }_1>1$ and ${\rho }_2>1$ are constant and $k>0$ is a threshold chosen in advance.

3.5. Convergence Analysis

This section discusses the convergence of the proposed algorithm.

Firstly, the optimal value of Equation (24) is expressed as follows

$\begin{array}{l}{p}^{\ast }=\inf \{{\Vert \mathcal{L}\Vert }_{\ast }-Tr\left({\mathcal{A}}_l{\ast }_L\mathcal{Z}{\ast }_L{\mathcal{B}}_l^{\text{T}}\right)+\gamma \left({\Vert \mathcal{L}\Vert }_F^2-{\Vert {\mathcal{A}}_l{\ast }_L\mathcal{L}\Vert }_F^2\right)\\ {}^{{}_{}{}^{}}+\lambda {\Vert \mathcal{E}\Vert }_1\mathrm{<mo>\; :\; </mo>}\mathcal{L}=\mathcal{Z}\mathcal{X}=\mathcal{L}+\mathcal{Z}\}\end{array}$ (38)

The augmented Lagrange function is written as

$\begin{array}{l}{L}_0\left(\mathcal{L}\mathrm{,}\mathcal{Z}\mathrm{,}\mathcal{E}\mathrm{,}\mathcal{Y}\mathrm{,}\mathcal{W}\right)\\ ={\Vert \mathcal{L}\Vert }_{\ast }-Tr\left({\mathcal{A}}_l{\ast }_L\mathcal{Z}{\ast }_L{\mathcal{B}}^{\text{T}}\right)+\gamma \left({\Vert \mathcal{L}\Vert }_F^2-{\Vert {\mathcal{A}}_l{\ast }_L\mathcal{L}\Vert }_F^2\right)+\lambda {\Vert \mathcal{E}\Vert }_1\\ +\langle \mathcal{W}\mathrm{,}\mathcal{L}-\mathcal{Z}\rangle +\langle \mathcal{Y}\mathrm{,}\mathcal{X}-\mathcal{L}-\mathcal{E}\rangle \end{array}$ (39)

In addition, in order to further analyze the convergence of the algorithm, the following three lemmas are established

Lemma 2 Let $\left({\mathcal{L}}^{\ast }\mathrm{,}{\mathcal{Z}}^{\ast }\mathrm{,}{\mathcal{E}}^{\ast }\mathrm{,}{\mathcal{X}}^{\ast }\mathrm{,}{\mathcal{Y}}^{\ast }\mathrm{,}{\mathcal{W}}^{\ast }\right)$ be the optimal solution of the augmented Lagrange function (38) and satisfy ${\mathcal{X}}^{\ast }={\mathcal{L}}^{\ast }+{\mathcal{E}}^{\ast }$ , then:

$p^{\ast }-p_{k+1}\le \langle {\mathcal{W}}^{\ast }\mathrm{,}{\mathcal{L}}_{k+1}-{\mathcal{Z}}_{k+1}\rangle +\langle {\mathcal{Y}}^{\ast }\mathrm{,}{\mathcal{X}}_{k+1}-{\mathcal{L}}_{k+1}-{\mathcal{E}}_{k+1}\rangle$ (40)

where $\left({\mathcal{L}}_{k+1}\mathrm{,}{\mathcal{Z}}_{k+1}\mathrm{,}{\mathcal{X}}_{k+1}\mathrm{,}{\mathcal{E}}_{k+1}\right)$ is the solution of the $k+1$ -th iteration in the algorithm 3, $p_{k+1}$ is the k-th iterative solution of (38). $p^{\ast }={\Vert {\mathcal{L}}_{k+1}\Vert }_{\ast }-Tr\left({\mathcal{A}}_l{\ast }_L{\mathcal{Z}}_{k+1}{\ast }_L{\mathcal{B}}_l^{\text{T}}\right)+\gamma \left({\Vert {\mathcal{L}}_{k+1}\Vert }_F^2-{\Vert {\mathcal{A}}_l{\ast }_L{\mathcal{L}}_{k+1}\Vert }_F^2\right)+\lambda {\Vert {\mathcal{E}}_{k+1}\Vert }_1$ .

Lemma 3 Let ${\mathcal{R}}_{k+1}={\mathcal{L}}_{k+1}-{\mathcal{Z}}_{k+1}$ , ${\mathcal{W}}_{k+1}={\mathcal{W}}_k+\alpha {\mathcal{R}}_{k+1}$ , ${\mathcal{Q}}_{k+1}={\mathcal{X}}_{k+1}-{\mathcal{L}}_{k+1}-{\mathcal{E}}_{k+1}$ , ${\mathcal{Y}}_{k+1}={\mathcal{Y}}_k+\beta {\mathcal{Q}}_{k+1}$ then the following inequality holds:

$\begin{array}{c}{p}_{k+1}-p^{\ast }\le \langle {\mathcal{W}}_{k+1}\mathrm{,}-{\mathcal{R}}_{k+1}\rangle +\langle {\mathcal{Y}}_{k+1}\mathrm{,}-{\mathcal{Q}}_{k+1}\rangle \\ -\alpha \langle {\mathcal{Z}}_k-{\mathcal{Z}}_{k+1}\mathrm{,}-{\mathcal{R}}_{k+1}+{\mathcal{Z}}^{\ast }-{\mathcal{Z}}_{k+1}\rangle \\ +\beta \langle {\mathcal{E}}_k-{\mathcal{E}}_{k+1}\mathrm{,}-{\mathcal{Q}}_{k+1}+{\mathcal{L}}^{\ast }-{\mathcal{X}}_{k+1}-{\mathcal{E}}_{k+1}\rangle \end{array}$ (41)

Lemma 4 Let $\left({\mathcal{L}}^{\ast }\mathrm{,}{\mathcal{Z}}^{\ast }\mathrm{,}{\mathcal{E}}^{\ast }\mathrm{,}{\mathcal{X}}^{\ast }\mathrm{,}{\mathcal{Y}}^{\ast }\mathrm{,}{\mathcal{W}}^{\ast }\right)$ be the optimal solution of the augmented Lagrange function (38) and ${\mathcal{R}}_{k+1}={\mathcal{L}}_{k+1}-{\mathcal{Z}}_{k+1}$ , ${\mathcal{Q}}_{k+1}={\mathcal{X}}_{k+1}-{\mathcal{L}}_{k+1}-{\mathcal{E}}_{k+1}$ , define:

$t_k=\frac{1}{\alpha }{\Vert {\mathcal{W}}_k-{\mathcal{W}}^{\ast }\Vert }_F^2+\alpha {\Vert {\mathcal{Z}}^{\ast }-{\mathcal{Z}}_{k+1}\Vert }_F^2+\frac{1}{\beta }{\Vert {\mathcal{Y}}_k-{\mathcal{Y}}^{\ast }\Vert }_F^2+\beta {\Vert {\mathcal{L}}^{\ast }-{\mathcal{L}}_{k+1}\Vert }_F^2$ (42)

Then $t_k$ is decreasing in each iteration and satisfies the following relationship:

$t_k-t_{k+1}\ge \alpha {\Vert {\mathcal{R}}_{k+1}-\left({\mathcal{Z}}_k-{\mathcal{Z}}_{k+1}\right)\Vert }_F^2+\beta {\Vert {\mathcal{Q}}_{k+1}-\left({\mathcal{E}}_k-{\mathcal{E}}_{k+1}\right)\Vert }_F^2$ (43)

According to the above results, the following convergence theorems are obtained:

Theorem 5 Based on the conditions in lemmas 2, 3 and 4, the iterative solution $p_k\to p^{\ast }$ , when $k\to \infty$ .

4. Experiments

In this section, we will conduct numerical experiments to confirm our main results. We studied the ability of T-HTN to recover various tube rank tensors from various sparse noises, and applied T-HTN to image denoising.

4.1. Synthetic Data Experiments

In this section, we compare the accuracy and speed of T-HTN and TNN based TRPCA [22] on synthetic datasets. Given tensor size $n_1\times n_2\times n_3$ and tubal rank $r\ll \min \left\{n_1,n_2\right\}$ , we first generate a tensor ${\mathcal{L}}_0\in {ℝ}^{n_1\times n_2\times n_3}$ by ${\mathcal{L}}_0=\mathcal{A}\ast \mathcal{B}$ ,where the elements of tensors $\mathcal{A}\in {ℝ}^{n_1\times r\times n_3}$ , $\mathcal{B}\in {ℝ}^{r\times n_2\times n_3}$ are sampling from independent identically distributed (i.e.) standard Gaussian distribution. Then, we from ${\mathcal{L}}^{\ast }$ by ${\mathcal{L}}^{\ast }=\sqrt{n_1{n}_2{n}_3}{\mathcal{L}}_0/{\Vert {\mathcal{L}}_0\Vert }_F$ . Next, the support of ${\mathcal{E}}^{\ast }$ is uniformly sampled at random. For any $\left(i\mathrm{,}j\mathrm{,}k\right)\in supp\left({\mathcal{E}}^{\ast }\right)$ , we get ${\mathcal{E}}_{ijk}^{\ast }={\mathcal{B}}_{ijk}$ , where $\mathcal{B}$ is a tensor with independent Bernoulli ±1 entries. Thus, we get the observation tensor $\mathcal{M}={\mathcal{L}}^{\ast }+{\mathcal{E}}^{\ast }$ . In the experiment part, we set the parameters

$\lambda =1/\sqrt{n_3\max \left\{n_1\mathrm{,}{n}_2\right\}}$ . We use the relative square error (RSE) to evaluate the estimated ${\mathcal{L}}^{\ast }$ of the underlying tensor $\hat{\mathcal{L}}$ , that is $RSE\left(\hat{\mathcal{L}}\mathrm{,}{\mathcal{L}}^{\ast }\right)\mathrm{<mo>\; :\; </mo>}=\frac{{\Vert \hat{\mathcal{L}}-{\mathcal{L}}^{\ast }\Vert }_F}{{\Vert {\mathcal{L}}^{\ast }\Vert }_F}$ .

4.1.1. Effectiveness and Efficiency of T-HTN

Firstly, we prove that T-HTN can accurately recover the underlying tensor ${\mathcal{L}}^{\ast }$ . Based on experience, we test the recovery performance of tensors of different sizes by setting $n=n_1=n_2\in \left\{150,300,350\right\}$ and $n_3=3$ , with

$\left(r_t\left({\mathcal{L}}^{\ast }\right)\mathrm{,}{\Vert {\mathcal{E}}^{\ast }\Vert }_0\right)=\left(0.1n\mathrm{,0.1}{n}^2{n}_3\right)$ . Then a more difficult setting

$\left(r_t\left({\mathcal{L}}^{\ast }\right)\mathrm{,}{\Vert {\mathcal{E}}^{\ast }\Vert }_0\right)=\left(0.1n\mathrm{,0.3}{n}^2{n}_3\right)$ is tested. The results are shown in Table 1. and

Table 2. It is not difficult to see that T-HTN and TRPCA have the same good recovery performance, because both can accurately recover the underlying tensor, but T-HTN has obvious advantages in time.

To test the influence of the distribution of outliers on T-HTN performance, we obtain the outlier tensor element ${\mathcal{E}}^{\ast }$ from i.i.d Gaussian distribution $\mathcal{N}\left(\mathrm{0,1}\right)$ , or uniform distribution $\mathcal{U}\left[\mathrm{0,1}\right]$ . The corresponding results are given in Table 3 and Table 4. The performance of T-HTN and TRPCA is not significantly affected by the outlier’s distribution. This phenomenon can be explained by Theorem 4.1 in [22], that is when the outlier tensor ${\mathcal{E}}^{\ast }$ is uniformly distributed, TRPCA can accurately restore the underlying tensor ${\mathcal{L}}^{\ast }$ under some mild conditions. In [22], only one hypothesis is made for the random location distribution, but no hypothesis is made for the size or symbol of non-zero terms. Because the T-HTN proposed in this paper can well simulate TRPCA with low tube rank tensors, T-HTN is also robust to outlier.

Table 1. Comparison with TRPCA [22] in both accuracy and speed for different tensor sizes when $\left(r_t\left({\mathcal{L}}^{\ast }\right)\mathrm{,}{\Vert {\mathcal{E}}^{\ast }\Vert }_0\right)=\left(0.1n\mathrm{,0.1}{n}^2{n}_3\right)$ .

Table 2. Comparison with TRPCA [22] in both accuracy and speed for different tensor sizes when $\left(r_t\left({\mathcal{L}}^{\ast }\right)\mathrm{,}{\Vert {\mathcal{E}}^{\ast }\Vert }_0\right)=\left(0.1n\mathrm{,0.3}{n}^2{n}_3\right)$ .

Table 3. Comparison with TRPCA [22] in both accuracy and speed for different tensor sizes when the outlier tensor element ${\mathcal{E}}^{\ast }$ from i.i.d Gaussian distribution $\mathcal{N}\left(\mathrm{0,1}\right)$ .

Table 4. Comparison with TRPCA [22] in both accuracy and speed for different tensor sizes when the outlier tensor element ${\mathcal{E}}^{\ast }$ from i.i.d Gaussian distribution $\mathcal{U}\left(\mathrm{0,1}\right)$ .

In order to further verify the efficiency of the proposed T-HTN, we consider a special case: fixing the tubal rank of the underlying tensor ${\mathcal{L}}^{\ast }$ and changing the size of the underlying tensor ${\mathcal{L}}^{\ast }$ . Explicitly, we fix $r_t\left({\mathcal{L}}^{\ast }\right)=10$ , and vary $n\in \left\{\mathrm{100,150,300,400,500}\right\}$ with $n_3=3$ . We tested each data 10 times and calculated the average time. Figure 1 shows the relationship between average time and tensor size. Obviously, both can accurately recover the underlying tensor, but in terms of running time, TRPCA expands super-linearly and T-HTN expands approximately linear scaling.

4.1.2. Effects of the Number of Truncated Singular Values

The performance of T-HTN largely depends on the number of truncated elements of ${\mathcal{L}}^{\ast }$ in (23), that is, the number of singular values to be retained. Here, we discuss the influence of different truncation degrees of Frobenius norm and nuclear norm on the accuracy and speed of T-HTN. Specifically, we consider the tensor with the size of $300\times 300\times 3$ and set up four different truncation methods $r^{\ast }=r_t\left({\mathcal{L}}^{\ast }\right)$ and sparsity $s^{\ast }={\Vert {\mathcal{E}}^{\ast }\Vert }_0$ as $\left(r^{\ast }\mathrm{,}{s}^{\ast }\right)\in \left\{\left(\mathrm{10,4.05}e4\right)\mathrm{,}\left(\mathrm{10,8.1}e4\right)\mathrm{,}\left(\mathrm{15,4.05}e4\right)\mathrm{,}\left(\mathrm{15,8.1}e4\right)\right\}$ , where the elements outliers follow i.i.d. $\mathcal{N}\left(\mathrm{0,1}\right)$ . By varying the initialized $r\in \left\{\mathrm{5,10,15,}\cdots \mathrm{,50}\right\}$ . Firstly, we give the effect of the number of truncated singular values on the recovery performance of the underlying tensor ${\mathcal{L}}^{\ast }$ .The results are shown in Figure 2. There is a phrase transition point $r_{pt}$ . Once the reserved singular valuer is greater than it, the RSE of $\hat{\mathcal{L}}$ will decrease rapidly. Then, we give the influence of the number of truncated singular values on the estimation performance of outlier tensor ${\mathcal{E}}^{\ast }$ . Figure 3 shows the RSE and $l_0$ -norm of $\hat{\mathcal{E}}$ finally solved. Finally, we show the effect of the number of truncated singular values on the running time of T-HTN in Figure 4. Obviously, the more singular values remain, the longer the running time, and the more complex the underling tensor becomes, which is also consistent with our intuition.

4.2. Real Data Experiments

In this section, we evaluate the efficiency of T-HTN proposed in this paper on real data sets and compare it with TRPCA. Specifically, we do tensor restoration experiments on color image data. The purpose is to restore the original image from its corrupted observation. For the estimation $\hat{\mathcal{L}}$ of the underlying tensor ${\mathcal{L}}^{\ast }$ , we choose the relative square error(RSE), the peak signal-to-noise ratio (PSNR), and the structured similarity index(SSIM) as the evaluation index, which is respectively defined as,

Figure 1. Computation time of TRPCA and proposed T-HTN.

Figure 2. Effects of initialized tubal rank r on the recovery performance of the underlying tensor L.

Figure 3. Effects of initialized tubal rank r on the recovery performance of the underlying tensor E.

Figure 4. Effects of initialized tubal rank r on the running time of T-HTN.

$\text{PSNR}=10{\log }_{10}\left(\frac{n_1{n}_2{n}_3{\Vert {\mathcal{L}}^{\ast }\Vert }_{\infty }^2}{{\Vert \hat{\mathcal{L}}-{\mathcal{L}}^{\ast }\Vert }_F^2}\right),$

and

$\text{SSIM}=\frac{\left(2{\mu }_{{\mathcal{L}}^{\ast }}{\mu }_{\hat{\mathcal{L}}}+c_1\right)\left({\sigma }_{\mathcal{L}{\hat{\mathcal{L}}}^{\ast }}+c_2\right)}{\left({\mu }_{{\mathcal{L}}^{\ast }}^2+{\mu }_{\hat{\mathcal{L}}}^2+c_1\right)\left(\sigma +\sigma +c_2\right)}\mathrm{.}$

where ${\mu }_{{\mathcal{L}}^{\ast }}$ and ${\mu }_{\hat{\mathcal{L}}}$ are the average values of original tensor and recovered tensor represents the covariance of ${\mathcal{L}}^{\ast }$ and $\hat{\mathcal{L}}$ , ${\sigma }_{{\mathcal{L}}^{\ast }}$ and ${\sigma }_{\hat{\mathcal{L}}}$ respectively denotes the standard deviation of ${\mathcal{L}}^{\ast }$ and $\hat{\mathcal{L}}$ . Natural scenes images follow natural statistics [32]. As shown by Hu et al. [33], information of image scenes is dominated by the top 20 singular values, which is low-rank. In Figure 5, our experimental data are from 10 common color images. The size of the selected images is $300\times 300\times 3$ . When these color images are converted into matrices, they can be regarded as low rank structures. The same is true for tensor data.

Table 5. PSNR values of different truncated singular values.

Figure 5. Tested color images.

Number of Optimal Truncated Singular Values

First, we apply our algorithm to a picture data. We need to preset the number of truncated singular values. Therefore, we designed an experiment in this part, set the number of reserved singular values to $r_0\in \left\{\mathrm{2,4,}\cdots \mathrm{,18,20}\right\}$ , test all possible values, and select the best value. We test 10 images and selected the number of optimal truncated singular values. The detailed results are shown in Table 5. In the worst case of our approach, it is sufficient to test $r_0$ from 1 to 20. Even if the best $r_0$ is not selected, its effectiveness will not be lost.

4.3. Conclusions

This paper introduces a new regularization term T-TFN, integrates T-TFN and T-TNN, and proposes a new model T-HTN for TRPCA. Because of the emergence of T-TFN, this new T-HTN regularization method can improve the effectiveness and stability of the model. Then, an effective iterative framework is designed to solve the new optimization model. In addition, its convergence is also derived in the mathematical field. The experimental results on synthetic data, real visual images and recommendation systems, especially the use of statistical analysis methods, illustrate the advantages of HTN over other methods. In other words, HTN method is more effective and stable.

There is still room for further research in this field, for example, how to prove the stability of the proposed method mathematically, and how to select the proportion of missing elements to ensure some theoretical analysis of effective performance.

This work is supported by Innovative talents support plan of colleges and universities in Liaoning Province (2021).

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	Lu, C., Feng, J., Chen, Y., et al. (2017) Tensor Robust Principal Component Analysis: Exact Recovery of Corrupted Low-Rank Tensors via Convex Optimization. 2016 IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2016, Las Vegas, 27-30 June 2016, 5249-5257. https://doi.org/10.1109/CVPR.2016.567
[2]	De Lathauwer, L. and Vandewalle, J. (2004) Dimensionality Reduction in Higher-Order Signal Processing and Rank-(R1, R2, …, RN) Reduction in Multilinear Algebra. Linear Algebra and Its Applications, 391, 31-55. https://doi.org/10.1016/j.laa.2004.01.016
[3]	Vasilescu, M. and Terzopoulos, D. (2003) Multilinear Subspace Analysis of Image Ensembles. IEEE Computer Society Conference on Computer Vision and Pattern Recognition, Madison, 18-20 June 2003, II-93.
[4]	Cyganek, B. (2015) Visual Pattern Recognition Framework Based on the Best Rank Tensor Decomposition. In: Tavares, J.M.R.S. and Jorge, R.N., Eds., Developments in Medical Image Processing and Computational Vision, Springer International Publishing, Berlin, 89-103.
[5]	Kolda, T.G. and Ba Der, B.W. (2009) Tensor Decompositions and Applications. SIAM Review, 51, 455-500. https://doi.org/10.1137/07070111X
[6]	Candès, E.J., Li, X.D., et al. (2009) Robust Principal Component Analysis? Journal of the ACM, 58, 1-37.
[7]	Wright, J., Ganesh, A., Rao, S., et al. (2009) Robust Principal Component Analysis: Exact Recovery of Corrupted Low-Rank Matrices via Convex Optimization. 23rd Annual Conference on Neural Information Processing Systems 2009, Vancouver, 7-10 December 2009.
[8]	Bao, B.K., Liu, G., Xu, C., et al. (2012) Inductive Robust Principal Component Analysis. IEEE Transactions on Image Processing, 21, 3794-3800. https://doi.org/10.1109/TIP.2012.2192742
[9]	Javed, S., Mahmood, A., Bouwmans, T., et al. (2017) Motion-Aware Graph Regularized RPCA for Background Modeling of Complex Scenes. 2016 IEEE 23rd International Conference on Pattern Recognition (ICPR), Cancun, 4-8 December 2016, 120-125. https://doi.org/10.1109/ICPR.2016.7899619
[10]	Liu, G., Lin, Z., Yan, S., et al. (2010) Robust Recovery of Subspace Structures by Low-Rank Representation. IEEE Transactions on Pattern Analysis and Machine Intelligence, 35, 171-184.
[11]	Golbabaee, M. and Vandergheynst, P. (2012) Compressed Sensing of Simultaneous Low-Rank and Joint-Sparse Matrices. https://doi.org/10.1109/ICASSP.2012.6288484
[12]	Hillar, C.J. and Lim, L.H. (2009) Most Tensor Problems Are NP-Hard. Journal of the ACM, 60, Article No. 45. https://doi.org/10.1145/2512329
[13]	Gandy, S., Recht, B. and Yamada, I. (2011) Tensor Completion and Lown-Rank Tensor Recovery via Convex Optimization. Inverse Problems, 27, Article ID: 025010. https://doi.org/10.1088/0266-5611/27/2/025010
[14]	Tucker, L. (1966) Some Mathematical Notes on Three-Mode Factor Analysis. Psychometrika, 31, 279-311. https://doi.org/10.1007/BF02289464
[15]	Kilmer, M.E., Braman, K., Hao, N., et al. (2013) Third-Order Tensors as Operators on Matrices: A Theoretical and Computational Framework with Applications in Imaging. SIAM Journal on Matrix Analysis and Applications, 34, 148-172. https://doi.org/10.1137/110837711
[16]	Bo, H., Mu, C., Goldfarb, D., et al. (2015) Provable Models for Robust Low-Rank Tensor Completion. Pacific Journal of Optimization, 11, 339-364.
[17]	Anandkumar, A., Jain, P., Shi, Y., et al. (2015) Tensor vs Matrix Methods: Robust Tensor Decomposition under Block Sparse Perturbations.
[18]	Kilmer, M.E., et al. (2011) Factorization Strategies for Third-Order Tensors. Linear Algebra and Its Applications, 435, 641-658. https://doi.org/10.1016/j.laa.2010.09.020
[19]	Wang, A., Zhong, J. and Li, X. (2018) Coherent Low-Tubal-Rank Tensor Completion. 2017 4th IAPR Asian Conference on Pattern Recognition (ACPR), Nanjing, 26-29 November 2017, 518-523. https://doi.org/10.1109/ACPR.2017.66
[20]	Lu, C., Feng, J., Chen, Y., et al. (2020) Tensor Robust Principal Component Analysis with a New Tensor Nuclear Norm. IEEE Transactions on Pattern Analysis and Machine Intelligence, 42, 925-938. https://doi.org/10.1109/TPAMI.2019.2891760
[21]	Li, T. and Ma, J. (2019) Non-Convex Penalty for Tensor Completion and Robust PCA.
[22]	Lu, C., Feng, J., Chen, Y., et al. (2020) Tensor Robust Principal Component Analysis with a New Tensor Nuclear Norm. IEEE Transactions on Pattern Analysis and Machine Intelligence, 42, 925-938. https://doi.org/10.1109/TPAMI.2019.2891760
[23]	Jiang, T.X., Huang, T.Z., Zhao, X.L., et al. (2017) Multi-Dimensional Imaging Data Recovery via Minimizing the Partial Sum of Tubal Nuclear Norm. Journal of Computational and Applied Mathematics, 372, Article ID: 112680.
[24]	Ye, H., Li, H., et al. (2019) A Hybrid Truncated Norm Regularization Method for Matrix Completion. IEEE Transactions on Image Processing, 28, 5171-5186.
[25]	Kilmer, M.E., Martin, C.D. and Perrone, L. (2008) A Third-Order Generalization of the Matrix SVD as a Product of Third-Order Tensors.
[26]	Lu, C., Peng, X. and Wei, Y. (2019) Low-Rank Tensor Completion with a New Tensor Nuclear Norm Induced by Invertible Linear Transforms. 2019 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), Long Beach, 15-20 June 2019, 5989-5997. https://doi.org/10.1109/CVPR.2019.00615
[27]	Lu, C., Feng, J., Lin, Z. and Yan, S. (2018) Exact Low Tubal Rank Tensor Recovery from Gaussian Measurements. Proceedings of the 27th International Joint Conference on Artificial Intelligence, Stockholm, 13-19 July 2018, 2504-2510. https://doi.org/10.24963/ijcai.2018/347
[28]	He, B.S., Yang, H. and Wang, S.L. (2000) Alternating Direction Method with Self-Adaptive Penalty Parameters for Monotone Variational Inequalities. Journal of Optimization Theory and Applications, 106, 337-356. https://doi.org/10.1023/A:1004603514434
[29]	Yang, J. and Yuan, X. (2012) Linearized Augmented Lagrangian and Alternating Direction Methods for Nuclear Norm Minimization. Mathematics of Computation, 82, 301-329. https://doi.org/10.1090/S0025-5718-2012-02598-1
[30]	Xue, S.K., Qiu, W.Y., Liu, F., et al. (2017) Low-Rank Tensor Completion by Truncated Nuclear Norm Regularization. 2018 24th International Conference on Pattern Recognition (ICPR), Beijing, 20-24 August 2018, 2600-2605. https://doi.org/10.1109/ICPR.2018.8546008
[31]	Lin, Z., Liu, R. and Li, H. (2015) Linearized Alternating Direction Method with Parallel Splitting and Adaptive Penalty for Separable Convex Programs in Machine Learning. JMLR: Workshop and Conference Proceedings, Vol. 29, 116-132. https://doi.org/10.1007/s10994-014-5469-5
[32]	Fan, H., Kuang, G. and Qiao, L. (2017) Fast Tensor Principal Component Analysis via Proximal Alternating Direction Method with Vectorized Technique. Applied Mathematics, 8, 77-86. https://doi.org/10.4236/am.2017.81007
[33]	Hu, Y., et al. (2013) Fast and Accurate Matrix Completion via Truncated Nuclear Norm Regularization. IEEE Transactions on Pattern Analysis and Machine Intelligence, 35, 2117-2130. https://doi.org/10.1109/TPAMI.2012.271