Analyzing the group sparsity based on the rank minimization methods

Zhiyuan Zha, Xin Liu, Xiaohua Huang, Xiaopeng Hong, Henglin Shi, Yingyue Xu, Qiong Wang, Lan Tang, Xinggan Zhang

Abstract

Sparse coding has achieved a great success in various image processing studies. However, there is not any benchmark to measure the sparsity of image patch/group because sparse discriminant conditions cannot keep unchanged. This paper analyzes the sparsity of group based on the strategy of the rank minimization. Firstly, an adaptive dictionary for each group is designed. Then, we prove that group-based sparse coding is equivalent to the rank minimization problem, and thus the sparse coefficient of each group is measured by estimating the singular values of each group. Based on that measurement, the weighted Schatten $p$-norm minimization (WSNM) has been found to be the closest solution to the real singular values of each group. Thus, WSNM can be equivalently transformed into a non-convex $\ell_p$-norm minimization problem in group-based sparse coding. To make the proposed scheme tractable and robust, the alternating direction method of multipliers (ADMM) is used to solve the $\ell_p$-norm minimization problem. Experimental results on two applications: image inpainting and image compressive sensing (CS) recovery have shown that the proposed scheme outperforms many state-of-the-art methods.

Introduction

In image restoration tasks such as inpainting or compressive sensing recovery, sparse coding is a highly effective technique. It assumes that image patches can be represented as sparse linear combinations of elements from a dictionary. Recently, group-based sparse coding—which groups similar patches to exploit non-local self-similarity—has gained popularity.

However, a fundamental challenge persists: the lack of a reliable benchmark to measure the true sparsity of an image group. Because mathematical conditions for sparse solutions change with image content, researchers often rely on approximations like the $\ell_1$-norm without knowing if they are truly optimal. This paper addresses this gap by bridging group-based sparse coding with rank minimization.

Methodology: Bridging Sparse Coding and Rank Minimization

The core innovation of this work is establishing a mathematical equivalence between two previously distinct fields: sparse coding and rank minimization.

Adaptive Dictionary and Mathematical Equivalence

Instead of using a static global dictionary, the authors design an adaptive dictionary for each patch group using Singular Value Decomposition (SVD). They formally prove that under this specific dictionary, group-based sparse coding is perfectly equivalent to the rank minimization problem. This allows the singular values of an image group to serve as a direct, computable benchmark for its sparsity.

Optimization via WSNM and ADMM

By evaluating different norms against this new benchmark, the authors found that the Weighted Schatten p-norm Minimization (WSNM) provides the closest approximation to the ground truth singular values.

Figure 1: (a) Original image, (b) image with 80% missing pixels, and (c, d) comparison of various minimization methods (NNM, WNNM, SNM) against WSNM and ground truth singular values.

The restoration task is formulated as a non-convex $\ell_p$-norm minimization problem. To solve this robustly, the authors utilize the Alternating Direction Method of Multipliers (ADMM) combined with Generalized Soft-Thresholding (GST).

Experimental Results

The proposed method was evaluated using a standard collection of 10 classic test images (e.g., Barbara, Mickey) across two key applications.

Image Inpainting

The method was tested on images with 80% missing pixels and those corrupted by inlayed text. It consistently outperformed state-of-the-art methods such as BPFA and IPPO. For text-inlayed images, the proposed scheme achieved an average PSNR of 33.58 dB (compared to IPPO's 32.90 dB), successfully reconstructing sharp edges and eliminating ringing artifacts.

Compressive Sensing (CS) Recovery

Tested at measurement ratios of 0.1N, 0.2N, and 0.3N, the method outperformed BM3D, ADS, SGSR, and MRK. At a high compression ratio of 0.1N, it achieved 28.89 dB, beating the BM3D baseline by over 4.6 dB and the next best method (SGSR) by nearly 1 dB.

Discussion and Conclusion

By unifying group sparse coding and rank minimization, this research provides a reliable proxy for true sparsity via singular values. This approach bypasses the NP-hard nature of $\ell_0$ minimization and yields superior restoration quality.

Future work may address current limitations, such as the need for manual hyperparameter tuning (e.g., the power $p$ and ADMM penalty $\rho$) and the computational intensity of performing SVDs across thousands of patch groups. Potential improvements include automated parameter learning or algorithmic acceleration for high-resolution images.

Summary updated

Abstract

Sparse coding has achieved a great success in various image processing studies. However, there is not any benchmark to measure the sparsity of image patch/group because sparse discriminant conditions cannot keep unchanged. This paper analyzes the sparsity of group based on the strategy of the rank minimization. Firstly, an adaptive dictionary for each group is designed. Then, we prove that group-based sparse coding is equivalent to the rank minimization problem, and thus the sparse coefficient of each group is measured by estimating the singular values of each group. Based on that measurement, the weighted Schatten $p$-norm minimization (WSNM) has been found to be the closest solution to the real singular values of each group. Thus, WSNM can be equivalently transformed into a non-convex $\ell_p$-norm minimization problem in group-based sparse coding. To make the proposed scheme tractable and robust, the alternating direction method of multipliers (ADMM) is used to solve the $\ell_p$-norm minimization problem. Experimental results on two applications: image inpainting and image compressive sensing (CS) recovery have shown that the proposed scheme outperforms many state-of-the-art methods.
BibTeX
@inproceedings{zha2017analyzing,
  author = {Zhiyuan Zha and Xin Liu and Xiaohua Huang and Xiaopeng Hong and Henglin Shi and Yingyue Xu and Qiong Wang and Lan Tang and Xinggan Zhang},
  title = {{Analyzing the group sparsity based on the rank minimization methods}},
  booktitle = {ICME},
  year = {2017},
  doi = {10.1109/icme.2017.8019334},
}
Figure