Analyzing the Weighted Nuclear Norm Minimization and Nuclear Norm Minimization based on Group Sparse Representation

Zhiyuan Zha, Xinggan Zhang, Qiong Wang, Yechao Bai, Lan TangarXiv 2017 · OpenReview

Introduction

Image restoration often relies on the assumption that natural images contain redundant structures. Two prominent frameworks have emerged to exploit this redundancy: Rank Minimization, which treats similar image patches as low-rank matrices, and Group Sparse Representation (GSR), which represents groups of patches as sparse combinations of dictionary elements. While both have been successful, they were largely treated as separate approaches. This research, published in IEEE Transactions on Image Processing, bridges this gap, demonstrating that they are mathematically equivalent under specific conditions.

The Problem with Standard Nuclear Norm Minimization

In Rank Minimization, Nuclear Norm Minimization (NNM) is commonly used to "clean" noisy images by shrinking the singular values of a patch matrix. However, standard NNM has a significant drawback: it treats all singular values equally. In a natural image, large singular values typically correspond to major structural components like edges and textures, whereas small singular values often represent noise. By applying a uniform shrinkage, NNM tends to "over-shrink" the important structural information, resulting in blurred edges and loss of fine detail.

Weighted NNM (WNNM) was introduced as a heuristic solution to this problem, assigning smaller weights to larger singular values to preserve structure. While empirically successful, it lacked a rigorous mathematical justification until now. This paper seeks to explain why WNNM outperforms NNM and how to make the weighting process more robust.

Methodology

The authors' primary contribution is a formal proof of equivalence between WNNM and weighted GSR. Their approach involves three key components:

  1. Adaptive Dictionary Learning: Instead of relying on generic fixed dictionaries like Wavelets or DCT, the method groups similar patches and performs Singular Value Decomposition (SVD) on each group. This process generates an adaptive dictionary tailored to the specific local content of the image.
  2. The Equivalence Proof: The core of the paper proves that solving an NNM problem is mathematically identical to solving an $\ell_1$-norm sparsity problem using this adaptive dictionary. Crucially, they show that WNNM is equivalent to a weighted $\ell_1$-norm sparsity problem. This unifies "low-rankness" and "sparsity" as two sides of the same coin.
Comparison of different sparsity-promoting functions, illustrating the behavior of $L_1$, $L_0$, and logarithmic norms.
  1. Adaptive Weighting Scheme: To improve stability over previous heuristic methods, the authors propose a new adaptive weight formula: $$w_i = \frac{c \cdot 2\sqrt{2}\sigma_n^2}{\gamma_i + \epsilon}$$ where $\sigma_n^2$ represents the noise variance and $\gamma_i$ is the estimated variance of the singular values. This formulation avoids common errors during SVD and provides a more robust weighting mechanism.

Experimental Evaluation

The proposed GSR-WNNM scheme was evaluated on 14 standard benchmark images, including classic examples like Lena, Barbara, House, and Starfish. The evaluation covered two primary tasks:

  • Image Denoising: Images were corrupted with additive white Gaussian noise at levels ranging from $\sigma_n = 20$ to $100$.
  • Image Inpainting: Random pixel masking was applied, with 50% to 80% of pixels missing.

Key Results and Discussion

Quantitative analysis showed that GSR-WNNM consistently outperformed state-of-the-art methods such as BM3D and NCSR. On average, it achieved a PSNR gain of 0.32dB over BM3D and up to 1.50dB over standard NNM-based approaches.

Qualitatively, the method excels at preserving sharpness and fine textures. Unlike BM3D, which can over-smooth details, or other sparse coding methods that may introduce ringing artifacts, GSR-WNNM maintains the integrity of complex patterns. For example, it preserves the fine textures of a starfish or the weave in a shawl even under high noise levels.

Qualitative comparison of image restoration on the Starfish benchmark, demonstrating the superior detail preservation of the proposed method (j) compared to noisy input (b) and other techniques.

In the challenging task of inpainting with 80% missing data, the algorithm successfully recovered sharp edges and intricate details that competing methods left distorted or blurry.

Conclusion

By unifying Rank Minimization and Group Sparse Representation, this work provides a deep theoretical understanding of image priors. The proof that WNNM is a form of weighted sparsity explains its superior performance and enables more principled algorithm design. While computationally intensive due to iterative SVDs, the method sets a new standard for image restoration quality. Future research may focus on optimizing efficiency and extending the framework to handle non-Gaussian noise and other degradation models.

Summary updated

Abstract

Rank minimization methods have attracted considerable interest in various areas, such as computer vision and machine learning. The most representative work is nuclear norm minimization (NNM), which can recover the matrix rank exactly under some restricted and theoretical guarantee conditions. However, for many real applications, NNM is not able to approximate the matrix rank accurately, since it often tends to over-shrink the rank components. To rectify the weakness of NNM, recent advances have shown that weighted nuclear norm minimization (WNNM) can achieve a better matrix rank approximation than NNM, which heuristically set the weight being inverse to the singular values. However, it still lacks a sound mathematical explanation on why WNNM is more feasible than NNM. In this paper, we propose a scheme to analyze WNNM and NNM from the perspective of the group sparse representation. Specifically, we design an adaptive dictionary to bridge the gap between the group sparse representation and the rank minimization models. Based on this scheme, we provide a mathematical derivation to explain why WNNM is more feasible than NNM. Moreover, due to the heuristical set of the weight, WNNM sometimes pops out error in the operation of SVD, and thus we present an adaptive weight setting scheme to avoid this error. We then employ the proposed scheme on two low-level vision tasks including image denoising and image inpainting. Experimental results demonstrate that WNNM is more feasible than NNM and the proposed scheme outperforms many current state-of-the-art methods.
BibTeX
@misc{zha2017analyzing,
  author = {Zhiyuan Zha and Xinggan Zhang and Qiong Wang and Yechao Bai and Lan Tang},
  title = {{Analyzing the Weighted Nuclear Norm Minimization and Nuclear Norm Minimization based on Group Sparse Representation}},
  year = {2017},
  eprint = {1702.04463},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1702.04463},
}
Figure