Over the past decade, there has been a significant rise in the volume of data, accompanied by a notable shift towards multidimensional data, as opposed to traditional data confined to one or two dimensions. This trend presents various challenges regarding storage, transmission, and analysis. Tensors [7,23], representing multidimensional arrays, have emerged as crucial tools in numerous applications such as computer vision [3,28,49], signal processing [31,40], seismic imaging [9,35], statistics [15,24,57], and machine learning [1,6,18]. Exploring low-dimensional structures within such complex data has gained increasing importance, particularly when these structures can be effectively modeled by certain low-rank properties.
Unlike matrices designed to handle two-dimensional (2D) data, the concept of tensor rank is not universally defined and can vary depending on the chosen tensor decomposition methods. The CANDECOMP/PARAFAC (CP) rank [23] originates from the CP decomposition [20], determining the minimum number of rank-one decompositions to represent a given tensor. On the other hand, the Tucker rank [12], derived from the Tucker decomposition [42], is a vector wherein each element represents the rank of a matrix unfolded from the original tensor. Additionally, the tensor multi-rank [12] and tubal rank [21] have emerged from tensor singular value decomposition (t-SVD) [22], analogous to the singular value decomposition (SVD) of matrices. Consequently, various surrogates of tensor rank have been proposed. For instance, Liu et al. [27] introduced the sum of the nuclear norm (SNN) based on the Tucker decomposition. The concept of a matrix nuclear norm was extended to the tensor nuclear norm (TNN) for the t-SVD in [39]. Moreover, several nonconvex alternatives to TNN have been proposed [53,54,58]. Jiang et al. [19] introduced the partial sum of the tubal nuclear norm (PSTNN), which calculates the partial sum of smaller singular values for every frontal slice after applying a discrete Fourier transformation (DFT). Xu et al. [50] incorporated the Laplace function into TNN, leading to a Laplace-based nonconvex surrogate. Qiu et al. [37] proposed a nonconvex alternating projection method with linear convergence, followed by an acceleration leveraging the properties of the tangent space of low-rank tensors. Recently, Yan and Guo [51] considered using the ℓ p quasi-norm (0 < p < 1) to impose sparse constraints on both the singular values and sparse components simultaneously, which is referred to as the p-TRPCA model.
A conventional yet valuable tool in data analysis is principal component analysis (PCA) [48], utilized for extracting dominant patterns from matrices. However, a well-known drawback of PCA is its susceptibility to sparse errors and outlier observations. To address this limitation, robust PCA (RPCA) [4] was introduced as the first polynomial-time algorithm with robust recovery guarantees. Subsequently, tensor robust principal component analysis (TRPCA) [29] extended RPCA from matrices to tensors, allowing for the identification of low-rank tensors from sparsely corrupted entries. Specifically, TRPCA aims to decompose an observed tensor X ∈ R n 1 ×n 2 ×n 3 into X = L 0 + E 0 , where L 0 represents a low-rank tensor and E 0 is a tensor containing only a small number of nonzero elements. Mathematically, TRPCA can be formulated as the following optimization problem:
where λ > 0 is a fixed parameter, • 0 denotes the number of nonzero elements, and rank(L) represents some type of tensor rank. However, both the rank and the ℓ 0 minimization problems are NP-hard [33]. Alternatively, convex or non-convex surrogate functions [16,52] to approximate the rank and ℓ 0 penalties are used in TRPCA.
The ℓ 1 norm serves as a convex relaxation of the ℓ 0 norm and has found widespread application in statistics, as highlighted in [41] with the introduction of the least absolute shrinkage and selection operator (LASSO). However, Fan and Li [10] noted that the ℓ 1 norm may not always be statistically optimal to yield the best estimation performance. Consequently, various nonconvex penalties [14,55] have been proposed, including the bridge penalty by Huang et al. [17], the logistic penalty by Nikolova et al. [34], the hard thresholding penalty function by Fan and Li [10], the minimax concave penalty by Zhang [56]. In the context of tensor recovery problems, two convex relaxation methods are the ℓ 1 norm [13,30,36] and the • 2,1 functional [60]. Nonconvex penalties include the ℓ p regularization [26] for low-rank tensor recovery problems.
All the aforementioned nonconvex surrogates of tensor rank come with internal parameters that significantly influence the model's performance. Motivated by the remarkable performance of the ratio of the ℓ 1 -norm and the ℓ 2 -norm for sparse signal recovery [38,[43][44][45], we propose a parameter-free regularization technique utilizing the ratio of the tensor nuclear norm and the Frobenius norm (TNF) to approximate the tensor tubal rank. Specifically, in the TRPCA problem (1), we utilize the TNF regularization to enforce the low rankness while using the ℓ 1 -norm for sparsity. For brevity, we refer to the combination of TNF and ℓ 1 as simply TNF. Following a set of incoherence conditions formulated in the TNN-based TRPCA model [30], we prove that a pair of tensors serves as a local minimizer of the proposed TNF-based TRPCA model if one tensor is sufficiently low in rank and the other tensor is sufficiently sparse. In addition, we propose replacing the ℓ 1 norm with the ratio of the ℓ 1 and Frobenius norm for tensors, the latter denoted as the ℓ F norm. We refer to the combination of TNF and ℓ 1 /ℓ F as the TNF+ model in short.
Computationally, we devise efficient algorithms based on the alternating direction method of multipliers (ADMM) [2] to solve for both TNF and TNF+ models. We also establish their subsequential convergence under certain conditions. Extensive experiments conducted on synthetic and real image data confirm the superiority of our proposed methods over state-ofthe-art approaches. The key contributions of our work are summarized as follows:
• We propose two novel models (TNF and TNF+) for TRPCA.
• We present an exact recovery theory of TNF under incoherence conditions.
• We adopt ADMM to solve the proposed models along with convergence analysis.
We organize the rest of the paper as follows. We introduce our proposed model TNF and its properties in Sect. 2. The algorithm development with convergence analysis is presented in Algorithm 3. A variant model, called TNF+, along with an algorithm and its convergence is discussed in Sect. 4. We conduct numerical experiments in Sect. 5, including synthetic and real data to show the superiority of our proposed models. Finally, we conclude the paper in Sect. 6.
In this section, we introduce basic tensor notations and discuss a non-convex regularization method, which involves the ratio of the tensor nuclear norm to the Frobenius norm (TNF), aimed at approximating the tensor tubal rank [59]. We adapt the TNF regularization to the TRPCA problem and establish a recovery guarantee of using TNF and ℓ 1 to identify a lowrank tensor and a sparse tensor, respectively.
We provide an overview of necessary notations and definitions used throughout this paper, as summarized in Table 1. The field of real numbers and complex numbers are denoted as R and C, respectively. Considering a tensor A ∈ R n 1 ×n 2 ×n 3 , we denote A as the tensor after applying the fast Fourier Transform (FFT) to the tensor A along the third (tubal) dimension, i.e., A = fft (A, [ ], 3) via the MATLAB command "fft". We compute A via A = ifft A, [ ], 3 . Following the work [30], we define the tensor Frobenius norm and the tensor nuclear norm (TNN) as follows,
where A (i) is the i-th frontal slice of A, σ i j is the j-th singular value of A (i) , and
Our models and algorithms are built on the t-SVD algebraic framework [22]. Please refer to Definition 1 for t-SVD and other related concepts in Appendix A.
Definition 1 (tensor singular value decomposition: t-SVD [22]) Let A ∈ R n 1 ×n 2 ×n 3 , then the t-SVD of A is given by
where U ∈ R n 1 ×n 1 ×n 3 , V ∈ R n 2 ×n 2 ×n 3 are orthogonal tensors, and S ∈ R n 1 ×n 2 ×n 3 is an fdiagonal tensor.
Analogous to skinny matrix SVD, the skinny t-SVD requires the tensor tubal rank, which is defined in Definition 2.
Definition 2 (tensor tubal rank [30]) For a tensor A ∈ R n 1 ×n 2 ×n 3 , its tubal rank, denoted as rank t (A) defined as the number of nonzero singular tubes of S, where S comes from the t-SVD of A, i.e. A = U * S * V * .
For tensor A ∈ R n 1 ×n 2 ×n 3 with tubal rank r < n (2) , the skinny t-SVD of A is defined by
Zheng et al. [59] proposed the ratio of the tensor nuclear norm and the Frobenius norm (TNF) as a nonconvex surrogate of tensor tubal rank for the tensor completion problem. The TNF regularization is defined as
TNF effectively enforces a low-rank structure of the tensor, analogous to the ℓ 1 /ℓ 2 model [38,45] applied to the vector formed by stacking all singular values {σ i j }.
the matrix trace
the inner product between A and
This paper focuses on the TRPCA problem, which aims to decompose a given tensor into the sum of a low-rank tensor and a sparse tensor. We employ the TNF regularization for low rankness and the standard ℓ 1 norm for sparsity. In short, the proposed model is formulated as min
where X ∈ R n 1 ×n 2 ×n 3 is a given third-order tensor. Throughout the remainder of the paper, we refer to this TNF-based TRPCA model ( 6) briefly as "TNF".
We establish a recovery theory for the proposed model ( 6) to identify the two tensors (a low-rank tensor and a sparse tensor) under tensor incoherence conditions. Some notations are required to present the conditions in Definition 3 and Theorem 1. The column basis is denoted as -→ e i , which is a tensor of size n 1 ×1 × n 3 with its (i, 1, 1)-th entry set to 1 and the remaining entries set to 0. The nonzero entry one only appears at the first frontal slice of -→ e i . Naturally its conjugate transpose -→ e * i is called row basis. The tube basis, denoted as ėk , is a tensor of size 1 × 1 × n 3 with its (1, 1, k)-th entry set to 1 and the reset set to 0. We define e i jk := -→ e i * ėk * -→ e * j ∈ R n 1 ×n 2 ×n 3 , which is a unit tensor with the only non-zero entry at (i, j, k) being to 1. [30]) For a low-rank tensor L 0 ∈ R n 1 ×n 2 ×n 3 , we assume rank t (L 0 ) = r and its skinny t-SVD is
where -→ e i and -→ e j are column basis of size n 1 × 1 × n 3 and n 2 × 1 × n 3 , respectively. We present our main theoretical result regarding the recovery guarantee of the TNF regularization and the ℓ 1 norm for finding a low-rank tensor and a sparse tensor, respectively.
Theorem 1 Suppose L 0 ∈ R n 1 ×n 2 ×n 3 with tubal rank r obeys the tensor incoherence conditions (7) with parameter μ. Suppose that the support of E 0 is uniformly distributed among all sets of cardinality m = 2γ n 1 n 2 n 3 , where γ = P(sgn(E 0 ) = 1) = P(sgn(E 0 ) = -1). If the parameter λ in the TNF model ( 6) is selected within the interval
with sufficiently large n 1 , n 2 , n 3 , there exists a positive constant c 0 such that with probability at least
Theorem 1 implies that for L 0 with sufficiently low rank (its tubal rank is upper bounded) and E 0 with sufficiently sparse (its cardinality is upper bounded), the pair (L 0 , E 0 ) is a local minimum of the proposed TNF model (6) with high probability under some certain conditions. In addition, sufficiently large n 1 , n 2 , n 3 can ensure that 24 1-2γ / L 0 F < n 1 n 2 n 2 3 , and 1 4
2μr > √ rn 3 such that the interval for λ is well-defined. Its proof is given in the supplementary material.
In this section, we employ the alternating direction method of multipliers (ADMM) to solve the proposed model ( 6), accompanied by analyses of its complexity and convergence.
We introduce an auxiliary variable H and design a specific splitting scheme that reformulates (6)
The corresponding augmented Lagrangian function is expressed as
where Y, Z are dual variables and μ 1 , μ 2 are positive parameters. In the ADMM scheme, we alternatively update the variables L, H, E, Y, and Z by
The L-subproblem in (11) can be rewritten as
which has a closed-form solution by the tensor singular value thresholding (t-SVT) [30]. Specifically given a tensor A with its t-SVD A = U * S * V * , the t-SVT operator is defined by
where τ > 0 and S τ is an tensor that satisfies S τ = max{S -τ, 0}. Hence, we have the L-update as follows,
The H-subproblem of (11) can be expressed as
where a scalar ρ (k+1) = L (k+1) * and a tensor
Following the work of [38], we derive the closed-form solution to the problem (14) given by
where G (k) is a random tensor with its Frobenius norm being 3 ρ (k+1) μ 1
and
and
Lastly, the tensor E-subproblem of ( 11) can be equivalently expressed as minimizing the ℓ 1 minimization elementwise, thus allowing for a closed-form solution through a softthresholding operator, i.e.,
where shrink(v, ρ) = sign(v) max{|v| -ρ, 0}.
We present the overall algorithm for solving problem (6) in Algorithm 1. Its primary computational complexity arises from updating L and H. Specifically, in each iteration, updating L incurs a computational cost of O((n
). Consequently, the overall computational complexity of Algorithm 1 is
This section is devoted to the convergence analysis of our algorithm. Specifically, We show that the sequence generated by Algorithm 1 has a subsequence convergent to a stationary point of with the TNF model ( 6) under the following two assumptions. A1: The sequence {L (k) } generated by (11) is bounded, so is its nuclear norm of
A2: The Frobenius norm of {H (k) } has a uniform lower bound, i.e., there exists a positive constant δ such that H (k) F ≥ δ, ∀k. Lemma 1 Under assumptions A1-A2 with sufficiently large parameters μ 1 , μ 2 , the sequence {Y (k) } generated by (11) satisfies
Algorithm 1 ADMM for solving the TNF model (6).
Require: Observed data X , parameters: μ 1 , μ 2 , kMax, 1: Initialization: (L (0) , E (0) ) by a TNN-based TRPCA model, H (0) = L (0) , Y (0) = Z (0) = O, and k = 0 2: while k < kMax or not converged do 3:
where M and δ are the constants defined in A1 and A2, respectively.
Lemma 2 Under assumptions A1-A2, the augmented Lagrangian function (10) of the sequence {L (k) ,
with four positive constants c 1 , c 2 , c 3 , c 4 .
be the sequence generated by (11), then there exist a tensor
and a constant κ > 0 such that
Theorem 2 Under assumptions A1-A2, the sequence
generated by (11) satisfies (i) The sequences {H (k) }, {E (k) }, {Y (k) }, and {Z (k) } are bounded.
(ii)The sequence {C (k) } has a convergent subsequence. If
The proofs of Lemma 1-Lemma 3 and Theorem 2 are provided in the supplement.
Remark 1 It is challenging to analyze the convergence of (11) due to the appearance of two Lagrangian multipliers, or so-called three-block ADMM [5]. Some existing works in the general optimization literature [46] require an accompanying function, such as an objective function, merit function, or augmented Lagrangian function, that possesses properties such as being coercive, separable, or Lipschitz differentiable within a specific domain. However, none of these properties are satisfied for our TNF model. Because (18) includes a positive term Z (k+1) -Z (k) 2 F on the right-hand side, while the others are negative, we need to make an assumption about Z for the convergence analysis in Theorem 2. This line of proof follows from two recent works [8,32].
This section introduces an alternative model based on TNF and ℓ 1 /ℓ F , along with an algorithm and its convergence analysis.
To mitigate the bias caused by the ℓ 1 norm of E in ( 6), we propose utilizing ℓ 1 /ℓ F to encourage sparsity of the tensor E, thereby introducing a new model. The formulation of the second proposed model is given by min
referred to as "TNF+" for the rest of the paper. Note that it is challenging to establish the recovery guarantee of the TNF+ model. The main difficulty lies in the two denominators in (20), which change in opposite directions to satisfy the constraint L + E = X , whereas TNF has only one fractional term. The analysis on the TNF+ model will be left to future work. Similar to TNF, ADMM is employed to solve (20). Specifically, we introduce two auxiliary variables H and D along with a specific splitting scheme that reformulates (20)
Its augmented Lagrangian function is written by
with dual variables Y, Z, U and positive parameters μ 1 , μ 2 , μ 3 . At each iteration, ADMM involves the following updates.
Since the L-subproblem and the H-subproblem are the same as the ones in (11), we use the same closed-form solutions for L (k+1) and H (k+1) . The E-subproblem of ( 23) can be expressed as
which is equivalent to the ℓ 1 minimization elementwise. Hence, it has a closed-form solution given by the soft-thresholding operator, i.e.,
Lastly, the D-subproblem of ( 23) can be expressed as
Similar to H-subproblem (15), we derive the closed-form solution of ( 25) to be
where J (k) is a random tensor with its Frobenius norm being 3 β (k+1) μ 1
for
and
We summarize the overall algorithm of ADMM for solving the problem (20) in Algorithm 2. Compared to Algorithm 1, Algorithm 2 incurs additional complexity due to the update of D, which takes O(n 1 n 2 n 3 n (2) ) and is of the same order as updating H. Consequently, Algorithm 2 exhibits equivalent complexity Algorithm 1, that is,
123
Algorithm 2 ADMM of the TNF+ model.
Require: Observed data X , parameters: μ 1 , μ 2 , μ 3 , kMax, 1: Initialization: (L (0) , E (0) ) by a TNN-based TRPCA model,
We show that the sequence generated by Algorithm 2 has a subsequence convergent to a stationary point of (20) under the following two assumptions. A3: The sequence ({L (k) }, {E (k) }) generated by ( 23) is bounded, so are the nuclear norm of L (k) and the ℓ 1 norm of {E (k) }, denoted by sup k { L (k) * } ≤ M and sup k { E (k) 1 } ≤ m. A4: The Frobenius norm of {H (k) } and {D (k) } have uniform bounds, i.e., there exist positive constants δ 1 and δ 2 such that H (k) F ≥ δ 1 , ∀k and
Lemma 4 Under assumptions A3-A4 with sufficiently large parameters μ 1 , μ 2 , the sequence {Y (k) } and {U (k) } generated by (23) satisfies
where M, m, δ 1 and δ 2 are the constants defined in A3 and A4, respectively.
Lemma 5 Under assumptions A3-A4, the augmented Lagrangian function (22) of the sequence
where c 5 , c 6 , c 7 , c 8 , c 9 are positive constants.
be the sequence generated by (23), then there exist a tensor
and a constant κ 2 > 0 such that
Theorem 3 Under assumptions A3-A4, the sequence
generated by (23) satisfies
where the zero tensor O is composed of seven tensors, each of dimension n 1 × n 2 × n 3 .
We present the proofs of Lemma 4 and Lemma 5 in the supplementary material while omitting the proofs of Lemma 6 and Theorem 3 due to their similarity to the ones in the TNF model.
This section contains extensive experiments aimed at evaluating the performance of our proposed TNF and TNF+ models using both synthetic and real-world datasets. In the synthetic scenario, the observed data are generated as the sum of a low-rank tensor and a sparse tensor.
For denoising experiments, we use real color images with manually added sparse noises. Furthermore, we employ surveillance videos for background modeling, wherein the video is decomposed into a low-rank background tensor and a sparse motion component. Although real-world data may not be strictly low rank, the underlying tensors can be predominantly approximately by their top singular values. Therefore, the proposed methodologies still yield satisfactory results. All experiments are conducted using MATLAB (R2023a) on the Windows 10 platform with an Intel Core i5-1135G7 2.40 GHz processor and 16 GB of RAM.
We generate each observation X ∈ R nfoot_0 ×n 2 ×n 3 by adding a low-rank tensor L 0 and a sparse component E 0 of the same dimension. Here L 0 is obtained by the t-product of two tensors of smaller dimensions, i.e., L 0 = P * Q, where P ∈ R n 1 ×r ×n 3 and Q ∈ R r ×n 2 ×n 3 with r n (2) . The tubal rank of the resulting tensor L 0 is at most r . The elements of tensor P are drawn from an independent and identically distributed (i.i.d.) Gaussian distribution N (0, 1/n 1 ), while the elements of Q are drawn from N (0, 1/n 2 ). As for the sparse components E 0 , we assume its support follows a Bernoulli distribution. Specifically, we randomly set the values of its entries to either +1 or -1, each with probability γ , and set to 0 with probability 1 -2γ, where 2γ ∈ [0, 1] is referred to as a sampling rate or a sparsity level.
We start with empirical evidence of convergence in the proposed TRPCA methodologies by considering a third-order tensor of dimensions 40 × 40 × 30, with a tubal rank of 3 and a sampling rate of 0.2. The relative square errors of tensors L (k) and E (k) to the corresponding ground truth L 0 and E 0 at each iteration k are depicted in Fig. 1, showing that the errors of both models reduce to less than 10 -15 in about 100 iterations. Also, TNF+ has a faster convergence compared to TNF.
Next, we conduct a comparative study of our proposed TNF and TNF+ models with some existing works, including TNN [30], Laplace [50], t-S w, p [54], and p-TRPCA [51]. For our models, we set to 10 -4 in both Algorithm 1 and Algorithm 2. We gradually increase the values of μ 1 and μ 2 instead of fixed values for acceleration, as considered in [30]. Specifically, we initialize μ 1 = 10 -4 and μ 2 = 10 -3 in TNF while μ 1 = 10 -4 and μ 2 = μ 3 = 10 -3 in TNF+. For both TNF and TNF+, we consider an increment factor of 1.1 in each iteration and a maximum cap of these parameters by 10 10 . We set λ = 2 × 10 -4 in TNF for all synthetic experiments, although a finer tuning of λ could potentially enhance our model's performance. For TNF+ model, we set the value of λ to Fig. 2 The success rates of various methods for the TRPCA problem with varying tubal ranks (r ) and sparsity levels (ρ). Each cell represents the percentage of successful recoveries over ten independent realizations. White dashed lines have been added along the diagonal to facilitate comparison We employ success rates as a metric to assess recovery performance, which is defined as the ratio of successful trials to the total number of trials. Specifically, we conduct ten independent random trials for each combination of a predetermined tubal rank (r ) and sampling rate (2γ ). A trial is deemed successful if the relative square error between the recovered tensor L and the ground-truth tensor L 0 , denoted as
, is less than 10 -3 . The success rate is then calculated by dividing the number of successful trials by 10. Finally, we adhere to the experimental setup in [19] for using the tensor dimension of 40 × 40 × 30. The tubal rank in L ranges from 1 to 19 with an increment of 2, while the sparsity in E varies from 0.05 to 0.5 with an increment of 0.05.
Each cell in Fig. 2 illustrates the success rate corresponding to a combination of tubal rank and sparsity levels. Generally, successful recovery is more probable when the sparsity level or tubal rank is relatively low. Fig. 2 showcases that our models outperform the state-of-the-art methods, particularly when the specified L rank is low.
We perform experiments on real-world data comprising color images and videos. For image denoising tests, we employ the peak signal-to-noise ratio (PSNR) [30] and the structural similarity index (SSIM) [47] to quantitatively evaluate recovery performance. Additionally, we present background separation results using grayscale videos. Since the final results are evaluated using PSNR and SSIM, we have adopted the same termination criterion for all competing algorithms; see Algorithm 1 and Algorithm 2.
We conduct image denoising experiments on five color images, labeled by "boat", "houses", "seabeach", "bicycle", and "brook." These images can be obtained online 1 . Each image is corrupted by sparse noise, where 20% of the pixels randomly receive values in the range of 0 to 255, with the locations of the distorted pixels unspecified. Both TNF and TNF+ models are applied for image denoising. In the TNF model, we select the best λ value from the range [4.5 : 0.5 : 6.5] × 10 -5 that achieves the highest PSNR. The initial values are set as μ 1 = μ 2 = 10 -4 . Conversely, for the TNF+ model, we choose λ among the set [1.6 : 0.4 : 2.8] × 10 -2 and initialize μ 1 = 10 -4 , μ 2 = 10 -2 , μ 3 = 10 -4 . We compare the TNF and TNF+ models with TNN [30], Laplace [50], t-S w, p [54], and p-TRPCA [51]. Quantitative evaluations in terms of PSNR and SSIM are presented in Table 3, indicating improved performance with our proposed TNF regularization over stateof-the-art TRPCA methods for denoising sparse noise. Among the five color images, the best performance is achieved either by TNF or TNF+. Notably, the TNF model achieves the highest PSNR for the "houses", "bicycle", and "brook" images, while the TNF+ model appears to perform the best according to the SSIM metric. TNF and TNF+ achieve the top two performances in most cases. Specifically, the average PSNR of TNF and TNF+ is 28.1005 and 28.0875, respectively, both exceeding the rest of the methods by more than 0.2.
We present visual recovery results in Fig. 3. Each image contains a zoomed region for ease of comparison. The noisy inputs are depicted in the second column of Fig. 3, exhibiting severe speckle artifacts. TNF and TNF+ provide results with fewer speckles, particularly noticeable in the zoomed region of the "bicycle" image. In the "house" and "seabeach" images, our methods better preserve the details of zoomed-in letters and trees, while TNN exhibits some blurring. Additionally, Laplace and p-TRPCA models retain artifacts from sparse noise. Moreover, our proposed model effectively removes noise without excessively smoothing the image, as compared to t-S w, p (0.9). This difference is particularly evident in the "boat" and "brook" images.
To analyze the efficiency of all approaches, we summarize the runtime of the algorithms in Table 2.
The TNF algorithm generally runs faster than p-TRPCA and TNF+, but slower than Laplace and S wp (0.9). Although TNF+ is slightly slower than TNF, it is still faster than PSTNN and p-TRPCA and is competitive with Laplace in some cases.
e) t-S w, p (0.9), (f) p-TRPCA, (g) TNF, and (h) TNF+. From left to right: five color images ("boat," "house," "seabeach," "bicycle," and "brook")
The background modeling problem aims to separate foreground objects from the background. In videos, the background is typically approximated as a low-rank tensor since it remains nearly constant across the timeframes. In contrast, moving foreground objects are treated as sparse components. In the context of the TRPCA problem, the background and foreground tensors correspond to the low-rank tensor L 0 and the sparse tensor S 0 , respectively. We conduct experiments using sequences of "airport" (144 × 176 × 400) and "bootstrap" (120 × 160 × 400) from the 12R dataset [25], as well as "shoppingmall" (220 × 352 × 400) from [25]. All three videos have slow object movement against different background scenarios. We compare our TNF and TNF+ models with SNN, TNN, PSTNN, Laplace, and t-S w, p (0.9) models. We set λ = 10 -6 and μ 1 = μ 2 = 10 -5 in TNF and λ = 1/ √ max(n 1 , n 2 )n 3 , μ 1 = μ 3 = 10 -5 and μ 2 = 10 -3 in TNF+.
Fig. 4 presents the visual results of background modeling obtained by various methods. For each video, we select one image in the sequence as shown in the first column (a) of Fig. 4, followed by the background images of the same frame obtained by (b) TNN, (c) Laplace, (d) t-S w, p (0.9), (e) EAP-TRPCA-FFT [37], (g) TNF, and (h) TNF+. The second row of each video depicts the motion in the scene. In the "airport" video, the background recovered by both TNF and TNF+ contains less ghost silhouette compared to other methods, indicating a better background separation. Similarly, in the "bootstrap" and "shopping mall" videos, the humans identified by the proposed method look sharper and clearer than the ones by other methods.
A F . Using the frontal slices of a tensor A, we define the block circulant matrix of A as bcirc(A) := ⎡ ⎢ ⎢ ⎢ ⎣ A (1) A (n 3 ) • • • A (2) A (2) A (1) • • • A (3) . . . . . . . . . . . .
We define two operators:
A (2) . . .
and fold (unfold(A)) = A, (33) where unfold(•) maps A to a matrix of size n 1 n 3 × n 2 and fold(•) is its inverse operator.
Definition A.4 (t-product [22]) Let A ∈ R n 1 ×l×n 3 and B ∈ R l×n 2 ×n 3 , then the t-product A * B is defined by
resulting a tensor of size n 1 × n 2 × n 3 . Note that A * B = Z if and only if A B = Z.
Definition A.5 (identity tensor [22]) The identity tensor I ∈ R n×n×n 3 is the tensor with its first frontal slice being the n × n identity matrix and other frontal slices being all zeros. It is clear that A * I = A and I * A = A given the appropriate dimensions.
Definition A.6 (tensor conjugate transpose [22]) The conjugate transpose of a tensor A ∈ C n 1 ×n 2 ×n 3 is a tensor A * obtained by conjugate transposing each of the frontal slices and then reversing the order of transposed frontal slices 2 through n 3 .
Definition A.7 (orthogonal tensor [22]) A tensor Q ∈ R n×n×n 3 is orthogonal if it satisfies
Definition A.8 ( f -diagonal tensor [22]) A tensor is called f -diagonal if each frontal slice is a diagonal matrix.
√ n (1) n 3 = 0.0289, consistent with the λ value used in the TNN model[30]. As for the competing methods (TNN, t-S w, p , and p-TRPCA), we employ the Matlab codes provided by the respective authors with default parameter settings. For the Laplace model, we adapt the code of the tensor completion model into the TRPCA model while setting to 10 -6 .
http://r0k.us/graphics/kodak
√n 3