Beyond Low-rankness: Guaranteed Matrix Recovery via Modified Nuclear Norm

1 Introduction

The nuclear norm (NN), serving as a convex relaxation of the matrix rank, is widely applied to various matrix optimization problems due to its ability to effectively preserve the global low-rank property of data while possessing many desirable theoretical properties [Candes and Recht, 2012; Cand`es et al., 2011; De Silva and Lim, 2008; Recht et al., 2010; Gu et al., 2014]. The data property is typically encoded by a regularizer term R(·) and incorporated into the following energy function (1):

where X and Y represent the data to be recovered and the observed data, respectively. The function L(X,Y) is the loss function, which can be in the form of ℓ1 and ℓ2 norm.

∗Corresponding authors

However, in many cases, alongside the global low-rankness of data, local prior information also plays a crucial role, especially in data related to computer vision tasks such as hyperspectral image [Wang et al., 2017], multispectral image [Xie et al., 2017], CT images [Wang et al., 2023], and surveillance videos [Peng et al., 2022b], as shown in Fig. 1. Efficiently integrating global and local information to obtain a model with theoretical guarantees is an important issue for restoration tasks. Previous methods of integrating global and local information typically involve constructing multiple regularizer terms and combining them additively [Wang et al., 2017; He et al., 2015; Xue et al., 2021; He et al., 2017; Shang et al., 2023; Chen et al., 2023]. Taking global low-rankness and local smoothness properties as an example, the traditional fused regularization method is given by:

where ∥X∥TV is the total variation (TV) regularizer to encode the sparsity of difference map of the original data [Rudin et al., 1992], and β is the trade-off parameter need to be finetuned for each data. The TV regularizer often fails to capture the local smoothness of the data adequately. Therefore, in many cases, additional regularizers need to be incorporated in the manner (2). This inevitably introduces the problem of selecting more balanced parameters. Besides, except for NN, many regularizers don't hold good theoretical properties.

To tackle the above two drawbacks, we introduce a new modified nuclear norm (MNN) that can capture both the local information and global low-rankness of data. Specifically, the MNN is defined by adopting a suitable transformation and then performing the NN on the transformed matrix, i.e.,

Compared to NN, MNN (3) can concurrently capture local information and global low-rankness of data. Specifically, the transformation D(·) exploits useful local correlation information of the matrix and performing the NN on the transformed matrix could finely utilize such local correlation based on the compatibility of norms.

Specifically, the proposed MNN framework offers two key advantages over existing methods that integrate global and local information. First, MNN eliminates the need for parameter tuning required in additive manner (2). Second, under mild transformation assumptions, MNN provides exact recovery guarantees for two typical matrix applications: Robust PCA and Matrix Completion (MC). Building on theoretical tools related to nuclear norms [Candes and Recht, 2012; Cand`es et al., 2011; Chen, 2015; Candes and Plan, 2010; Negahban and Wainwright, 2012; Shahid et al., 2015], the MNN framework leverages these tools to offer theoretical guarantee. It incorporates various classical transformations, such as the difference operator [Peng et al., 2022b; Wang et al., 2023; Liu et al., 2023], the Sobel operator [Kanopoulos et al., 1988], and the Laplacian operators [Wang, 2007], enabling the integration of diverse local information. In summary, the contributions of this paper are:

Modeling: We propose the MNN framework, which can simultaneously exploit global and local information of data by performing the NN on a transformed matrix that encodes local correlations through a suitable transformation operator without trade-off parameters.

Theory: Under mild conditions, we prove the exact recoverability theory of MNN on two types of problems: Robust PCA and MC. Although the theoretical bounds are not improved compared to NN, from the perspective of embedding local smoothness, MNN provides a unified recoverability theory framework for integrating low-rank and multi-layer local information priors. Extensive experiments validate the efficacy of the MNN framework.

Operator: Classical operators are introduced into the MNN framework to characterize local smoothness. This paper demonstrates that for low-rank image data, the difference, Sobel, and Laplacian operators can be directly embedded into MNN to improve model's performance. In particular, Laplacian operators can provide richer local information than the widely used first-order differences operator.

2 Modified Nuclear Norm

In this part, we will give the forms and theoretical results about the MNN-induced Robust PCA and MC models.

2.1 Motivations

The previous global and local information fusion model [Wang et al., 2017; He et al., 2015; Xue et al., 2021; He et al., 2017; Peng et al., 2022a; Peng et al., 2020] was characterized by constructing multiple regularizers and summing them up, as follows:n∑

where Ri(X)(i = 1, · · · , n) are regularizers, such as the nuclear norm (NN) and total variation (TV) regularizer in the form (2), and τi are trade-off parameters, manner (4) is intuitive and effective. However, it suffers from two key issues: the challenge of parameter selection among multiple regularizers and the lack of theoretical recoverability. To address these limitations, inspired by the norm compatibility and exact recovery guarantees of the nuclear norm, we propose the MNN defined in Eq. (3). As demonstrated in Remark 1, Eq. (3) effectively models both global and local information, eliminating the need for hyperparameter tuning.

Remark 1. MNN (3) can simultaneously encode global and local information based on two aspects.

1) MNN could capture global low-rankness. We assume that D(·) can be reformulated as a full-rank matrix-induced linear operator, i.e., there exists a full-rank matrix A such that

Based on the above derivation, it can be inferred that the low-rankness of D(X) stems from the low-rankness of X, i.e., minimizing the rank of D(X) is equivalent to minimizing the rank of X. Hence, MNN can characterize the global lowrankness of the data.

2) MNN could capture local information. According to the norm compatibility theorem, we have

holds for all transformation operators. Thus, it can be inferred that minimizing ∥D(X)∥∗ can simultaneously minimize both ∥D(X)∥F and ∥D(X)∥1. If an appropriate transformation operator D(·) is chosen so that D(X) can capture useful local information of data (e.g., edge structures), then MNN can effectively utilize such local information based on Eq. (6). For example, when D(·) is chosen as the firstorder difference operator ∇(·), ∥∇(X)∥F and ∥∇(X)∥1 correspond to isotropic [Rudin et al., 1992] and anisotropic [He et al., 2017] TV regularizer, respectively. Therefore, our MNN can then characterize the local smoothness of data 1 .

1 If D(·) is set as identity mapping, ∥D(X)∥∗ degenerates to ∥X∥∗. Since ∥X∥F and ∥X∥1 cannot encode local structural information of the data, ∥X∥∗ can only characterize the global low rankness.

Indeed, several works such as Correlated Total Variation (CTV [Wang et al., 2023; Peng et al., 2022b; Liu et al., 2023]) can be seen as a special case of our MNN by setting the transformation operator as the first-order difference.

Remark 2. Unlike the first-order difference in CTV, which only captures adjacent similarities, the proposed MNN framework accommodates operators with larger receptive fields, enabling more effective modeling of local smoothness across broader regions. What's more, MNN also removes the need for tuning the parameters between multiple regularization terms. While combining several regularizers improves interpretability, it often requires careful hyperparameter tuning-poor choices can yield suboptimal results.

2.2 Theoretical Guarantees

Next, we establish the exact recovery guarantees of MNNinduced RPCA and MC models.

Models

Robust PCA [Cand`es et al., 2011] is a problem aiming at accurately separating a low-rank matrix X0 ∈ Rn1×n2 and a sparse matrix S0 from the observed data matrix M = X0+S0. By using MNN and ℓ1 norms to respectively encode the global low-rankness and local priors of low-rank matrices, as well as the sparsity of sparse matrices, we can derive the following MNN-RPCA model:

MC [Candes and Recht, 2012] is a problem aiming to accurately infer the clean data X0 from a limited set of observed data M (the support set denoted as Ω). Using MNN, we can obtain the following MNN-MC model:

where PΩ(·) is a mapping operator. If (i, j) ∈ Ω, then PΩ(Xij) =Xij; otherwise, it is set to 0.

In our MNN-based model, the single regularization term simultaneously captures both global and local information, which avoids the need for carefully tuning the trade-off parameter τi required by additive model-based methods (4).

Assumptions

Before giving the theorems, we need three mild assumptions. Assumption 1 (Incoherence Condition). For the low-rank matrix X0 ∈ Rn1×n2 with rank r, it follows the incoherence condition with parameter µ, i.e.,

where U ∈ Rn1×r and V ∈ Rn2×r are obtained from the singular vector decomposition of X0 and ek is the unit orthogonal vector.

Incoherence condition is a widely used assumption for lowrank recovery problems [Cand`es et al., 2011; Chen, 2015; Candes and Romberg, 2007] to control the dispersion of the elements of the low-rank matrix. If the data is a rank-r identity matrix, since the observed values are likely to be zero, it is difficult to infer the non-zero elements, so we need this condition to keep the data away from the identity matrix.

The random distribution assumption for S0 and the normalization assumption of D(·) are as follows:

Assumption 2 (Random Distribution). For the sparse term S0, its support Ω is chosen uniformly among all sets of cardinality m, and the signs of supports are random, i.e.

Assumption 3 (Normalization). The Frobenius norm of the linear transformation D(·) in Eq. (6) is one.

Assumption 3 ensures that the elements of the transformed data D(X) remain bounded, allowing key inequalities in the dual verification to hold. If the Frobenius norm of D(·) is not one, normalization can be used to satisfy Assumption 3.

Main Results

Based on Assumptions 1-3, we can derive that:

Theorem1 (MNN-RPCATheorem). Suppose that D(X0) ∈ Rn1×n2 , S0 and D(·) obey Assumptions 1-3, respectively. Without loss of generality, suppose n1 ≥ n2. Then, there is a numerical constant c > 0 such that with probability at least 1 - cn-10 1 (over the choice of support of S0), the MNNRPCA model (7) with λ = 1/(√n1) is exact, i.e., the solution

where ρr and ρs are some positive numerical constants, and m is the number of the support set of S0.

Theorem 2 (MNN-MC Theorem). Suppose that D(X0) ∈ Rn1×n2 and D(·) obey Assumptions 1 and 3, Ω ∼ Ber(p) and m is the number of Ω, where Ber(p) represents the Bernoulli distribution with p. Without loss of generality, suppose n1 ≥ n2. Then, there exist universal constants c0, c1 > 0 such that X0 is the unique solution to MNN-MC model (8) with probability at least 1 - c1n-3 1 logn1, provided that

Theorems 1 and 2 establish the exact recoverable theory for the fusion-induced model combining low-rank and general local smoothness priors, which was unavailable in previous studies. Proofs are provided in the supplementary materials.

2.3 Optimizations

The exact recoverable theory, as outlined in Theorems 1 and 2, asserts that the optimal solution ( ˆX, ˆS) of the model accurately reflects the true value (X0, S0). Thus, the following corollary can be inferred with high probability.

Corollary. Suppose X0 and S0 satisfy Assumptions 1 and 2, and transformation operator D(·) satisfy Assumption 3. Denote the objective functions of the RPCA and MC models as

respectively, where λ = 1/√n1 and µ = (√n1 + √n2)√pσ according to [Candes and Plan, 2010], and n1, n2, σ, p are the sizes of matrix, noise standard variance, and missing ratio. Then, for any X, we have:

Then, according to Corollary 2.3, we can directly perform a simple gradient descent on the objective function (14) to obtain the final solution. More details can be seen in the supplementary materials.

2.4 Some Suitable Transformation Operators for MNN

In this section, we shift our attention to another important aspect, namely, the selection of the transformation operator D(·). The local smoothness of images is typically achieved through convolution operators. The most common one is the first-order difference operator ∇(·) =[-1,1]/[-1;1]. Based on the first-order difference operator [Rudin et al., 1992] and its fast Fourier transform-based solving algorithm [Chambolle, 2004; Huang et al., 2008], various types of total variation regularization have been developed in recent decades [Wang et al., 2017; He et al., 2015; Peng et al., 2020]. However, the difference operators may not be able to characterize local information of data with multiple directions and higherorder derivative information. Hence, we consider several other transformations by taking advantage of multiple directions and higher-order derivatives.

Specifically, we examine four common convolution kernels: the first-order central difference operator, the Sobel operator, and two types of Laplacian operators. Their forms and edge extraction effects on the "Barbara" image are shown in Figure 2. It can be observed that compared to the central difference operator, the latter three operators capture more abundant local information about the image.

Next, we give an intuitive mathematical explanation of the superior local correlation excavation abilities of the Sobel and Laplacian operators by Remark 3.

Remark 3. For an image, it can be modeled as a bivariate function z = f(x, y), where x, y represent the coordinates, and z represents the grayscale value. The first-order difference of f(x, y) is:

The second-order difference of f(x, y) can be represented in the x and y directions as follows:

The first-order difference operator ∂f ∂x / ∂f ∂y corresponds to the convolution kernel [-1,1]/[-1;1]. The Sobel operator ∂f ∂x + ∂f ∂y and Laplacian operator ∂ 2 f ∂x2 + ∂ 2 f ∂y2 have effects equivalent to [-2,-1;-1,0] and [0,-1,0;-1,4,-1;0,-1,0], respectively. The first derivative detects edges, while the second derivative detects the rate of change of edges. Derivatives in multiple directions can comprehensively characterize edge information. Therefore, the Sobel operator and the two types of Laplacian operators provided in Figure 2 can exploit richer local priors.

3 Simulated Experiment

The numerical experiments are conducted to validate Theorems 1 and 2. As described in Section 2.4, we use difference, Sobel, and Laplacian operators in MNN, denoted as MNNDiff, MNN-Sobel, MNN-L1, and MNN-L2 in Figure 2. Note that MNN-Diff reduces to the CTV regularizer. Following Corollary 2.3, we set λ = 1/√max{n1, n2} for the TRPCA task and µ = (√n1 + √n2)√pσ, σ = 1e-4 for the MC noiseless task. Further performance gains can be achieved by fine-tuning λ and µ. All simulations are run on a PC with an Intel Core i5-10600KF CPU (4.10 GHz), 32 GB RAM, and a GeForce RTX 3080 GPU.

3.1 Data Generation

We create two factor matrices U ∈ Rn1×r and V ∈ Rr×n2 , yielding X0 = UVT as a low-rank matrix, where n1 = hw. To introduce image-like properties, each column of U (i.e., U(:, i)) is reshaped into an h × w matrix, thus we can get the tensor U ∈ Rh×w×r satisfies U = unfold3(U) where unfold3(·) is the unfold operator to unfold the tensor to matrix along the third-mode. Each slice U(:, :, i) is randomly divided into c regions, with elements within each region being consistent and drawn from N(0, 1) distribution. The elements of V are selected from N(0, 1) distribution. The entire generation process is shown in Figure 3. Besides, the support set Ω is NN

MNN-Diff

MNN-Sobel

MNN-L1

MNN-L2

00 600 700 800 900 1000

tion chosen randomly. For RPCA task, S0 is set as S0 = PΩ(E) and the observed matrix M is set as M = X0 + S0, where E is a matrix with independent Bernoulli ±1 entries. For MC task, M is set as M = PΩ(X0).

3.2 Experiment Settings and Result Analysis

Experiment Settings. In all experiments, we set h = w = 50, n1 = hw = 2500, and n2 = 100. We evaluate how the rank r, sparsity ρs (RPCA), and missing ratio ρ (MC) affect performance by varying ρs in (0.01, 0.5) (step 0.01), ρ in (0.01, 0.99) (step 0.02), and r in (1, 50) (step 1).

Phase Transition Diagram. For each (r, ρs) and (r, ρ), we run 10 trials and consider recovery successful if ∥ ˆX -

1

0.8

0.6

0.4

0.2

0

4

2 Table 1: Comparison of methods for fusing global and local priors.

0

0 100 200 300 400 500 600 700 800 900 1000

0 100 200 300 400 500 600 700 800 900 1000

Iteration Iteration (b) MC Task X0∥F/∥X0∥F ≤ 0.05. Figure 4 shows the phase diagrams with recovery rates. Compared to NN, MNN variants (Diff, Sobel, L1, L2) significantly expand the recovery region by leveraging local structures. Notably, MNN-Sobel, MNN-L1, and MNN-L2 outperform MNN-Diff, highlighting the advantage of high-order operators as noted in Remark 3.

Empirical analysis of convergence. According to Corollary 2.3, the objectives of models (7) and (8) reach their minima at X0 and S0 under Assumptions 1-3. Even when the assumptions are only partially met, the objective values still decrease, and NMSE sequence ∥Xk-X0∥F /∥X0∥F steadily declines. Figure 5 shows that under a learning rate of 1e-4 , NN and all MNN variants converge stably.

4 Real Application

We then assess the restoration performance on real datasets.

Datasets. We selected four commonly used low-rank image datasets, which are HSI data used in [Wang et al., 2023], MSI 2 , color video sequences 3 , and MRI and CT images 4 . Among them, hyperspectral images, multispectral images, color video sequences, and MRI and CT images contain 5, 11, 10, and 4 images, respectively. We adopt the same noise addition mechanism and sampling scheme as in the simulation experiments section.

2 https://www.cs.columbia.edu/CAVE/databases/multispectral/

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

4 https://www.cancerimagingarchive.net/

Objective Function Comparison methods. To validate the effectiveness of MNN in fusing global and local priors, we selected methods such as LRTV [He et al., 2015], LRTDTV [Wang et al., 2017], CTV [Peng et al., 2022b], Qrank [], KBR [Xie et al., 2017], TCTV [Wang et al., 2023], SNN [Liu et al., 2012], Qrank [Kong et al., 2021], TNN [Lu et al., 2019] and Framlet [Jiang et al., 2020]. It is worth noting that CTV can actually be regarded as a special case of MNN since it utilizes multiple differential operators from different methods and employs the ADMM [Boyd et al., 2011] algorithm to solve the model. To facilitate readers' understanding of these comparison methods, the description of these methods are placed in Table 1.

4.1 Robust Principal Component Analysis Tasks

We evaluate denoising performance on HSI, MSI, and RGB video data with salt-and-pepper noise levels ranging from 10% to 70%, using PSNR and SSIM as metrics. Table 2 summarizes the average results. The following observations can be observed: 1) In most cases, the MNN-Sobel model achieves the best performance; 2) Models such as MNNSobel, MNN-L1, and MNN-L2 generally outperform MNNDiff, partially supporting Remark 3, which suggests that expanding the receptive field of convolutional operators enhances performance; 3) In some scenarios, MNN-L1 and MNN-L2 outperform MNN-Sobel, indicating that different transformation operators are required for different types of data and noise. If suitable transformation operators can be adaptively selected, further improvements in restoration performance are achievable.

Figure 6 shows restored pseudo-color images for two datasets, where MNN-Sobel and MNN-L2 visibly enhance noise reduction and color fidelity. More results are provided in the supplementary materials.

4.2 Completion Tasks

We conduct completion experiments on four datasets using random sampling. Table 3 reports the average restoration metrics, leading to the same three conclusions as in the denoising results (Table 2 ). Notably, despite being matrixbased, MNN consistently outperforms tensor-based methods like TNN, TCTV, and KBR, demonstrating its ability to effectively capture both global and local features.

Figure 7 shows visual results on two datasets, where MNNbased models excel in structure preservation, color fidelity, and overall restoration. Additional results are provided in the supplementary materials.

5 Conclusion

This paper proposes a modified nuclear norm (MNN) regularizer that integrates global low-rankness and local priors via transformation operators. Under mild and general theoretical conditions, MNN accommodates a broad range of transformations, enabling flexible and effective fusion of local and global information within a unified framework.

Acknowledgments

This work was in part by the National Key R& D Program of China (2020YFA0713900), the National Natural Science Foundation of China under Grant 12401674, 62272375 and 12201497, Tianyuan Fund for Mathematics of the National Natural Science Foundation of China (Grant No. 12426105), the Major Key Project of Pengcheng Laboratory under Grant PCL2024A06, the Guangdong Basic and Applied Basic Research Foundation under Grant 2025A1515011453, the Fundamental Research Funds for the Central Universities under Grant D5000240095, and the Key Research, Development Plan of Shaanxi Province, China (No. 2024GX-YBXM-145).