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.
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