Flexible Generalized Low-Rank Regularizer for Tensor RPCA

1 Introduction

Tensor data are ubiquitous, many real-world data are usually inherently multidimensional, with information stored in multi-way arrays known as tensors, e.g., images, videos, network flow data, etc. In recent years, significant advancements across various interdisciplinary domains have been made in tensor analysis, such as machine learning [Wen et al., 2024; Phothilimthana et al., 2024], data mining [Zhang et al., 2023a; Huang et al., 2024], and computer vision [Zhao et al., 2024; Liu et al., 2024a]. However, due to the inherent limitations of signal acquisition equipment, including sensor sensitivity, photon effects, and calibration errors, tensor data gathered from real-world environments frequently suffer from substantial corruption [Wang et al., 2023a]. Consequently, tensor recovery has become a crucial task in tensor analysis.

† Corresponding author: Yulong Wang

This paper concentrates on the problem of Tensor Robust Principal Component Analysis (TRPCA) [Huang et al., 2015], which seeks to recover the underlying low-rank tensor L and sparse tensor E from their sumM(see Figure 1 for a visual representation) and solves the following problem

where λ > 0 is a regularization parameter, rank(L) denotes the rank of clean tensor L and ∥E∥1 is ℓ1-norm (sum of the absolute values of all the entries) to measure the sparsity of the noise tensor E. A key challenge is the definition of tensor rank, which is inherently more complex than matrix rank. Various conventional methods for defining tensor rank originate from distinct tensor decompositions. For instance, inspired by the tensor singular value decomposition (t-SVD), [Kilmer et al., 2013] proposed the tensor tubal rank that can be efficiently computed using the fast Fourier Transform (FFT). Since the non-convexity and discontinuity of the rank function, solving the problem (1) is usually NP-hard. Consequently, [Lu et al., 2020] proposed a novel tensor nuclear norm as a convex approximation to the tensor tubal rank and proposed a new TRPCA method defined as follows

where ∥ · ∥∗ represents the tensor nuclear norm (TNN). Furthermore, recent research by [Kilmer et al., 2021] has demonstrated the optimal representation and compression capabilities of t-SVD, further highlighting the significance of model (2) in capturing the intrinsic low-rank structures of tensors. As a result, the model (2) under t-SVD has garnered considerable interests recently [Hou et al., 2024; Liu et al., 2024c; Qin et al., 2024].

Despite the impressive performance of TRPCA, it still exhibits several limitations. Specifically, when minimizing the TNN, TRPCA employs tensor singular value thresholding to uniformly diminish all singular values. In real-world applications, singular values often carry distinct physical meanings, supported by prior knowledge indicating that larger singular values are generally associated with more significant information. The uniform shrinkage approach of TRPCA fails to account for these differences among singular values, potentially leading to suboptimal results.

While many existing advanced methodologies [Gao et al., 2020; Jiang et al., 2020; Wang et al., 2023b; Zhang et al., 2023b; Yan and Guo, 2024; Liu et al., 2024b] develop various TNN-based low-rank regularizers that penalize large singular values less and small singular values more, thereby efficiently preserving essential information and filtering out irrelevant details. However, their discrete and fixed models lack flexibility for diverse scenarios. To address this problem, we design a novel Flexible Generalized low-rank regularizer (FGTNN) to adaptively assign different penalties to distinct singular values and impose the constraint on the sparse component. We have shown that several existing TRPCA models can be reformulated as special cases of FGTRPCA. Apart from that, we can also derive a wider family of new TRPCA models by tuning a continuous parameter to improve performance. Through this, our model significantly improves flexibility and efficiency in complex situations.

Note that the low-rankness prior and the smoothness prior modeled by total variation (TV) are widely utilized in tensor recovery applications [Ko et al., 2020; Qiu et al., 2021]. This prior states how similar objects/scenes (with shapes) are adjacently distributed [Peng et al., 2022b]. Most previous works encoded the two priors with two independent regularizers and incorporated them into a unified model, which achieved better performance [Peng et al., 2020; Peng et al., 2022a]. However, they have two drawbacks: (1) it is challenging to fine-tune the regularization parameter between the two terms; (2) the theoretical guarantee for exact recovery remains unproven for the related methods.

Given the circumstances above, [Wang et al., 2023a] proposed the tensor Correlated Total Variation (t-CTV) norm which integrates the two priors into a single regularization term, eliminating the need for tuning separate parameters. Moreover, this work offered theoretical guarantees for the precise recovery of analogous tensor methods that concurrently model both priors. Analogously, the integration regularization term was also based on TNN in the gradient domain. Consequently, [Huang et al., 2024] proposed a reweighted regularizer based on ℓp norm as a surrogate for t-CTV term. In this paper, we employ FGTNN to explore the inherent structural properties of gradient tensors and introduce a new tensor-correlated Flexible Generalized Joint Prior (t-FGJP) regularizer.

Our principal contributions are outlined as follows:

• We propose a flexible generalized low-rank regularizer (FGTNN) that accounts for the varying importance of different singular values in low-rank tensors and develop a novel FGTRPCA framework. The FGTRPCA, not only regards many existing TRPCA methods as special cases, but also opens a door to design a broad new family of TRPCA methods by tuning a continuous parameter. This enhances the flexibility of our model to counter more intricate scenarios.
• Considering the low-rankness and smoothness priors simultaneously, we propose a novel tensor-correlated Flexible Generalized Joint Prior (t-FGJP) regularizer based on FGTNN. It maintains the flexibility of discriminatively controlling different singular values of the gradient tensors and can derive a new smooth FGTRPCA

model, termed SFGTRPCA.

• We design ADMM-based [Boyd et al., 2011] optimization algorithmic frameworks tailored for our FGTRPCA and SFGTRPCA models. Extensive experiments on various tensor denoising and recovery tasks demonstrate the advantages of our models.

2 Notations and Preliminaries

First, we present some key notations and definitions used throughout the paper. We represent scalars, vectors, and matrices using lowercase letters, boldface lowercase letters, and boldface uppercase letters, e.g., x, x, X, respectively. Tensors are presented by bold calligraphic letters, e.g., X. 1d1×d2 and 1d1×d2×d3 represent a matrix of size d1 ×d2 and a tensor of size d1 ×d2 ×d3 with all entries as ones. For a 3-order tensor X ∈ Rd1×d2×d3 , we denote Xijk as its (i, j, k)-th entry, X(i, :, :) as its horizontal slice, X(:, j, :) as its lateral slice, X(:, :, k) as its frontal slice, respectively. For convenience, the frontal slice X(:, :, k) is often denoted as X(k) . The tensor nuclear norm (TNN), tensor ℓ1 norm (TL1N), tensor Frobenius norm and tensor infinity norm of X are defined by ∥X∥∗ , ∥X∥1 = ∑ijk |Xijk| , ∥X∥F = √∑ijk |Xijk|2 and ∥X∥∞ = maxijk|Xijk|, respectively. The transpose of X is defined as X T ∈ Rd2×d1×d3 [Lu et al., 2020].

Definition 1. (T-SVD) [Kilmer and Martin, 2011] For a tensor X ∈ Rd1×d2×d3 , it can be factorized by t-SVD as

where U ∈ Rd1×d1×d3 , V ∈ Rd2×d2×d3 are orthogonal tensors, i.e., U ∗ U T = U T ∗ U = V ∗ V T = V T ∗ V = I, and S ∈ Rd1×d2×d3 is an f-diagonal tensor, i.e., each frontal slices are the diagonal matrices, and "∗" is the t-product.

Definition 2. (Tensor Nuclear Norm, TNN) [Lu et al., 2020] For a tensor X ∈ Rd1×d2×d3 , d = min(d1, d2), the Tensor Nuclear Norm of X is defined as

where ¯ X is the result by applying FFT on X along the third dimension, i.e., ¯ X = fft(X, [], 3). ¯X(k) is the k-th frontal slice of ¯ X, σi ( ¯X(k) ) is the i-th singular value of ¯X(k) .

3 ProposedMethods

We begin by detailing the motivation for FGTNN and its characteristics, then propose the FGTRPCA framework and implement it using an efficient optimization algorithm. Furthermore, by simultaneously considering low-rankness and smoothness priors, we develop a novel t-FGJP regularizer and apply it to solve TRPCA problem, termed SFGTRPCA.

3.1 Flexible Generalized TNN

According to Definition 2, the original TNN uniformly shrinks each singular value of the low-rank tensor L when minimizing the tensor nuclear norm, which may lead to suboptimal solution. Indeed, larger singular values are associated with more critical information within the tensor. Inspired by the common purposes of enhancing TRPCA methods, we introduce a flexible generalized tensor nuclear norm (FGTNN) as a unified framework, which is defined below.

Definition 3. (FGTNN) For a tensor X ∈ Rd1×d2×d3 , d = min(d1, d2), the Flexible Generalized Tensor Nuclear Norm (FGTNN) is defined as follows

where gα(x) follows [Barron et al., 2023]:

where α ∈ R is a continuous parameter that controls the shape of gα(x) and c > 0 is a scale parameter.

Remark 1. Our proposed FGTNN mainly exhibits two desirable properties. 1) Generalizability: By introducing a continuous parameter α, low-rank regularizers in many existing popular methods such as TRPCA, LRTF, ETR, and DATRPCA can be viewed as special cases of FGTNN with different values of α.(see Table 1 for more details); 2) Flexibility: We can develop plenty of new low-rank regularizers by tuning α and achieve better performance. Compared to the method with fixed-form low-rank regularizer, our model gains flexibility and can adapt to more complex scenarios. Apart from that, gα(x) in FGTNN controls the penalty strength to singular values. Figure 3(a) intuitively presents the characteristics of gα(x). We observe that gα(x) increases slower than |x| for various α, which means less shrunk to large singular values, preserving the critical information within the tensor to a greater extent. More importantly, α is related to the shape of gα(x). When α → -∞, gα(x) follows an approximately exponential form; When α = 0, gα(x) takes a logarithmic form; When α = 1, gα(x) turns to |x|; And in the other case of α, gα(x) is represented in a approximate power form.

Specifically, we can extend FGTNN to the sparse component and define the flexible generalized tensor ℓ1 norm (FGTL1N).

Definition 4. (FGTL1N) For a tensor X ∈ Rd1×d2×d3 , the Flexible Generalized Tensor ℓ1 Norm (FGTL1N) is defined as follows:

3.2 Flexible Generalized TRPCA

By integrating FGTNN and FGTL1N into the TRPCA framework, we formulate the following Flexible Generalized TRPCA (FGTRPCA) model.

Remark 2. It is worth pointing out that FGTRPCA serves as a versatile framework for addressing TRPCA problems. By adjusting the parameter α, it can be tailored to develop new TRPCA methods. Specifically, in this paper, we introduce a variant of FGTRPCA with α = 0.5, a choice that has not been explored before.

Note that FGTNN includes a series of specific functions that are nonlinear and complex, thus making it hard to obtain the optimal solution of the FGTRPCA model. In this paper, we design an efficient algorithm optimization framework based on the ADMM framework [Boyd et al., 2011] to implement the FGTRPCAmodel.

Proposition 1. For gα(x), there exists a convex conjugate function ϕ : R → R which satisfies

and for fixed x, the minimum is reached at w = ξ(x; c)(c is a positive constant), which is defined as

Remark 3. According to Proposition 1, gα(x) in Eq. (6) can be optimized by an adaptive alternating weighted minimization scheme. From the perspective of weights, smaller weights represent smaller shrinkages to singular values. As shown in Figure 3(b), TNN assigns equal weight to each singular value, i.e., TNN treats each singular value equally. For our proposed FGTNN, larger singular values will adaptively receive smaller weights, resulting in less shrinkage.

According to Proposition 1, FGTNN can be transformed into

where the Wki is the k, i-th element of matrix W ∈ Rd3×d . The minimum is reached at Wki = ξ(σi(¯L(k) ); c). Similarly, as for FGTL1N, we have

where the Wijk is the i, j, k-th element of tensor W ∈ Rd1×d2×d3 . The minimum is reached at Wijk = ξ(|Eijk|; c).

Notably, problem (8) can be reformulated as the weighted tensor nuclear norm minimization problem (11) and the weighted tensor ℓ1 norm minimization problem (12). The following defines two key concepts: Weighted tensor nuclear norm (WTNN) and weighted tensor ℓ1 norm (WTL1N).

Definition 5. (Weighted Tensor Nuclear Norm, WTNN)[Wang et al., 2023b] For a tensor X ∈ Rd1×d2×d3 and a weight matrix W ∈ Rd3×d , d = min(d1, d2), the WTNN of X is defined as

Definition 6. (Weighted Tensor ℓ1 Norm, WTL1N)[Wang et al., 2023b] For a tensor X ∈ Rd1×d2×d3 and a weight tensor W ∈ Rd1×d2×d3 , the WTL1N of X is defined as

By incorporating Eq. (11) and Eq. (12) into model (8), and according to the definition of WTNN and WTL1N, we have

where ΦM(W) and ΦT (W) are defined such that ΦM(W) = ∑d1 k=1 ∑d2 i=1 ψ(Wki) and ΦT (W) = ∑d1 i=1 ∑d2 j=1 ∑d3 k=1 ψ(Wijk). In the next part, we will present the optimization for implementing FGTRPCA.

3.3 Optimization for FGTRPCA

The Lagrangian function of the FGTRPCA model is L(L, E, W, W, Z, µ) = ∥L∥W,∗ + λ∥E∥W,1 + ΦM (W)

where Z ∈ Rd1×d2×d3 denotes the Lagrangian multiplier and µ is a positive parameter. Each variable can be updated alternately in the scheme of the ADMM framework.

Step1: Update L by fixing the other variables:

The closed-form solution of (17) can be easily obtained with the following proximity operator.

Lemma 1. Given X ∈ Rd1×d2×d3 with t-SVD X = U ∗ S ∗ V ∗ and a weight matrix W ∈ Rd×d3 , where wk is the k-th column of W and d = min{d1, d2}. Considering the following Weighted Tensor Nuclear Norm minimization (WTNNM) problem

where ∥ · ∥W,∗ denotes the WTNN, and Prox∥·∥W,∗ is defined as a proximal operator. For non-descending weights 0 ≤ Wk1 ≤ Wk2 ≤ · · · ≤ Wkd(k = 1, . . . , d3), the problem (18) has the global solution which is defined as

where ifft denotes the inverse fast Fourier transform applied along the third dimension, PW(¯S) is a tensor to meet the conditions of its k-th frontal slice is Pwk (¯S(k) ) for k = 1, . . . , d3. ¯S(k) is the k-th frontal slice of ¯S, and Pwk (¯S(k) ) denotes a diagonal matrix which can be computed as (Pwk (¯S(k) ))ii = (¯S(k) ii -wki)+, where (x)+ = x if x > 0 and (x)+ = 0 otherwise. wki is the i-th element of the wk.

By recalling the definition of WTNN in Definition 5, we have 1 µt ∥L∥W,∗ = ∥L∥ 1 µt W,∗ . Based on Lemma 1, the solution of the subproblem (17) can be described as

Step2: Update E by fixing other variables:

To get the closed-form solution of the above problem, we utilize the tensor soft-thresholding operator (TST) defined below to update Et+1.

where the ijk-th entry of TST is defined by

Step3: Update the elements of W and W by an adaptive way according to Proposition 1

Step4: Update the Lagrangian multiplier tensor Z and the parameter µ by

Algorithm 1 FGTRPCA algorithm

Input: Observation tensor data M ∈ Rd1×d2×d3 , and the parameter λ.

• 1: Initialize L0 = E0 = Z0 = 0, W0 = 1d3×d, W0 = 1d1×d2×d3 , µ0 = 10-2 , ρ = 1.1, ϵ = 10-6 , and t = 0.
• 2: while not converge do
• 3: Update the low-rank tensor L by Eq. (17).
• 4: Update the sparse tensor E by Eq. (21).
• 5: Update the weightsWandW by Eq. (24).
• 6: Update the Lagrangian multiplier Z by Eq. (25).
• 7: Update the parameter µ by Eq. (26).
• 8: Check the convergence condition in Eq. (27).
• 9: end while

Output: L = Lt+1, E = Et+1

where ρ = 1.1. The convergence conditions are defined as

The whole optimization procedure is summarized in Algorithm 1.

3.4 Smooth FGTRPCA

Considering a structured tensor that exhibits both lowrankness and smoothness, we devise a novel regularizer that aims to represent both two properties simultaneously on the gradient tensors, instead of employing a combination of two distinct regularizers for encoding the two properties. We first introduce the definition of the gradient tensor and present our proposed tensor-correlated Flexible Generalized Joint Prior (t-FGJP) regularizer.

Definition 7. (Gradient tensor)[Wang et al., 2023a] For a tensor X ∈ Rd1×d2×d3 , its gradient tensor along the k-th mode is defined as

where Ddk is a row circulant matrix of (-1, 1, 0, ..., 0).

Definition 8. (t-FGJP) For a tensor X ∈ Rd1×d2×d3 , the proposed t-FGJP norm is defined as

where Γ represents a priori set of directions along which X equips both low-rankness and smoothness priors and γ := #{Γ} denotes the cardinality of Γ. By incorporating both tFGJP and FGTL1N into the TRPCA framework, we propose a smooth FGTRPCA (SFGTRPCA) model defined as

The SFGTRPCA optimization problem is similar to the FGTRPCA problem. Details of the optimization algorithm and the entire procedure are presented in the supplementary material due to space limitations.

4 Experiments

In this section, we present several real-world experiments to substantiate the effectiveness of our models. Additional results are provided in the supplementary material.

4.1 Settings

Datasets. For comprehensive comparison, we use 4 widely used tensor data types including color images, grayscale videos, hyperspectral images (HSIs), and multispectral images (MSIs). For color images, we choose 3 widely used datasets including Berkeley Segmentation Dataset 1 (BSD) [Martin et al., 2001], Kodak [Kodak, 1993] dataset 2 , and ZheJiang University (ZJU) [Hu et al., 2012] dataset 3 . For grayscale videos, we use 14 grayscale video sequences from the YUV dataset 4 and select the first 100 frames for each sequence. For HSIs, we utilize Cuprite 5 , DCMall 5 , Urban 5 , Indian Pines 5 , and Pavia University 5 (PaviaU) with their first 50 bands from each HSI dataset for experiments. For MSIs, we randomly select 4 MSIs from the CAVE dataset [Yasuma et al., 2008].

1 https://www2.eecs.berkeley.edu/Research/Projects/CS/vision/ bsds/

2 http://r0k.us/graphics/kodak/

3 https://sites.google.com/site/zjuyaohu/

4 http://trace.eas.asu.edu/yuv/

5 https://lesun.weebly.com/hyperspectral-data-set.html

Baselines. Our baselines are divided into two categories based on different priors. (1) Low-rankness: TRPCA [Lu et al., 2020], ETRPCA [Gao et al., 2020], and PTRPCA [Yan and Guo, 2024]; (2) Joint Low-rankness & Smoothness: tCTV [Wang et al., 2023a] and RTCTV [Huang et al., 2024]. We utilize the parameters recommended by the authors. For the key parameter α in our models, we search from a candidate set and employ α = 0.5. More detailed parameter settings are described in the supplementary material.

Evaluation metrics. The peak signal-to-noise ratio (PSNR) and structural similarity (SSIM) are used to evaluate the recovery performance.

Noising Data Construction. For each color channel of the color image, each frame of the grayscale video, and each band of HSI and MSI, we add random salt and pepper noise at varying noise ratios of 10%, 20%, and 30%.

4.2 Experimental Results

Visual Quality. To clearly illustrate the advantages of our methods on color image recovery, Figure 4 presents 6 sample images from the BSD dataset, along with the recovery results under 20% salt and pepper noise. The PSNR and SSIM values are listed above the recovered images to enhance the credibility of the results. The results show that SFGTRPCA constructs more image details and color information (Especially the contour and color of the moon in the 4-th image). Additionally, we have observed that the proposed FGTRPCA and SFGTRPCA methods significantly outperform the baseline methods under corresponding priors.

Quantitative Quality. Table 2 displays the results of all the competitors on the 4 tensor types with 10% and 20% noise. From the results, we draw the following conclusions:

• Firstly, SFGTRPCA outperforms all comparison methods, achieving an average PSNR improvement of over 4.4 dB compared to the second-best baseline. Specifically, it attains PSNR gains of 17.16% and 14.31% for

color images and MSIs with 10% noise, respectively. This is because our model can adaptively learn appropriate weights for the frontal slices of the tensor through a weighting function.

• Secondly, compared to the baselines that only consider the low-rankness prior (TRPCA, ETRPCA, and PTRPCA), our FGTRPCA demonstrates the best performance in most situations, and achieves an average improvement of over 1.7 dB in PSNR compared to the second-best baseline. Notably, our FGTRPCA always leads in SSIM values, which indicates that our FGTRPCA can recover more structural information.
• Thirdly, our methods consistently achieve competitive evaluation scores across diverse tensor data types under varying noise levels, demonstrating their ability to effectively leverage low-rank and sparse structures for robust recovery.

Parameter Analysis. It should be noticed that the parameter α plays a crucial role in our models, which can adjust the flexibility and generalizability to adapt to various scenarios. To explore its impact on different cases, we examine some recovery tasks with different values of α under various noise ratios on ZJU (color images) and Indian Pines (HSIs) datasets in Figure 5. As seen, by tuning α, our SFGTRPCA model gains significant improvements in various situations. This improvement highlights the advantage of incorporating α as a hyperparameter instead of a fixed formula and validates the flexibility of our framework.

5 Conclusion

In this article, we propose a flexible generalized low-rank regularizer termed FGTNN, and develop a novel FGTRPCA framework. Many existing TRPCA methods can fall into our special cases, which reveals connections between existing and new TRPCA approaches through a continuous parameter. Additionally, by integrating low-rankness and smoothness priors, we design a novel regularizer based on FGTNN and propose a smooth FGTRPCA (SFGTRPCA) model. Compared to existing works, our models process with flexibility and generalizability, demonstrating superior performance.

Ethical Statement

There are no ethical issues.

Acknowledgments

We are grateful to the anonymous IJCAI reviewers for their constructive comments. This work was supported by the National Natural Science Foundation of China (under Grant Nos. 62276111, 62076041, 61806027, 61702057, and 62202009), the Fundamental Research Funds for the Central Universities of China (under Grant Nos. 2662023XXPY002 and 2662023LXPY005), the HZAU-AGIS Cooperation Fund (under Grant No. SZYJY2023010), and the IndustryUniversity-Research Cooperation Project of Zhuhai, Guangdong, China, under Grant GP/026/2020 and Grant HF-0102021.

Contribution Statement

Zhiyang Gong and Jie Yu are co-first authors, and Yulong Wang is the corresponding author.