# Bridge the Gap Between Group Sparse Coding and Rank Minimization via
Adaptive Dictionary Learning

Zhiyuan Zha, Xin Yuan, Senior Member, IEEE Z. Zha is with the department of
Electronic Science and Engineering, Nanjing University, Nanjing 210023, China.
E-mail<EMAIL_ADDRESS>Yuan is with Nokia Bell Labs, 600 Mountain
Avenue, Murray Hill, NJ, 07974, USA. E-mail<EMAIL_ADDRESS>
###### Abstract

Both sparse coding and rank minimization have led to great successes in
various image processing tasks. Though the underlying principles of these two
approaches are similar, no theory is available to demonstrate the
correspondence. In this paper, starting by designing an adaptive dictionary
for each group of image patches, we analyze the sparsity of image patches in
each group using the rank minimization approach. Based on this, we prove that
the group-based sparse coding is equivalent to the rank minimization problem
under our proposed adaptive dictionary. Therefore, the sparsity of the
coefficients for each group can be measured by estimating the singular values
of this group. Inspired by our theoretical analysis, four nuclear norm like
minimization methods including the standard nuclear norm minimization (NNM),
weighted nuclear norm minimization (WNNM), Schatten $p$-norm minimization
(SNM), and weighted Schatten $p$-norm minimization (WSNM), are employed to
analyze the sparsity of the coefficients and WSNM is found to be the closest
solution to the singular values of each group. Based on this, WSNM is then
translated to a non-convex weighted $\ell_{p}$-norm minimization problem in
group-based sparse coding, and in order to solve this problem, a new algorithm
based on the alternating direction method of multipliers (ADMM) framework is
developed. Experimental results on two low-level vision tasks: image
inpainting and image compressive sensing recovery, demonstrate that the
proposed scheme is feasible and outperforms state-of-the-art methods.

###### Index Terms:

Group sparsity, sparse coding, rank minimization, nuclear norm minimization,
dictionary learning, alternating direction method of multipliers (ADMM), image
processing, compressive sensing, image restoration.

##  1 Introduction

Traditional patch-based sparse coding has been widely used in image processing
tasks and has achieved excellent results [1, 2, 3, 4, 5, 6]. It assumes that
each patch of an image can be precisely modeled by a sparse linear combination
of some fixed and trainable basis elements, which are therefore called atoms
and these atoms compose a dictionary. As such, one key issue in sparse coding
based scheme is to train a dictionary, with popular techniques including K-SVD
[1], ODL [5] and SDL [6]. Compared with the conventional analytically designed
basis, such as DCT [7] and wavelet [8], dictionaries learned from images enjoy
advantages of being better adapted to image local structures, and thus could
improve the sparsity performance. For instance, the seminal work of K-SVD
dictionary learning method [1] has not only demonstrated promising denoising
performance, but also been extended to other image processing and computer
vision tasks [9, 10, 11]. Another parallel research is using the rank
minimization models for image processing [33, 24, 61], which has also achieved
excellent results. Though intuitively, the rank minimization and sparse coding
share the similar spirit, there is no theoretical analysis of the
correspondence. This research gap is filled by our paper via developing an
adaptive dictionary learning approach using group-based sparse coding.

Two main issues exist in the patch-based sparse coding model. Firstly, since
dictionary learning is a large-scale and highly non-convex problem, it is
computationally expensive. Secondly, the patch-based sparse coding model
usually assumes the independence of image patches, which doesn’t take account
of the correlation among similar patches. Instead of using single patch as the
basic unit in sparse coding, recent advances of group-based sparse coding
(GSC)111This group-based sparse coding is different from the block-sparse
signal [56], where all items in one block are zeros or non-zeros. have
demonstrated great potentials in various image processing tasks [12, 13, 14,
15]. The GSC is a powerful mechanism to integrate local sparsity and nonlocal
similarity of image patches. Taking a gray-scale image
$\textbf{\emph{X}}\in{\mathbb{R}}^{\sqrt{N}\times\sqrt{N}}$ as an example, it
is divided into $n$ overlapping patches of size $\sqrt{d}\times\sqrt{d}$, and
each patch is denoted by a vector
${\textbf{\emph{x}}}_{i}\in\mathbb{R}^{d},i=1,2,...,n$. Then for each patch
${\textbf{\emph{x}}}_{i}$, its $m$ similar patches are selected from a
searching window with $C\times C$ pixels to form a set ${\cal S}_{i}$.
Following this, all patches in ${\cal S}_{i}$ are stacked into a matrix
${\textbf{\emph{X}}}_{i}\in\mathbb{R}^{d\times m}$, i.e.,

${\textbf{\emph{X}}}_{i}=\\{{\textbf{\emph{x}}}_{i,1},{\textbf{\emph{x}}}_{i,2},...,{\textbf{\emph{x}}}_{i,m}\\}.$
(1)

This matrix, ${\textbf{\emph{X}}}_{i}$, consisting of patches with similar
structures is thereby called a group, where
$\\{{\textbf{\emph{x}}}_{i,j}\\}_{j=1}^{m}$ denotes the $j$-th patch in the
$i$-th group. Similar to patch-based sparse coding [1, 2], given a dictionary
${\textbf{\emph{D}}}_{i}$, each group ${\textbf{\emph{X}}}_{i}$ can be
sparsely represented by solving the following minimization problem,

$\hat{\textbf{\emph{A}}}_{i}=\arg\min_{{\textbf{\emph{A}}}_{i}}\left(\frac{1}{2}||{\textbf{\emph{X}}}_{i}-{\textbf{\emph{D}}}_{i}{\textbf{\emph{A}}}_{i}||_{F}^{2}+\lambda||{\textbf{\emph{A}}}_{i}||_{0}\right),$
(2)

where $\lambda$ is the regularization parameter, $||~{}||_{F}^{2}$ denotes the
Frobenius norm, and $||~{}||_{0}$ signifies the $\ell_{0}$-norm222Though
$\ell_{0}$ is not a strict norm, we follow the terminology convention in the
literature., i.e., counting the nonzero entries in ${\textbf{\emph{A}}}_{i}$.

Since $\ell_{0}$-norm minimization is NP-hard, it is often replaced by the
$\ell_{1}$-norm or the weighted $\ell_{1}$-norm [16] to make the optimization
problem tractable. Nevertheless, the solution of these norm minimization
problems is only the estimation of the real sparsity solution under certain
conditions. For instance, Candès $\emph{et al}.$ [17] proved that solving
$\ell_{1}$-norm optimization problem can recover a $K$-sparse signal
$\textbf{\emph{x}}\in\mathbb{R}^{N}$ from $M=O(K\log(N/K))$ random
measurements in compressive sensing (CS). Unfortunately, in real applications,
one usually has no prior knowledge of the sparsity of the signal, and
therefore, it is difficult to evaluate the accuracy of the solution provided
by the $\ell_{1}$-norm minimization. Meanwhile, advanced minimization
problems, like the weighted $\ell_{1}$-norm [16] and weighted
$\ell_{1,2}$-norm [62], are also proposed to solve the $\ell_{0}$-norm
minimization problem. However, no matter which method is used, it is just an
estimate to the $\ell_{0}$-norm. Therefore, a benchmark is desired to evaluate
the sparsity of the signal/image.

Bearing the above concern in mind, in this paper, we analyze the group
sparsity (a.k.a. $\ell_{0}$-norm) from the perspective of rank minimization.
To the best of our knowledge, limited work has utilized the rank minimization
method to analyze the sparsity of image patch groups. The contributions of
this paper are threefold: $i$) An adaptive dictionary for each patch group is
designed with low computational complexity. $ii$) Based on this dictionary
learning scheme, we prove the equivalence of group-based sparse coding and the
rank minimization problem (Fig. 1), and thus the sparse coefficients of each
group can be measured by calculating the singular values of this group.
Following this, we have a benchmark to evaluate the sparsity of each group.
$iii$) We exploit four nuclear norm minimization methods, namely, the standard
nuclear norm minimization (NNM) [18], weighted nuclear norm minimization
(WNNM) [19], Schatten $p$-norm minimization (SNM) [20], and weighted Schatten
$p$-norm (WSNM) [21], to analyze the sparsity of each group and the solution
of WSNM is the closest to real singular values of each group. Therefore, WSNM
is equivalently translated into a non-convex weighted $\ell_{p}$-norm
minimization problem in group-based sparse coding. We develop algorithms to
solve this weighted $\ell_{p}$-norm minimization problem and apply them on two
low-level vision studies, namely image inpainting and image CS recovery.
Experimental results demonstrate that the proposed scheme is feasible and
outperforms state-of-the-art methods.

The rest of this paper is organized as follows. Section 2 briefly introduces
the rank minimization method and some nuclear norms. Section 3 proposes the
adaptive dictionary learning approach and analyses the sparsity of each group
from the perspective of rank minimization. Section 4 develops an efficient
algorithm to solve the proposed weighted $\ell_{p}$-norm minimization problem
based on the alternating direction method of multipliers (ADMM) framework.
Section 5 presents experimental results. Section 6 concludes the paper. The
preliminary work has appeared in [22]333Significant changes have been made
compared to our previous work in [22]. Specifically, we have added the
analysis of group sparsity using the nuclear norm minimization in Sec. 3.3;
gradient descent algorithm is introduced in Sec. 4.1.1 to solve the CS
inversion problem; the generalized soft-thresholding algorithm is reviewed in
Sec. 4.2. Moreover, extensive experiments have been added to verify the
feasibility, robustness, and convergence of the proposed algorithm in Sec. 5.
In addition, we have compared the proposed ADMM solver with the iterative
shrinkage thresholding solver in Sec. 5.5..

Figure 1: Correspondence between group-based sparse coding and rank
minimization via the proposed adaptive dictionary learning approach, where
$||\textbf{\emph{X}}||_{*}$ and $||\textbf{\emph{X}}||_{1}$ represent nuclear
norm and $\ell_{1}$-norm, respectively; $||\textbf{\emph{X}}||_{S_{p}}$ and
$||\textbf{\emph{X}}||_{p}$ represent Schatten $p$-norm and $\ell_{p}$-norm,
respectively; $||\textbf{\emph{X}}||_{w,*}$ and
$||\textbf{\emph{W}}\textbf{\emph{X}}||_{1}$ represent the weighted nuclear
norm and weighted $\ell_{1}$-norm, respectively;
$||\textbf{\emph{X}}||_{w,S_{p}}$ and
$||\textbf{\emph{W}}\textbf{\emph{X}}||_{p}$ represent the weighted Schatten
$p$-norm and weighted $\ell_{p}$-norm, respectively.

##  2 Background and Related Work

###  2.1 Rank Minimization

The main goal of low rank matrix approximation (LRMA) is to recover the
underlying low rank structure of a matrix from its degraded/corrupted
observation. In general, methods of LRMA can be classified into two
categories: the low rank matrix factorization (LRMF) methods [23, 24, 25, 26,
27] and the rank minimization methods [18, 19, 20, 21]. Given an input matrix
Y, the goal of LRMF is to factorize it into the product of two low rank
matrices that can be used to reconstruct Y with certain fidelity. A flurry of
LRMF have been proposed, such as the classical SVD under $\ell_{2}$-norm [23],
robust LRMF methods under $\ell_{1}$-norm [24, 25], and other probabilistic
methods [26, 27].

In this work we focus on the rank minimization problem. To be concrete, for an
input matrix Y, the rank minimization approach aims to find a low rank matrix
X, which is as close to Y as possible under $F$-norm data fidelity with a
nuclear norm constraint,

$\hat{\textbf{\emph{X}}}=\arg\min_{\textbf{\emph{X}}}\left(\frac{1}{2}||{\textbf{\emph{Y}}}-{\textbf{\emph{X}}}||_{F}^{2}+\lambda\textbf{\emph{R}}({\textbf{\emph{X}}})\right),$
(3)

where $\lambda$ is a parameter to balance the loss function and the low rank
regularization induced by the nuclear norm
$\textbf{\emph{R}}(\textbf{\emph{X}})$, which will be introduced in detail
below.

Figure 2: Analysing the sparsity of each group based nuclear norms
minimization in terms of image inpainting. (a) Original Lena image, (b) 80%
pixels are missing, (c-d) the singular values using different norms of the
patch group with reference in the cyan (1#) and orange (2#) boxes,
respectively. Figure 3: Analyzing the sparsity of each group based nuclear
norms minimization in terms of image CS recovery. The image _boats_ (a) is
compressively sampled by a random Gaussian matrix with 0.2$N$ measurements and
an initial image (b) is estimated by using the DCT based CS image recovery
method. (c-d) The singular values using different norms of the patch group
with reference in the cyan (3#) and orange (4#) boxes, respectively.

###  2.2 Nuclear Norms

Hereby, we briefly introduce several nuclear norms, including the standard
nuclear norm [18], the weighted nuclear norm [19], Schatten $p$-norm [20] and
the weighted Schatten $p$-norm [21]. The weighted Schatten $p$-norm is
described first as other three nuclear norms can be viewed as special cases of
it.

######  Definition 1.

The weighted Schatten $p$-norm [21] of a matrix,
$\textbf{\emph{X}}\in\mathbb{R}^{m\times n}$, is

$||\textbf{\emph{X}}||_{\textbf{\emph{w}},S_{p}}=\left(\sum\nolimits_{i=1}^{min\\{m,n\\}}w_{i}\sigma_{i}^{p}\right)^{\frac{1}{p}},$
(4)

where $0<p\leq 1$, and $\sigma_{i}$ is the $i$-th singular value of X.
$\textbf{\emph{w}}=[w_{1},...,w_{min\\{m,n\\}}]$, and $w_{i}\geq 0$ is a
weight assigned to $\sigma_{i}$.

######  Definition 2.

The weighted Schatten $p$-norm of X with power $p$ is

$||\textbf{\emph{X}}||_{\textbf{\emph{w}},S_{p}}^{p}=\sum\nolimits_{i=1}^{min\\{m,n\\}}w_{i}\sigma_{i}^{p}={\rm
Tr}(\textbf{\emph{W}}{\boldsymbol{\Delta}}^{p}),$ (5)

where W and ${\boldsymbol{\Delta}}$ are diagonal matrices whose diagonal
entries are composed of $w_{i}$ and $\sigma_{i}$, respectively; ${\rm
Tr}(~{})$ calculates the trace of the matrix in $(~{})$.

######  Definition 3.

The Schatten $p$-norm [20] of a matrix X can be represented by setting
$\textbf{\emph{w}}=[1,1,...,1]$ in Eq. (4),

$||\textbf{\emph{X}}||_{S_{p}}=\left(\sum\nolimits_{i=1}^{min\\{m,n\\}}\sigma_{i}^{p}\right)^{\frac{1}{p}}=\left({\rm
Tr}(({\textbf{\emph{X}}}^{T}{\textbf{\emph{X}}})^{\frac{p}{2}})\right)^{\frac{1}{p}}.$
(6)

######  Definition 4.

The weighted nuclear norm [19] of a matrix X can be represented by setting
$p$=1 in Eq. (4),

$||\textbf{\emph{X}}||_{\textbf{\emph{w},*}}=\left(\sum\nolimits_{i=1}^{min\\{m,n\\}}w_{i}\sigma_{i}\right)={\rm
Tr}(\textbf{\emph{W}}{\boldsymbol{\Delta}}).$ (7)

######  Definition 5.

A widely used standard nuclear norm [18] of a matrix X can be represented by
setting $p$=1 and $\textbf{\emph{w}}=[1,1,...,1]$ in Eq. (4),

$||\textbf{\emph{X}}||_{*}=\sum\nolimits_{i=1}^{min\\{m,n\\}}\sigma_{i}={\rm
Tr}(({\textbf{\emph{X}}}^{T}{\textbf{\emph{X}}})^{\frac{1}{2}}).$ (8)

##  3 Analysing the Sparsity of Group based on the Rank Minimization

In this section, we analyze the group sparsity from the point of view of rank
minimization. Towards this end, an adaptive dictionary for each group is
designed in a low computational complexity manner. Based on this dictionary
learning scheme, we prove that group-based sparse coding is equivalent to the
rank minimization problem, i.e., the sparsity of coefficients in each group is
measured by calculating the singular values of each group. Following this, we
have a benchmark to measure the sparsity of each group via the rank
minimization method. Further, the singular values of the original image patch
group can be easily obtained. We have thus achieved a visual comparison to
analyze the sparsity of each group; please refer to Figs. 2-3 for a
demonstration.

###  3.1 Adaptive dictionary learning

An adaptive dictionary learning method is now proposed, that is, for each
group ${\textbf{\emph{X}}}_{i}$, its adaptive dictionary can be learned from
its observation ${\textbf{\emph{Y}}}_{i}\in\mathbb{R}^{d\times m}$.
Specifically, we apply the SVD to ${\textbf{\emph{Y}}}_{i}$,

${\textbf{\emph{Y}}}_{i}={\textbf{\emph{U}}}_{i}{\boldsymbol{\Sigma}}_{i}{\textbf{\emph{V}}}_{i}^{T}=\sum\nolimits_{j=1}^{n_{1}}\sigma_{i,j}{\textbf{\emph{u}}}_{i,j}{\textbf{\emph{v}}}_{i,j}^{T},$
(9)

where ${\boldsymbol{\Sigma}}_{i}={\rm
diag}(\sigma_{i,1},\sigma_{i,2},...,\sigma_{i,{n_{1}}})$ is a diagonal matrix,
${n_{1}}={\rm min}(d,m)$, and
${\textbf{\emph{u}}}_{i,j},{\textbf{\emph{v}}}_{i,j}$ are the columns of
${\textbf{\emph{U}}}_{i}$ and ${\textbf{\emph{V}}}_{i}$, respectively.

Following this, we define each dictionary atom $\textbf{\emph{d}}_{i,j}$ of
the adaptive dictionary $\textbf{\emph{D}}_{i}$ for each group
$\textbf{\emph{Y}}_{i}$ by:

$\textbf{\emph{d}}_{i,j}={\textbf{\emph{u}}}_{i,j}{\textbf{\emph{v}}}_{i,j}^{T},\
\ \ j=1,2,...,{n_{1}}.$ (10)

Till now, we have learned an adaptive dictionary

$\textbf{\emph{D}}_{i}=[\textbf{\emph{d}}_{i,1},\textbf{\emph{d}}_{i,2},...,\textbf{\emph{d}}_{i,{n_{1}}}]$
(11)

from each group ${\textbf{\emph{Y}}}_{i}$. It can be seen that the proposed
dictionary learning method is efficient since it only requires one SVD
operation per group. The global dictionary D can be obtained by concatenating
these group dictionaries, as shown in Fig. 1.

###  3.2 Prove the equivalence of Group-based Sparse Coding and Rank
Minimization

In order to prove that the group-based sparse coding is equivalent to the rank
minimization problem, we firstly give two lemmas.

######  Lemma 1.

The minimization problem

$\hat{\textbf{\emph{x}}}=\arg\min_{\textbf{\emph{x}}}\left(\frac{1}{2}||{\textbf{\emph{x}}}-{\textbf{\emph{a}}}||_{2}^{2}+\tau||{\textbf{\emph{x}}}||_{1}\right)$
(12)

has a closed-form solution

$\hat{\textbf{\emph{x}}}={\rm soft}({\textbf{\emph{a}}},\tau)={\rm
sgn}({\textbf{\emph{a}}})\odot{\rm max}({\rm
abs}({\textbf{\emph{a}}})-\tau,0),$ (13)

where $\odot$ denotes the element-wise (Hadamard) product.

###### Proof.

See [28]. ∎

Consider the SVD of a matrix $\textbf{\emph{X}}\in\mathbb{R}^{d\times m}$ with
rank $r$

$\textbf{\emph{X}}=\textbf{\emph{U}}\boldsymbol{\Sigma}\textbf{\emph{V}}^{T},\quad\boldsymbol{\Sigma}={\rm
diag}(\\{\sigma_{i}\\}_{1\leq i\leq r})$ (14)

where $\textbf{\emph{U}}\in\mathbb{R}^{d\times r}$ and
$\textbf{\emph{V}}\in\mathbb{R}^{m\times r}$ are orthogonal matrices;
$\sigma_{i}$ is the $i$-th singular value of X. For any $\tau\geq 0$, the
soft-thresholding operator $\mathcal{D}_{\tau}$ is defined as

$\mathcal{D}_{\tau}(\textbf{\emph{X}})=\textbf{\emph{U}}\mathcal{D}_{\tau}(\boldsymbol{\Sigma})\textbf{\emph{V}}^{T},\quad\mathcal{D}_{\tau}(\boldsymbol{\Sigma})={\rm
soft}(\sigma_{i},\tau).$ (15)

Then, we have the following Lemma.

######  Lemma 2.

For any $\tau\geq 0$, and $\textbf{\emph{Y}}\in\mathbb{R}^{d\times m}$, the
singular value shrinkage operator in Eq. (15) satisfies

$\mathcal{D}_{\tau}(\textbf{\emph{Y}})=\arg\min_{\textbf{\emph{X}}}\left(\frac{1}{2}||{\textbf{\emph{Y}}}-{\textbf{\emph{X}}}||_{F}^{2}+\tau||{\textbf{\emph{X}}}||_{*}\right).$
(16)

###### Proof.

See [18]. ∎

Recalling the adaptive dictionary defined in Eq. (11), the classical
$\ell_{1}$-norm group-based sparse coding problem can be represented as

$\hat{\textbf{\emph{A}}}_{i}=\arg\min_{{\textbf{\emph{A}}}_{i}}\left(\frac{1}{2}||{\textbf{\emph{Y}}}_{i}-{\textbf{\emph{D}}}_{i}{\textbf{\emph{A}}}_{i}||_{F}^{2}+\lambda||{\textbf{\emph{A}}}_{i}||_{1}\right).$
(17)

According to the above design of the adaptive dictionary
${\textbf{\emph{D}}}_{i}$, we have the following theorem.

######  Theorem 1.

$||{\textbf{\emph{Y}}}_{i}-{\textbf{\emph{X}}}_{i}||_{F}^{2}=||{\textbf{\emph{B}}}_{i}-{\textbf{\emph{A}}}_{i}||_{F}^{2},$
(18)

where ${\textbf{\emph{Y}}}_{i}={\textbf{\emph{D}}}_{i}{\textbf{\emph{B}}}_{i}$
and ${\textbf{\emph{X}}}_{i}={\textbf{\emph{D}}}_{i}{\textbf{\emph{A}}}_{i}$.

###### Proof.

See Appendix A. ∎

Based on Lemmas 1-2 and Theorem 1, we have the following theorem.

######  Theorem 2.

The equivalence of group-based sparse coding and rank minimization is
satisfied under the adaptive dictionary ${\textbf{\emph{D}}}_{i}$, i.e.,

$\displaystyle\hat{\textbf{\emph{A}}}_{i}$
$\displaystyle=\arg\min\limits_{{\textbf{\emph{A}}}_{i}}\left(\frac{1}{2}||{\textbf{\emph{Y}}}_{i}-{\textbf{\emph{D}}}_{i}{\textbf{\emph{A}}}_{i}||_{F}^{2}+\lambda||{\textbf{\emph{A}}}_{i}||_{1}\right)$
(19) $\displaystyle\ \ \ \ \ \ \ \ \ \ \ \ \ \Updownarrow$
$\displaystyle\hat{\textbf{\emph{X}}}_{i}$
$\displaystyle=\arg\min_{\textbf{\emph{X}}_{i}}\left(\frac{1}{2}||{\textbf{\emph{Y}}}_{i}-{\textbf{\emph{X}}}_{i}||_{F}^{2}+\tau||{\textbf{\emph{X}}}_{i}||_{*}\right).$

###### Proof.

See Appendix B. ∎

Similar to Theorem 2, we have the following conclusion.

######  Corollary 1.

The weighted $\ell_{1}$-norm, $\ell_{p}$-norm and weighted $\ell_{p}$-norm are
equivalent to the weighted nuclear norm [19], Schatten $p$-norm [20] and the
weighted Schatten $p$-norm [21], respectively, under the proposed adaptive
dictionary.

It is worth noting that the main difference between sparse coding and rank
minimization is that sparse coding has a dictionary learning procedure while
the rank minimization problem does not.

###  3.3 Analyze the Sparsity of Group with the Nuclear Norm Minimization

Based on Theorem 2, the group-based sparse coding can be translated into the
rank minimization problem, and we now possess a benchmark to measure the
sparsity of each group by the rank minimization methods.

Specifically, four nuclear norm minimization methods are used to constrain Eq.
(3) to analyze the sparsity of each group, i.e., NNM [18], WNNM [19], SNM [20]
and WSNM [21]. Two gray-scale images, namely _Barbara_ and _boats_ , are used
as examples in the context of image inpainting and image CS recovery,
respectively. In image inpainting, 80% pixels of image _Barbara_ are damaged
in Fig. 2(b) and two groups based on 1# position and 2# position are generated
in Fig. 2(a). In image CS recovery, image _boats_ is compressively sampled by
a random Gaussian matrix with 0.2$N$ measurements and an initial image is
estimated by using a standard CS recovery method (e.g., DCT/BCS [29] based
reconstruction method) shown in Fig. 3(b). We conduct two groups based on 3#
position and 4# position in Fig. 3(a). From Fig. 2(c-d) and Fig. 3(c-d), we
can observe that the singular values of WSNM results are the best
approximation to the ground-truth in comparison with three other methods.
Furthermore, based on Theorem 2, WSNM can be equivalently translated into
solving the non-convex weighted $\ell_{p}$-norm minimization problem.

##  4 Group-based Sparse Coding for Image Restoration with Weighted
$\ell_{p}$-norm Minimization

We now verify the proposed scheme in the application of image restoration,
which aims to reconstruct a high quality image X from its degraded observation
Y,

$\textbf{\emph{Y}}=\textbf{\emph{H}}\textbf{\emph{X}}+{{{\boldsymbol{\kappa}}}},$
(20)

where H is a non-invertible linear degradation operator and
${\boldsymbol{\kappa}}$ is usually assumed to be a zero-mean white Gaussian
noise. With different setting of matrix H, Eq. (20) can represent different
image restoration tasks. For instance, when H is an identity matrix, Eq. (20)
becomes image denoising [30, 31]; when H is a blur operator, Eq. (20) becomes
image deblurring [13, 14]; when H is a diagonal matrix whose diagonal entries
are either 1 or 0, keeping or killing corresponding pixels, Eq. (20) becomes
image inpainting [32]; when H is a random projection matrix with more columns
than rows, Eq. (20) becomes image CS [33]. In this paper, we focus on image
inpainting and image CS recovery.

Specifically, given the observed degraded image Y in Eq. (20), we aim to
recover the original image X by solving the following non-convex minimization
problem,

$\hat{\textbf{\emph{A}}}=\arg\min\limits_{{\textbf{\emph{A}}}}\frac{1}{2}||{\textbf{\emph{Y}}}-\textbf{\emph{H}}{\textbf{\emph{D}}}{\textbf{\emph{A}}}||_{2}^{2}+\lambda||{\textbf{\emph{W}}}{\textbf{\emph{A}}}||_{p},$
(21)

where W represents the weights in the weighted $\ell_{p}$-norm and $\lambda$
is a regularization parameter.

###  4.1 ADMM based Algorithm for Weighted $\ell_{p}$-norm Minimization

Due to the non-convex fact of Eq. (21), and in order to make the optimization
tractable, we employ the alternating direction method of multipliers (ADMM)
[34] framework, whose underlying principle is to split the unconstrained
minimization problem into different constrained sub-problems. Numerical
simulations have shown that ADMM can converge by only using a small memory
footprint, which makes it attractive for various large-scale optimization
problems [35, 36]. In the following, we give a brief introduction of the ADMM
method by considering a constrained optimization problem,

$\min_{\textbf{\emph{Z}}\in\mathbb{R}^{\bf{N}},{\textbf{\emph{A}}}\in\mathbb{R}^{\bf{M}}}f(\textbf{\emph{Z}})+g({\textbf{\emph{A}}}),\qquad{\rm
s.t.}\qquad\textbf{\emph{Z}}=\textbf{\emph{G}}{\textbf{\emph{A}}},$ (22)

where $\textbf{\emph{G}}\in\mathbb{R}^{\bf{M}\times\bf{N}}$ and
$f:{\mathbb{R}^{\bf{N}}\rightarrow\mathbb{R}}$,
$g:{\mathbb{R}^{\bf{M}}\rightarrow\mathbb{R}}$. The basic ADMM regime is shown
in Algorithm 1.

Algorithm 1 The ADMM Algorithm

0: A and Z

1: Initial $\rho>0$, $\boldsymbol{b}$

2: for $t=0$ to Max-Iter do

3:
${\textbf{\emph{Z}}}^{t+1}=\arg\min\limits_{\textbf{\emph{Z}}}f(\textbf{\emph{Z}})+\frac{\rho}{2}||\textbf{\emph{Z}}-\textbf{\emph{G}}{{{\textbf{\emph{A}}}}}^{t}-\textbf{\emph{b}}^{t}||_{2}^{2}$.

4:
${\textbf{\emph{A}}}^{t+1}=\arg\min\limits_{{\textbf{\emph{A}}}}g({\textbf{\emph{A}}})+\frac{\rho}{2}||{\textbf{\emph{Z}}}^{t+1}-\textbf{\emph{G}}{{\textbf{\emph{A}}}}-\textbf{\emph{b}}^{t}||_{2}^{2}$.

5:
${\textbf{\emph{b}}}^{t+1}={\textbf{\emph{b}}}^{t}-({\textbf{\emph{Z}}}^{t+1}-\textbf{\emph{G}}{{\textbf{\emph{A}}}}^{t+1})$.

6: end for

Now, let us come back to Eq. (21) and use ADMM to solve it. We first translate
Eq. (21) into another equivalent constrained form by introducing an auxiliary
variable Z,

$\hat{\textbf{\emph{A}}}=\arg\min\limits_{\textbf{\emph{Z}},{\textbf{\emph{A}}}}\frac{1}{2}||{\textbf{\emph{Y}}}-\textbf{\emph{H}}{\textbf{\emph{Z}}}||_{2}^{2}+\lambda||{\textbf{\emph{W}}}{\textbf{\emph{A}}}||_{p},\
{\rm s.t.}\ \ \textbf{\emph{Z}}={\textbf{\emph{D}}}{\textbf{\emph{A}}}.$ (23)

Following this, Eq. (23) can be transformed into three iterative steps:

$\displaystyle{\textbf{\emph{Z}}}^{t+1}$
$\displaystyle=\arg\min\limits_{\textbf{\emph{Z}}}\frac{1}{2}||\textbf{\emph{Y}}-\textbf{\emph{H}}{\textbf{\emph{Z}}}||_{2}^{2}+\frac{\rho}{2}||\textbf{\emph{Z}}-{{\textbf{\emph{D}}}{\textbf{\emph{A}}}}^{t}-\textbf{\emph{b}}^{t}||_{2}^{2},$
(24) $\displaystyle{\textbf{\emph{A}}}^{t+1}$
$\displaystyle=\arg\min\limits_{{\textbf{\emph{A}}}}\lambda||{\textbf{\emph{W}}}{\textbf{\emph{A}}}||_{p}+\frac{\rho}{2}||\textbf{\emph{Z}}^{t+1}-{{\textbf{\emph{D}}}{\textbf{\emph{A}}}}-\textbf{\emph{b}}^{t}||_{2}^{2},$
(25) $\displaystyle{\textbf{\emph{b}}}^{t+1}$
$\displaystyle={\textbf{\emph{b}}}^{t}-({\textbf{\emph{Z}}}^{t+1}-{{\textbf{\emph{D}}}{\textbf{\emph{A}}}}^{t+1}).$
(26)

One can observe that the minimization of Eq. (23) involves two minimization
sub-problems, i.e., Z and A sub-problems. Fortunately, there is an efficient
solution to each sub-problem, which will be discussed in following
subsections. The superscript $t$ is omitted for conciseness in the derivation
below.

####  4.1.1 Z Sub-problem

Given A, the Z sub-problem in Eq. (24) becomes

$\min_{\textbf{\emph{Z}}}{\textbf{\emph{Q}}}_{1}({{\textbf{\emph{Z}}}})=\min\limits_{\textbf{\emph{Z}}}\frac{1}{2}||\textbf{\emph{Y}}-\textbf{\emph{H}}{\textbf{\emph{Z}}}||_{2}^{2}+\frac{\rho}{2}||\textbf{\emph{Z}}-{{\textbf{\emph{D}}}{\textbf{\emph{A}}}}-\textbf{\emph{b}}||_{2}^{2}.$
(27)

This is a quadratic form and has a closed-form solution,

$\hat{\textbf{\emph{Z}}}=({\textbf{\emph{H}}}^{T}{\textbf{\emph{H}}}+\rho{\textbf{\emph{I}}})^{-1}({\textbf{\emph{H}}}^{T}{\textbf{\emph{Y}}}+\rho({{\textbf{\emph{D}}}{\textbf{\emph{A}}}}+\textbf{\emph{b}})),$
(28)

where I is an identity matrix with desired dimensions. Owing to the specific
structure of H in image inpainting, Eq. (27) can be efficiently computed
without computing the matrix inverse.

However, in image CS recovery, as H is a random projection matrix without a
special structure, it is too expensive to solve Eq. (28) directly. In this
work, we adopt the gradient descent method [38] to solve Eq. (27),

$\hat{\textbf{\emph{Z}}}={\textbf{\emph{Z}}}-\eta{\textbf{\emph{q}}},$ (29)

where q is the gradient direction of the objective function
${\textbf{\emph{Q}}}_{1}({{\textbf{\emph{Z}}}})$, and $\eta$ represents the
step size. Thereby, in image CS recovery, we only need an iterative
calculation to solve the Z sub-problem,

$\hat{\textbf{\emph{Z}}}={\textbf{\emph{Z}}}-\eta({{\textbf{\emph{H}}}}^{T}{{\textbf{\emph{H}}}}{\textbf{\emph{Z}}}-{{\textbf{\emph{H}}}}^{T}{\textbf{\emph{Y}}}+\rho(\textbf{\emph{Z}}-{{\textbf{\emph{D}}}{\textbf{\emph{A}}}}-\textbf{\emph{b}})),$
(30)

where ${{\textbf{\emph{H}}}}^{T}{{\textbf{\emph{H}}}}$ and
${{\textbf{\emph{H}}}}^{T}{\textbf{\emph{Y}}}$ can be pre-calculated.

####  4.1.2 A sub-problem

Given Z, the A sub-problem in Eq. (25) can be rewritten as

$\min_{{\textbf{\emph{A}}}}{\textbf{\emph{Q}}}_{2}({\textbf{\emph{A}}})=\min\limits_{{\textbf{\emph{A}}}}\frac{1}{2}||{{\textbf{\emph{D}}}{\textbf{\emph{A}}}}-\textbf{\emph{L}}||_{2}^{2}\\\
+\frac{\lambda}{\rho}||{\textbf{\emph{W}}}{\textbf{\emph{A}}}||_{p},$ (31)

where $\textbf{\emph{L}}=\textbf{\emph{Z}}-\textbf{\emph{b}}$.

However, due to the complicated structure of
$||{\textbf{\emph{W}}}{\textbf{\emph{A}}}||_{p}$, it is difficult to solve Eq.
(31). Let $\textbf{\emph{X}}={{\textbf{\emph{D}}}{\textbf{\emph{A}}}}$, Eq.
(31) can be rewritten as

$\min_{{\textbf{\emph{A}}}}{\textbf{\emph{L}}}_{2}({\textbf{\emph{A}}})=\min\limits_{{\textbf{\emph{A}}}}\frac{1}{2}||{{\textbf{\emph{X}}}}-\textbf{\emph{L}}||_{2}^{2}\\\
+\frac{\lambda}{\rho}||{\textbf{\emph{W}}}{\textbf{\emph{A}}}||_{p}.$ (32)

In order to achieve a tractable solution to Eq. (32), a general assumption is
made, and with which even a closed-form solution can be achieved.
Specifically, L can be regarded as a noisy observation of X, and then the
assumption is made that each element of
$\textbf{\emph{E}}=\textbf{\emph{X}}-\textbf{\emph{L}}$ follows an independent
zero-mean Gaussian distribution with variance ${\sigma}^{2}$. Provided this
assumption, we have the following theorem.

######  Theorem 3.

Define $\textbf{\emph{x}},\textbf{\emph{l}}\in\mathbb{R}^{N}$,
${\textbf{\emph{X}}}_{i}$, ${\textbf{\emph{L}}}_{i}\in\mathbb{R}^{d\times m}$,
and $e_{j}$ denoting the $j$-th element of the error vector
${\textbf{\emph{e}}}\in\mathbb{R}^{N}$, where
$\textbf{\emph{e}}=\textbf{\emph{x}}-\textbf{\emph{l}}$. Assume that $e_{j}$
follows an independent zero mean Gaussian distribution with variance
${\sigma}^{2}$, and thus for any $\varepsilon>0$, we can represent the
relationship between
$\frac{1}{N}||\textbf{\emph{x}}-\textbf{\emph{l}}||_{2}^{2}$ and
${\frac{1}{S}}\sum_{i=1}^{n}||{\textbf{\emph{X}}}_{i}-{\textbf{\emph{L}}}_{i}||_{F}^{2}$
by the following property,

$\lim_{{N\rightarrow\infty}\atop{S\rightarrow\infty}}{\textbf{\emph{P}}}{\left(\left|\frac{1}{N}||\textbf{\emph{x}}-\textbf{\emph{l}}||_{2}^{2}-{\frac{1}{S}}\sum\nolimits_{i=1}^{n}||{\textbf{\emph{X}}}_{i}-{\textbf{\emph{L}}}_{i}||_{F}^{2}\right|<\varepsilon\right)}=1,$
(33)

where ${\textbf{\emph{P}}}(~{})$ represents the probability and $S=d\times
m\times n$.

###### Proof.

See Appendix C. ∎

Based on Theorem 3, we have the following equation with a very large
probability (limited to 1) at each iteration,

$\frac{1}{N}||\textbf{\emph{x}}-\textbf{\emph{l}}||_{2}^{2}={\frac{1}{S}}\sum\nolimits_{i=1}^{n}||{\textbf{\emph{X}}}_{i}-{\textbf{\emph{L}}}_{i}||_{F}^{2}.$
(34)

Now replacing $\textbf{\emph{x}},\textbf{\emph{l}}$ with
$\\{\textbf{\emph{X}},\textbf{\emph{L}}\\}$, along with Eq. (32), we have

$\displaystyle\min\limits_{{\textbf{\emph{A}}}}\frac{1}{2}{||\textbf{\emph{X}}-\textbf{\emph{L}}||_{2}^{2}}+\frac{\lambda}{\rho}||{\textbf{\emph{W}}}{\textbf{\emph{A}}}||_{p}$
(35)
$\displaystyle=\min\limits_{{{\textbf{\emph{A}}}}_{i}}\left(\sum\nolimits_{i=1}^{n}\frac{1}{2}||{\textbf{\emph{X}}}_{i}-{\textbf{\emph{L}}}_{i}||_{F}^{2}+{{\tau}}_{i}||{\textbf{\emph{W}}}_{i}{{\textbf{\emph{A}}}}_{i}||_{p}\right)$
$\displaystyle=\min\limits_{{{\textbf{\emph{A}}}}_{i}}\left(\sum\nolimits_{i=1}^{n}\frac{1}{2}||{\textbf{\emph{L}}}_{i}-{{\textbf{\emph{D}}}_{i}{{\textbf{\emph{A}}}}_{i}}||_{F}^{2}+{{\tau}}_{i}||{\textbf{\emph{W}}}_{i}{{\textbf{\emph{A}}}}_{i}||_{p}\right),$

where ${{\tau}}_{i}=\frac{{{\lambda}}_{i}{\emph{S}}}{\rho{\emph{N}}}$,
${{\textbf{\emph{D}}}_{i}}$ is a dictionary, and here we abused the $p$-norm
for matrix. Clearly, Eq. (35) can be viewed as a sparse coding problem by
solving $n$ sub-problems for each group ${\textbf{\emph{X}}}_{i}$. Based on
Theorem 1, Eq. (35) can be rewritten as:

$\displaystyle{{\hat{\textbf{\emph{A}}}}_{i}}$
$\displaystyle=\min\limits_{{{\textbf{\emph{A}}}}_{i}}\left(\sum\nolimits_{i=1}^{n}\frac{1}{2}||{\textbf{\emph{R}}}_{i}-{\textbf{\emph{A}}}_{i}||_{F}^{2}+{{\tau}}_{i}||{\textbf{\emph{W}}}_{i}{{\textbf{\emph{A}}}}_{i}||_{p}\right)$
(36)
$\displaystyle=\min\limits_{{\boldsymbol{\alpha}}_{i}}\left(\sum\nolimits_{i=1}^{n}\frac{1}{2}||{{\boldsymbol{\gamma}}_{i}}-{{\boldsymbol{\alpha}}_{i}}||_{2}^{2}+{{\tau}}_{i}||{\textbf{\emph{w}}}_{i}{{\boldsymbol{\alpha}}_{i}}||_{p}\right),$

where
${\textbf{\emph{X}}}_{i}={{\textbf{\emph{D}}}_{i}{\textbf{\emph{A}}}_{i}}$ and
${\textbf{\emph{L}}}_{i}={{\textbf{\emph{D}}}_{i}{\textbf{\emph{R}}}_{i}}$;
${{{{\boldsymbol{\alpha}}}}_{i}}$, ${{{{\boldsymbol{\gamma}}}}_{i}}$ and
${{\textbf{\emph{w}}}}_{i}$ denote the vectorization of the matrix
${{{\textbf{\emph{A}}}}_{i}}$, ${{{\textbf{\emph{R}}}}_{i}}$ and
${\textbf{\emph{W}}}_{i}$, respectively.

Therefore, the minimization problem of Eq. (31) can be simplified to solve the
minimization problem in Eq. (36).

Algorithm 2 Generalized Soft-Thresholding (GST) Algorithm [39].

0: ${{\gamma}_{i,j}},{{{{w}}}_{i,j}},p,K$

1:
$\tau_{p}^{\emph{GST}}({{{{w}}}_{i,j}})=(2{{{{w}}}_{i,j}}(1-p))^{\frac{1}{2-p}}+{{{{w}}}_{i,j}}p(2{{{{w}}}_{i,j}}(1-p))^{\frac{p-1}{2-p}}$.

2: if $|{{\gamma}_{i,j}}|\leq\tau_{p}^{\emph{GST}}({{{{w}}}_{i,j}})$ then

3: ${\textbf{\emph{T}}}_{p}^{\emph{GST}}({{\gamma}_{i,j}};{{{{w}}}_{i,j}})=0$;

4: else

5: $k=0,~{}~{}{{\alpha}_{i,j}}^{(k)}=|{{\gamma}_{i,j}}|$

6: for $k=0$ to $K$ do

7:
${{\alpha}_{i,j}}^{(k+1)}=|{{\gamma}_{i,j}}|-{{{{w}}}_{i,j}}p\left({{\alpha}_{i,j}}^{(k)}\right)^{p-1}$.

8:
${\textbf{\emph{T}}}_{p}^{\emph{GST}}({{\gamma}_{i,j}};{{{{w}}}_{i,j}})={\rm
sgn}({{\gamma}_{i,j}}){{\alpha}_{i,j}}^{(k)}$.

9: end for

10: end if

11: Output:
${\textbf{\emph{T}}}_{p}^{\emph{GST}}({{\gamma}_{i,j}};{{{{w}}}_{i,j}})$

###  4.2 Generalized Soft-Thresholding (GST) Algorithm for Weighted
$\ell_{p}$-norm Minimization

The generalized soft-thresholding (GST) algorithm [39] is employed to solve
Eq. (36). Specifically, given $p$, $\gamma_{i,j}$ and $w_{i,j}$, there exists
a specific threshold,

$\tau_{p}^{\emph{GST}}({{{{w}}}_{i,j}})=(2{{{{w}}}_{i,j}}(1-p))^{\frac{1}{2-p}}+{{{{w}}}_{i,j}}p(2{{{{w}}}_{i,j}}(1-p))^{\frac{p-1}{2-p}},$
(37)

where ${{\gamma}_{i,j}}$, ${{\alpha}_{i,j}}$ and ${w}_{i,j}$ are the $j$-th
element of ${{{\boldsymbol{\gamma}}}}_{i}$, ${{{\boldsymbol{\alpha}}}}_{i}$
and ${\textbf{{\emph{w}}}}_{i}$, respectively. Then, if
${{\gamma}_{i,j}}<\tau_{p}^{\emph{GST}}({{{{w}}}_{i,j}})$,
${{\alpha}_{i,j}}=0$ is the global minimum. Otherwise, the optimum will be
obtained at a non-zero point. According to [39], for any
${{\gamma}_{i,j}}\in(\tau_{p}^{\emph{GST}}({{{{w}}}_{i,j}}),+\infty)$, Eq.
(36) has one unique minimum
${\textbf{\emph{T}}}_{p}^{\emph{GST}}({{\gamma}_{i,j}};{{{{w}}}_{i,j}})$,
which can be obtained by solving the following equation,

${\textbf{\emph{T}}}_{p}^{\emph{GST}}({{\gamma}_{i,j}};{{{{w}}}_{i,j}})-{{\gamma}_{i,j}}+{{{{w}}}_{i,j}}p\left({\textbf{\emph{T}}}_{p}^{\emph{GST}}({{\gamma}_{i,j}};{{{{w}}}_{i,j}})\right)^{p-1}=0.$
(38)

The complete description of the GST algorithm is exhibited in Algorithm 2.
Please refer to [39] for more details.

Therefore, a closed-form solution of Eq. (36) can be computed as

${{{{\alpha}}}_{i,j}}={{\emph{GST}}}(\gamma_{i,j},\tau_{i,j}w_{i,j},p,K),$
(39)

where $K$ denotes the iteration number in the GST algorithm.

Remark:
If $p=1/2$, the closed-form solution of Eq. (36) can be solved by
${{\alpha}_{i,j}}^{3}+{{\gamma}_{i,j}}^{2}{{\alpha}_{i,j}}-2{{\gamma}_{i,j}}{{\alpha}_{i,j}}^{2}-{\tau_{i,j}}^{2}{{{{w}}}_{i,j}}^{2}/4=0$.
Similarly, for the case of $p=2/3$, the closed-form solution of Eq. (36) can
be solved by
${{\alpha}_{i,j}}^{4}+3{{\gamma}_{i,j}}^{2}{{\alpha}_{i,j}}^{2}-3{{\gamma}_{i,j}}{{\alpha}_{i,j}}^{3}-{{\gamma}_{i,j}}^{3}{{\alpha}_{i,j}}+8{\tau_{i,j}}^{3}{{{{w}}}_{i,j}}^{3}/27=0$
[55].

Algorithm 3 ADMM for weighted $\ell_{p}$-norm minimization

0: The observed image Y and the measurement matrix H.

1: Initial $t$, b, Z, ${{\boldsymbol{\alpha}}}$, C, K, d, m, $\rho$, $p$,
$\sigma$, $\epsilon$ and $\varepsilon$.

2: for $t=0$ to Max-Iter do

3: if H is mask operator then

4: Update ${{\textbf{\emph{Z}}}}^{t+1}$ by Eq. (28);

5: else if H is random projection operator then

6: Update ${{\textbf{\emph{Z}}}}^{t+1}$ by Eq. (30);

7: end if

8: for Each group ${\textbf{\emph{L}}}_{i}$ do

9: Construct dictionary ${\textbf{\emph{D}}}_{i}$ by computing Eq. (10);

10: Update ${\lambda_{i}}^{t+1}$ by computing Eq. (41);

11: Update $\tau_{i}^{t+1}$ computing by
${{\tau}}_{i}=\frac{{{\lambda}}_{i}{\emph{S}}}{\rho{\emph{N}}}$;

12: Update ${{\emph{w}}}_{i}^{t+1}$ by computing Eq. (40);

13: Update ${{{\textbf{\emph{A}}}}_{i}}^{t+1}$ computing by Eq. (39);

14: end for

15: Update ${\textbf{\emph{D}}}^{t+1}$ by concatenating all
${\textbf{\emph{D}}}_{i}$.

16: Update ${{{{\textbf{\emph{A}}}}}}^{t+1}$ by concatenating all
${\boldsymbol{\alpha}}_{i}$.

17: Update ${{\textbf{\emph{b}}}^{t+1}}$ by computing Eq. (26).

18: end for

19: Output: The final restored image
$\hat{\textbf{\emph{X}}}={\textbf{\emph{D}}}{{{\textbf{\emph{A}}}}}.$

Figure 4: Test images. Top row, from left to right: Mickey, Barbara,
Butterfly, elaine, Fence, straw, Golem, peppers. Bottom row, from left to
right: House, Starfish, Fence, Nanna, lena, fireman, Bridge, Zebra.

###  4.3 Setting the Weight and Regularization Parameter

As large values in coefficient ${{{\boldsymbol{\alpha}}}}_{i}$ usually depict
major edge and texture information [16], in order to reconstruct
${\textbf{\emph{X}}}_{i}$ from its degraded one, we should shrink the larger
values less, while shrinking smaller ones more. Therefore, we let

${{{\emph{w}}}}_{i}=\frac{1}{|{{{\boldsymbol{\gamma}}}}_{i}|+\epsilon},$ (40)

with $\epsilon$ as a small positive constant.

The regularization parameter $\lambda$ that balances the fidelity term and the
regularization term should be adaptively determined for better reconstruction
performance. Inspired by [40], $\lambda_{i}$ of each group
${\textbf{\emph{L}}}_{i}$ is set as:

$\lambda_{i}=\frac{2\sqrt{2}\sigma^{2}}{\delta_{i}+\varepsilon},$ (41)

where $\delta_{i}$ denotes the estimated variance of
${{{\boldsymbol{\gamma}}}}_{i}$, and $\varepsilon$ is a small positive
constant.

After solving the two sub-problems, we summarize the overall algorithm for Eq.
(21) in Algorithm 3.

TABLE I: Detailed setting of $\rho,\lambda$ for inpainting and CS recovery
with proposed adaptive dictionary learning approach. Image Inpainting
---
ADL |  $\ell_{1}$-norm |  $\ell_{p}$-norm |  $w\ell_{1}$-norm |  $w\ell_{p}$-norm
Parameters | $\rho$ | $\lambda$ | $\rho$ | $\lambda$ | $\rho$ | $\rho$
80% | 7e-5 | 5e-6 | 0.006 | 0.07 | 0.1 | 0.0003
70% | 1e-4 | 7e-6 | 0.008 | 0.07 | 0.1 | 0.0003
60% | 1e-5 | 1e-6 | 7e-5 | 3e-6 | 0.1 | 0.03
50% | 5e-5 | 1e-5 | 0.0001 | 7e-6 | 0.1 | 0.04
Image CS Recovery
ADL |  $\ell_{1}$-norm |  $\ell_{p}$-norm |  $w\ell_{1}$-norm |  $w\ell_{p}$-norm
Parameters | $\rho$ | $\lambda$ | $\rho$ | $\lambda$ | $\rho$ | $\rho$
0.2 | 0.001 | 5e-5 | 0.003 | 5e-4 | 0.1 | 0.0005
0.3 | 0.003 | 7e-4 | 0.01 | 3e-4 | 0.1 | 0.05
0.4 | 0.003 | 5e-4 | 0.006 | 3e-4 | 0.1 | 0.05
0.5 | 0.003 | 5e-4 | 0.006 | 3e-4 | 0.2 | 0.05
TABLE II: PSNR (dB) comparison of $\ell_{1}$-norm, $\ell_{p}$-norm, $w\ell_{1}$-norm and $w\ell_{p}$-norm, based on the proposed ADL scheme for image inpainting. Miss pixels | Methods | Mickey | Butterfly | Fence | Starfish | Nanna | Zebra | fireman | Golem | Average
---|---|---|---|---|---|---|---|---|---|---
80% |  $\ell_{1}$-norm | 25.97 | 25.61 | 28.90 | 26.98 | 25.46 | 22.33 | 25.39 | 25.29 | 25.74
$\ell_{p}$-norm | 26.74 | 26.36 | 29.47 | 27.54 | 25.87 | 23.05 | 25.63 | 25.69 | 26.29
$w\ell_{1}$-norm | 26.66 | 26.39 | 29.98 | 28.00 | 25.73 | 22.39 | 25.68 | 26.12 | 26.37
$w\ell_{p}$-norm | 26.92 | 26.52 | 30.00 | 28.05 | 25.95 | 23.06 | 25.80 | 26.26 | 26.57
70% |  $\ell_{1}$-norm | 27.86 | 27.86 | 30.72 | 29.02 | 27.32 | 24.26 | 27.05 | 27.40 | 27.69
$\ell_{p}$-norm | 29.04 | 29.10 | 31.54 | 30.25 | 28.31 | 25.19 | 27.69 | 28.37 | 28.69
$w\ell_{1}$-norm | 29.16 | 29.21 | 31.83 | 30.54 | 28.07 | 24.82 | 27.81 | 28.53 | 28.75
$w\ell_{p}$-norm | 29.29 | 29.28 | 31.85 | 30.56 | 28.39 | 25.13 | 27.84 | 28.62 | 28.87
60% |  $\ell_{1}$-norm | 29.61 | 29.82 | 32.29 | 30.78 | 29.02 | 25.93 | 28.53 | 28.93 | 29.36
$\ell_{p}$-norm | 29.85 | 30.16 | 32.51 | 31.14 | 29.22 | 26.13 | 28.69 | 29.16 | 29.61
$w\ell_{1}$-norm | 31.44 | 31.40 | 33.65 | 32.93 | 30.42 | 27.04 | 29.74 | 30.27 | 30.86
$w\ell_{p}$-norm | 31.46 | 31.54 | 33.67 | 33.02 | 30.56 | 27.21 | 29.77 | 30.35 | 30.95
50% |  $\ell_{1}$-norm | 31.62 | 31.46 | 33.78 | 32.62 | 30.68 | 27.65 | 30.13 | 30.48 | 31.05
$\ell_{p}$-norm | 31.88 | 31.78 | 33.97 | 32.99 | 30.89 | 27.86 | 30.28 | 30.70 | 31.29
$w\ell_{1}$-norm | 33.98 | 33.16 | 35.30 | 34.99 | 32.38 | 29.12 | 31.31 | 31.88 | 32.76
$w\ell_{p}$-norm | 34.01 | 33.26 | 35.25 | 35.05 | 32.53 | 29.26 | 31.32 | 31.91 | 32.82

##  5 Experimental Results

To demonstrate the feasibility of the proposed scheme, in this section, we
report extensive experiments to evaluate the performance of the proposed
weighted $\ell_{p}$-norm ($w\ell_{p}$-norm) minimization and compare it with
many existing norm minimization methods, including $\ell_{1}$-norm
minimization, weighted $\ell_{1}$-norm ($w\ell_{1}$-norm) minimization, and
$\ell_{p}$-norm minimization in group-based sparse coding. We conduct
performance evaluations on image inpainting and image CS recovery. The peak
signal-to-noise ratio (PSNR) is adopted to evaluate the quality of restored
images. We have also calculated the SSIM [57] of recovered images, which shows
similar results to PSNR and thus omitted here due to the space limit. The
experimental images are shown in Fig. 4.

###  5.1 Parameter Selection

The parameters used in the algorithm are empirically chosen according to
different applications in order to achieve relatively good performance. Note
that all norm minimization problems are based on the proposed adaptive
dictionary learning (ADL) scheme in group-based sparse coding.

In image inpainting, the mask is generated randomly. The size of patch is set
to be $8\times 8$. The similar patch number $m$ is set to 60. The searching
window $C\times C$ is set to $25\times 25$; $\sigma=\sqrt{2}$ and $K=2$; $p$
is set to 0.45, 0.45, 0.95 and 0.95 when 80%, 70%, 60% and 50% pixels are
missing, respectively. $\epsilon$ and $\varepsilon$ are set as 0.35, 0.35 and
0.1, 0.3 for $w\ell_{1}$-norm and $w\ell_{p}$-norm, respectively. The detailed
settings of $\rho$ and $\lambda$ are shown on the upper part of Table I.
However, due to the existence of the weight W, $\lambda$ is computed by Eq.
(41) in $w\ell_{1}$-norm and $w\ell_{p}$-norm.

In image CS recovery, we generate the CS measurements at the block level by
utilizing a Gaussian random projection matrix to test images, i.e., CS with
block size $32\times 32$ [29]. The patch size is set to be $7\times 7$. The
similar patch number $m=60$, and the search window is set to $20\times 20$;
$\sigma=\sqrt{2}$ and $K=2$; $p$ is set to 0.5, 0.95, 0.95 and 0.95 with
0.2$N$, 0.3$N$, 0.4$N$ and 0.5$N$ measurements, respectively. $\epsilon$ and
$\varepsilon$ are set as 0.35, 0.35 and 0.1, 0.4 for $w\ell_{1}$-norm and
$w\ell_{p}$-norm, respectively. Similarly, $\lambda$ is computed by Eq. (41)
in $w\ell_{1}$-norm and $w\ell_{p}$-norm. The detailed settings of $\rho$ and
$\lambda$ are shown at the lower part of Table I.

In addition, to make a fair comparison of all norm minimization methods, The
iterative stopping criterion is set to: PSNR($t+1$) - PSNR($t$)$<$0, where
PSNR($t+1$) and PSNR($t$) denote the PSNR values of reconstructed images at
the $(t+1)$-th iteration and $t$-th iteration, respectively.

TABLE III: PSNR (dB) comparison of $\ell_{1}$-norm, $\ell_{p}$-norm, $w\ell_{1}$-norm and $w\ell_{p}$-norm, based on the proposed ADL scheme for image CS Recovery. Ratio | Methods | Barbara | bridge | elaine | Fence | House | lena | peppers | straw | Average
---|---|---|---|---|---|---|---|---|---|---
0.2 |  $\ell_{1}$-norm | 32.24 | 25.03 | 34.59 | 29.31 | 36.01 | 30.77 | 30.00 | 24.11 | 30.26
$\ell_{p}$-norm | 34.31 | 25.13 | 35.75 | 29.99 | 37.15 | 31.50 | 30.79 | 24.82 | 31.18
$w\ell_{1}$-norm | 34.53 | 25.04 | 36.22 | 30.19 | 37.07 | 31.49 | 31.22 | 24.82 | 31.32
$w\ell_{p}$-norm | 34.55 | 25.28 | 36.00 | 30.38 | 36.92 | 31.62 | 31.32 | 25.06 | 31.39
0.3 |  $\ell_{1}$-norm | 34.49 | 26.49 | 36.76 | 31.16 | 37.94 | 32.97 | 31.93 | 26.11 | 32.23
$\ell_{p}$-norm | 34.86 | 26.59 | 37.07 | 31.42 | 38.29 | 33.15 | 32.22 | 26.23 | 32.48
$w\ell_{1}$-norm | 37.10 | 27.25 | 38.26 | 32.50 | 39.07 | 34.26 | 33.39 | 27.84 | 33.71
$w\ell_{p}$-norm | 37.23 | 27.22 | 38.30 | 32.53 | 39.23 | 34.29 | 33.32 | 27.89 | 33.75
0.4 |  $\ell_{1}$-norm | 36.79 | 27.94 | 38.58 | 32.84 | 39.70 | 34.76 | 33.63 | 27.95 | 34.03
$\ell_{p}$-norm | 37.15 | 28.06 | 38.87 | 33.09 | 39.98 | 34.95 | 33.91 | 28.10 | 34.26
$w\ell_{1}$-norm | 39.04 | 28.90 | 40.03 | 34.50 | 40.82 | 36.58 | 35.10 | 30.30 | 35.66
$w\ell_{p}$-norm | 39.13 | 28.85 | 40.05 | 34.42 | 40.93 | 36.66 | 35.00 | 30.28 | 35.67
0.5 |  $\ell_{1}$-norm | 38.80 | 29.38 | 40.26 | 34.50 | 41.27 | 36.56 | 35.18 | 29.88 | 35.73
$\ell_{p}$-norm | 39.19 | 29.51 | 40.54 | 34.75 | 41.52 | 36.78 | 35.43 | 30.07 | 35.97
$w\ell_{1}$-norm | 40.84 | 30.51 | 41.52 | 36.29 | 42.25 | 38.99 | 36.56 | 32.49 | 37.43
$w\ell_{p}$-norm | 40.94 | 30.52 | 41.63 | 36.24 | 42.38 | 39.09 | 36.53 | 32.46 | 37.47

Figure 5: Inpaniting performance comparison of Mickey based on the proposed
adaptive dictionary learning method. (a) Original image; (b) Degraded image
with 80% pixels missing; (c) $\ell_{1}$-norm (PSNR= 25.97dB); (d)
$\ell_{p}$-norm (PSNR= 26.74dB); (e) $w\ell_{1}$-norm (PSNR= 26.66dB); (f)
$w\ell_{p}$-norm (PSNR= 26.92dB).

Figure 6: CS recovery performance comparison of straw with $0.2N$ measurements
based on the proposed adaptive dictionary learning method. (a) Original image;
(b) Initial recovered image by [29] (PSNR= 23.76dB); (c) $\ell_{1}$-norm
(PSNR= 24.11dB); (d) $\ell_{p}$-norm (PSNR= 24.82dB); (e) $w\ell_{1}$-norm
(PSNR= 24.82dB); (f) $w\ell_{p}$-norm (PSNR= 25.06dB).

###  5.2 Comparisons of $\ell_{1}$-norm, Weighted $\ell_{1}$-norm,
$\ell_{p}$-norm and Weighted $\ell_{p}$-norm

We firstly compare four norm minimization methods, i.e., $\ell_{1}$-norm
minimization, $w\ell_{1}$-norm minimization, $\ell_{p}$-norm minimization and
$w\ell_{p}$-norm minimization, based on the proposed ADL scheme for image
inpainting and image CS recovery.

The PSNR results of image inpainting and image CS recovery are shown in Table
II and Table III, respectively. It can be seen that the $w\ell_{p}$-norm
achieves better results than other three norms in most cases in terms of PSNR.
Fig. 5 plots the image inpainting results of image Mickey with 80% pixels
missing. Fig. 6 plots the image CS recovery results of image Straw with 0.2$N$
measurements. We can observe that the $w\ell_{p}$-norm obtains better
perceptual quality than other three norms. Therefore, these experimental
results are consistent with our theoretical analysis.

TABLE IV: Detailed setting of $\rho,\lambda$ for inpainting and CS recovery,
with the graph-based dictionary learning [41] and PCA dictionary learning
[42]. Image Inpainting
---
Graph |  $\ell_{1}$-norm |  $\ell_{p}$-norm |  $w\ell_{1}$-norm |  $w\ell_{p}$-norm
Parameters | $\rho$ | $\lambda$ | $\rho$ | $\lambda$ | $\rho$ | $\rho$
80% | 0.008 | 1e-5 | 0.003 | 7e-5 | 0.15 | 0.06
70% | 0.003 | 1e-5 | 0.003 | 7e-5 | 0.1 | 0.05
60% | 0.006 | 7e-5 | 0.003 | 5e-5 | 0.07 | 0.09
50% | 0.003 | 7e-5 | 0.003 | 9e-5 | 0.05 | 0.05
Image CS Recovery
PCA |  $\ell_{1}$-norm |  $\ell_{p}$-norm |  $w\ell_{1}$-norm |  $w\ell_{p}$-norm
Parameters | $\rho$ | $\lambda$ | $\rho$ | $\lambda$ | $\rho$ | $\rho$
0.2 | 0.03 | 1e-6 | 0.003 | 7e-5 | 0.09 | 0.07
0.3 | 0.008 | 1e-6 | 0.006 | 7e-5 | 0.07 | 0.09
0.4 | 0.008 | 1e-6 | 0.008 | 1e-5 | 0.05 | 0.05
0.5 | 0.008 | 1e-6 | 0.008 | 1e-5 | 0.05 | 0.05

Next, in order to prove the universality of the proposed scheme, instead of
using the proposed ADL method, we exploit another widely used dictionary
learning methods to verify the proposed scheme, i.e., graph-based dictionary
learning method [41] and PCA dictionary learning method [42] for image
inpainting and image CS recovery. Similar to the proposed ADL dictionary, we
learn the graph-based dictionary and PCA dictionary from each group of the
degraded image. All the parameters remain the same as specified in the
subsection 5.1 except for $\rho$ and $\lambda$, which are now shown in Table
IV. The PSNR comparison results for image inpainting of four competing methods
are shown in Table V. It can be observed that the $w\ell_{p}$-norm
consistently outperforms the other three norms for most testing images (the
only exception is the image Zebra for which the $w\ell_{1}$-norm is slightly
higher than the $w\ell_{p}$-norm in the scene of 80% and 70% pixels missing).
The PSNR comparison results of image CS recovery are shown in Table VI, and we
can observe that the $w\ell_{p}$-norm outperforms the other three norms in
most cases. Fig. 7 plots the visual comparison of image Fence with 80% pixels
missing for image inpainting based on graph-based dictionary learning method.
The visual comparison of image peppers with 0.2$N$ measurements for image CS
recovery based on PCA dictionary learning method is shown in Fig. 8. It is
clearly demonstrated that the $w\ell_{p}$-norm achieves better visual quality
than other three norms. This again verifies the feasibility of the proposed
scheme.

We also notice that for various dictionary learning methods, the results of
$w\ell_{p}$-norm are usually a little bit ($\sim$0.1dB) better than those of
$w\ell_{1}$-norm, which has also been observed in [21]. Similar phenomenons
can also be found between $\ell_{p}$-norm and $\ell_{1}$-norm. In addition,
comparing Tables V-VI with Tables II-III, we can observe that the proposed ADL
can provide better performance than graph-based dictionary learning and PCA
dictionary learning methods. This again demonstrate the superiority of our
proposed algorithm.

TABLE V: PSNR (dB) comparison of $\ell_{1}$-norm, $\ell_{p}$-norm, $w\ell_{1}$-norm and $w\ell_{p}$-norm, based on the _graph-based dictionary learning_ method for image inpainting. Miss pixels | Methods | Mickey | Butterfly | Fence | Starfish | Nanna | Zebra | fireman | Golem | Average
---|---|---|---|---|---|---|---|---|---|---
80% |  $\ell_{1}$-norm | 24.63 | 23.62 | 22.92 | 26.27 | 25.52 | 20.45 | 24.59 | 23.57 | 23.82
$\ell_{p}$-norm | 25.20 | 24.51 | 25.83 | 26.41 | 24.79 | 20.79 | 24.88 | 24.31 | 24.59
$w\ell_{1}$-norm | 25.30 | 24.63 | 26.67 | 26.20 | 24.75 | 20.98 | 24.88 | 24.44 | 24.73
$w\ell_{p}$-norm | 25.40 | 24.74 | 26.99 | 26.43 | 24.92 | 20.97 | 25.00 | 24.60 | 24.88
70% |  $\ell_{1}$-norm | 26.31 | 25.75 | 25.06 | 28.07 | 26.21 | 21.84 | 26.08 | 25.33 | 25.58
$\ell_{p}$-norm | 27.21 | 26.88 | 28.27 | 28.33 | 26.58 | 22.43 | 26.50 | 26.43 | 26.58
$w\ell_{1}$-norm | 27.37 | 27.00 | 28.89 | 27.92 | 26.58 | 22.80 | 26.55 | 26.65 | 26.72
$w\ell_{p}$-norm | 27.49 | 27.19 | 29.12 | 28.50 | 26.81 | 22.77 | 26.77 | 26.84 | 26.93
60% |  $\ell_{1}$-norm | 27.58 | 27.50 | 27.48 | 29.46 | 27.61 | 23.37 | 27.38 | 26.80 | 27.15
$\ell_{p}$-norm | 27.72 | 27.66 | 28.09 | 29.47 | 27.65 | 23.46 | 27.41 | 26.93 | 27.30
$w\ell_{1}$-norm | 28.79 | 28.84 | 30.74 | 29.68 | 28.22 | 24.72 | 28.05 | 28.39 | 28.43
$w\ell_{p}$-norm | 28.80 | 28.91 | 30.79 | 29.81 | 28.29 | 24.75 | 28.11 | 28.45 | 28.49
50% |  $\ell_{1}$-norm | 29.14 | 29.24 | 29.73 | 30.93 | 29.13 | 24.84 | 28.78 | 28.37 | 28.77
$\ell_{p}$-norm | 29.31 | 29.40 | 30.24 | 30.86 | 29.12 | 24.98 | 28.80 | 28.50 | 28.90
$w\ell_{1}$-norm | 30.68 | 30.62 | 32.65 | 31.51 | 29.76 | 26.61 | 29.64 | 30.04 | 30.19
$w\ell_{p}$-norm | 30.71 | 30.69 | 32.71 | 31.56 | 29.82 | 26.62 | 29.70 | 30.08 | 30.24

Figure 7: Inpaniting performance comparison on the image Fence based on the
graph-based dictionary learning method. (a) Original image; (b) Degraded image
with 80% pixels missing sample; (c) $\ell_{1}$-norm (PSNR= 22.92dB); (d)
$\ell_{p}$-norm (PSNR= 25.83dB); (e) $w\ell_{1}$-norm (PSNR= 26.67dB); (f)
$w\ell_{p}$-norm (PSNR= 26.99dB).

Figure 8: CS recovery performance comparison with $0.2N$ measurements on the image peppers based on PCA dictionary learning method. (a) Original image; (b) Initial image by [29] (PSNR= 28.61dB); (c) $\ell_{1}$-norm (PSNR= 30.08dB); (d) $\ell_{p}$-norm (PSNR= 30.87dB); (e) $w\ell_{1}$-norm (PSNR= 31.10dB); (f) $w\ell_{p}$-norm (PSNR= 31.31dB). TABLE VI: PSNR (dB) comparison of $\ell_{1}$-norm, $\ell_{p}$-norm, $w\ell_{1}$-norm and $w\ell_{p}$-norm, based on _PCA dictionary learning_ scheme for image CS Recovery. Ratio | Methods | Barbara | bridge | elaine | Fence | House | lena | peppers | straw | Average
---|---|---|---|---|---|---|---|---|---|---
0.2 |  $\ell_{1}$-norm | 32.13 | 25.05 | 34.60 | 29.12 | 35.92 | 30.78 | 30.08 | 24.10 | 30.22
$\ell_{p}$-norm | 34.07 | 25.24 | 35.74 | 29.87 | 36.76 | 31.46 | 30.87 | 24.74 | 31.10
$w\ell_{1}$-norm | 32.89 | 25.25 | 33.32 | 29.87 | 36.23 | 31.23 | 31.10 | 24.50 | 30.55
$w\ell_{p}$-norm | 34.09 | 25.29 | 35.74 | 30.14 | 36.75 | 31.48 | 31.31 | 24.89 | 31.21
0.3 |  $\ell_{1}$-norm | 34.38 | 26.53 | 36.80 | 31.08 | 38.05 | 33.03 | 32.10 | 26.09 | 32.26
$\ell_{p}$-norm | 34.50 | 26.60 | 36.84 | 31.19 | 38.04 | 33.09 | 32.24 | 26.18 | 32.34
$w\ell_{1}$-norm | 35.53 | 26.95 | 34.94 | 31.73 | 38.04 | 33.69 | 32.99 | 27.05 | 32.61
$w\ell_{p}$-norm | 35.69 | 27.04 | 37.25 | 31.84 | 38.07 | 33.80 | 33.06 | 27.28 | 33.01
0.4 |  $\ell_{1}$-norm | 36.69 | 28.01 | 38.65 | 32.84 | 39.80 | 34.83 | 33.85 | 27.96 | 34.08
$\ell_{p}$-norm | 37.03 | 28.13 | 38.92 | 33.09 | 40.07 | 35.04 | 34.10 | 28.10 | 34.31
$w\ell_{1}$-norm | 37.63 | 28.39 | 39.03 | 33.43 | 39.75 | 35.46 | 34.59 | 29.07 | 34.67
$w\ell_{p}$-norm | 37.74 | 28.45 | 39.11 | 33.51 | 39.84 | 35.57 | 34.65 | 29.21 | 34.76
0.5 |  $\ell_{1}$-norm | 38.72 | 29.46 | 40.32 | 34.55 | 41.36 | 36.64 | 35.45 | 29.89 | 35.80
$\ell_{p}$-norm | 39.09 | 29.60 | 40.59 | 34.80 | 41.59 | 36.88 | 35.66 | 30.07 | 36.03
$w\ell_{1}$-norm | 39.53 | 29.95 | 40.59 | 35.13 | 41.25 | 37.45 | 36.09 | 31.16 | 36.39
$w\ell_{p}$-norm | 39.64 | 30.00 | 40.67 | 35.21 | 41.33 | 37.56 | 36.14 | 31.30 | 36.48

###  5.3 Comparison with Other Leading Algorithms

We now validate the performance of the proposed scheme, i.e., group-based
sparse coding with non-convex $w\ell_{p}$-norm (GSC-$w\ell_{p}$) minimization
for image inpainting and image CS recovery with the proposed adaptive
dictionary learning method, by comparing it with recent state-of-the-art
methods.

In image inpainting, we compare GSC-$w\ell_{p}$ with five other competing
methods: SALSA [43], BPFA [44], IPPO [45], JSM [46] and Aloha [47]. Table VII
lists the PSNR results for a collection of 8 color images for these five
methods. The average gains of the proposed GSC-$w\ell_{p}$ over SALSA, BPFA,
IPPO, JSM and Aloha methods are as much as 4.06dB, 2.26dB, 1.06dB, 1.25dB and
1.62dB, respectively. The visual comparison of image Zebra with 80% pixels
missing is shown in Fig. 9. It can be seen that SALSA and BPFA could not
reconstruct sharp edges and fine details. The IPPO, JSM and Aloha methods
produce images with a much better visual quality than SALSA and BPFA, but
still suffer from some undesirable artifacts, such as the ringing effects. By
contrast, the proposed GSC-$w\ell_{p}$ not only preserves sharp edges and fine
details, but also eliminates the ringing effects.

Figure 9: Inpaniting performance comparison on the image Zebra. (a) Original image; (b) Degraded image with 80% pixels missing sample; (c) SALSA [43] (PSNR= 19.68dB); (d) BPFA [44] (PSNR= 20.90dB); (e) IPPO [45] (PSNR= 22.71dB); (f) JSM [46] (PSNR= 21.88dB); (g) Aloha [47] (PSNR=22.72dB); (h) GSC-$w\ell_{p}$ (PSNR= 23.06dB). TABLE VII: PSNR (dB) comparison of SALSA [43], BPFA [44], IPPO [45], JSM [46], ALoha [47] and GSC-$w\ell_{p}$ for image inpainting. Miss pixels | Methods | Mickey | Butterfly | Fence | Starfish | Nanna | Zebra | fireman | Golem | Average
---|---|---|---|---|---|---|---|---|---|---
80% | SALSA [43] | 24.46 | 22.85 | 21.80 | 25.70 | 24.12 | 19.68 | 24.38 | 23.15 | 23.27
BPFA [44] | 24.53 | 24.04 | 26.24 | 26.79 | 24.71 | 20.90 | 24.88 | 24.13 | 24.53
IPPO [45] | 26.33 | 25.13 | 27.98 | 26.30 | 25.60 | 22.71 | 25.56 | 25.66 | 25.66
JSM [46] | 26.09 | 25.57 | 28.59 | 27.07 | 25.33 | 21.88 | 25.31 | 25.40 | 25.65
Aloha [47] | 25.33 | 24.88 | 28.88 | 26.33 | 25.54 | 22.72 | 25.03 | 25.23 | 25.49
GSC-$w\ell_{p}$ | 26.92 | 26.52 | 30.00 | 28.05 | 25.95 | 23.06 | 25.80 | 26.26 | 26.57
70% | SALSA [43] | 25.98 | 25.06 | 23.57 | 27.55 | 25.44 | 21.41 | 25.82 | 25.00 | 24.98
BPFA [44] | 26.16 | 26.68 | 28.87 | 28.93 | 26.62 | 22.78 | 26.55 | 26.46 | 26.63
IPPO [45] | 28.59 | 27.68 | 30.08 | 28.91 | 27.44 | 24.76 | 27.44 | 27.92 | 27.85
JSM [46] | 28.25 | 27.97 | 30.46 | 29.36 | 27.34 | 23.95 | 27.16 | 27.59 | 27.76
Aloha [47] | 27.11 | 27.29 | 30.57 | 28.22 | 27.43 | 24.55 | 26.52 | 27.33 | 27.38
GSC-$w\ell_{p}$ | 29.29 | 29.28 | 31.85 | 30.56 | 28.39 | 25.13 | 27.84 | 28.61 | 28.87
60% | SALSA [43] | 27.41 | 26.79 | 25.45 | 29.09 | 26.94 | 22.80 | 27.15 | 26.66 | 26.54
BPFA [44] | 27.83 | 28.88 | 30.79 | 30.98 | 28.63 | 24.53 | 28.23 | 28.30 | 28.52
IPPO [45] | 30.76 | 29.85 | 32.14 | 31.09 | 29.41 | 26.79 | 29.13 | 29.57 | 29.84
JSM [46] | 29.85 | 29.83 | 32.23 | 31.40 | 29.09 | 25.90 | 28.79 | 29.24 | 29.54
Aloha [47] | 28.59 | 29.16 | 32.33 | 30.19 | 29.51 | 26.24 | 28.24 | 28.92 | 29.15
GSC-$w\ell_{p}$ | 31.46 | 31.54 | 33.67 | 33.02 | 30.56 | 27.21 | 29.77 | 30.35 | 30.95
50% | SALSA [43] | 28.98 | 28.52 | 27.25 | 30.90 | 28.53 | 24.42 | 28.54 | 28.20 | 28.17
BPFA [44] | 29.43 | 30.98 | 32.82 | 33.13 | 30.68 | 26.37 | 30.12 | 30.46 | 30.50
IPPO [45] | 32.74 | 31.69 | 33.95 | 33.10 | 31.17 | 28.42 | 30.82 | 31.11 | 31.63
JSM [46] | 31.96 | 31.47 | 33.75 | 33.24 | 30.75 | 27.77 | 30.37 | 30.89 | 31.27
Aloha [47] | 30.33 | 30.78 | 33.79 | 31.85 | 31.24 | 27.67 | 29.88 | 30.28 | 30.73
GSC-$w\ell_{p}$ | 34.00 | 33.26 | 35.25 | 35.05 | 32.53 | 29.26 | 31.32 | 31.91 | 32.82
TABLE VIII: PSNR (dB) comparison of BCS[48], BM3D-CS [49], ADS-CS [50], ALSB [51], SGSR [52], MRK [59], JASR [53], AMP-FBM3D [58] and GSC-$w\ell_{p}$ for image CS recovery. Ratio | Methods | Barbara | Bridge | Elaine | Fence | House | Lena | Peppers | Straw | Average
---|---|---|---|---|---|---|---|---|---|---
0.2 | BCS [48] | 24.24 | 23.61 | 31.18 | 21.57 | 30.54 | 28.15 | 27.15 | 20.69 | 25.89
BM3D-CS [49] | 28.83 | 23.77 | 33.75 | 22.57 | 35.04 | 30.30 | 31.09 | 20.04 | 28.17
ADS-CS [50] | 32.27 | 25.39 | 35.78 | 28.37 | 35.76 | 33.92 | 31.01 | 23.74 | 30.78
ALSB [51] | 30.72 | 24.97 | 32.56 | 28.41 | 36.08 | 30.68 | 29.96 | 24.33 | 29.71
SGSR [52] | 33.44 | 24.72 | 34.85 | 29.42 | 35.81 | 30.89 | 30.51 | 24.54 | 30.52
MRK [59] | 27.99 | 25.70 | 35.94 | 22.20 | 36.36 | 32.58 | 31.83 | 23.02 | 29.45
JASR [53] | 34.16 | 25.18 | 35.66 | 29.95 | 35.88 | 31.19 | 31.06 | 24.95 | 31.00
| AMP-FBM3D [58] | 33.66 | 25.00 | 36.14 | 30.15 | 37.75 | 34.86 | 31.74 | 23.28 | 31.57
| GSC-$w\ell_{p}$ | 34.55 | 25.28 | 36.00 | 30.38 | 36.92 | 31.62 | 31.32 | 25.06 | 31.39
0.3 | BCS [48] | 25.59 | 25.00 | 33.68 | 23.24 | 32.85 | 30.16 | 29.05 | 22.19 | 27.72
BM3D-CS [49] | 33.00 | 26.59 | 37.23 | 30.68 | 36.84 | 35.01 | 33.62 | 22.37 | 31.92
ADS-CS [50] | 35.81 | 27.36 | 37.91 | 31.29 | 38.21 | 37.20 | 33.26 | 26.58 | 33.45
ALSB [51] | 35.00 | 26.83 | 34.30 | 30.83 | 38.34 | 33.36 | 32.37 | 26.61 | 32.21
SGSR [52] | 35.91 | 26.80 | 36.87 | 31.56 | 37.37 | 33.27 | 32.71 | 27.33 | 32.73
MRK [59] | 32.64 | 27.62 | 38.40 | 24.44 | 38.35 | 35.69 | 33.91 | 25.52 | 32.07
JASR [53] | 36.59 | 27.19 | 36.83 | 31.87 | 38.04 | 34.05 | 33.09 | 27.87 | 33.19
| AMP-FBM3D [58] | 36.41 | 26.97 | 38.25 | 33.05 | 39.92 | 38.01 | 33.75 | 26.24 | 34.07
| GSC-$w\ell_{p}$ | 37.23 | 27.22 | 38.30 | 32.53 | 39.23 | 34.29 | 33.32 | 27.89 | 33.75
0.4 | BCS [48] | 27.10 | 26.31 | 35.66 | 24.81 | 34.65 | 32.06 | 30.77 | 23.71 | 29.38
BM3D-CS [49] | 35.92 | 28.52 | 39.23 | 33.83 | 38.08 | 38.46 | 35.20 | 24.38 | 34.20
ADS-CS [50] | 38.34 | 29.40 | 39.50 | 34.02 | 40.30 | 39.63 | 34.96 | 28.80 | 35.59
ALSB [51] | 38.34 | 29.10 | 39.60 | 32.83 | 40.25 | 35.47 | 34.44 | 28.54 | 34.58
SGSR [52] | 37.70 | 28.46 | 38.63 | 33.34 | 38.99 | 35.68 | 34.47 | 29.63 | 34.61
MRK [59] | 36.17 | 29.24 | 40.02 | 26.63 | 40.04 | 38.14 | 35.50 | 27.69 | 34.18
JASR [53] | 37.39 | 28.69 | 38.28 | 33.96 | 38.80 | 36.12 | 34.70 | 30.04 | 34.75
| AMP-FBM3D [58] | 38.34 | 28.82 | 39.74 | 35.42 | 41.63 | 40.60 | 35.20 | 28.32 | 36.01
| GSC-$w\ell_{p}$ | 39.13 | 28.85 | 40.05 | 34.42 | 40.93 | 36.66 | 35.00 | 30.28 | 35.67
0.5 | BCS [48] | 28.67 | 27.64 | 37.51 | 26.20 | 36.29 | 33.78 | 32.31 | 25.30 | 30.96
BM3D-CS [49] | 38.43 | 30.68 | 41.01 | 36.21 | 40.34 | 39.19 | 36.80 | 26.94 | 36.20
ADS-CS [50] | 40.19 | 30.83 | 40.92 | 36.20 | 41.86 | 41.60 | 36.46 | 30.88 | 37.37
ALSB [51] | 39.26 | 30.03 | 41.18 | 34.81 | 41.93 | 37.79 | 36.21 | 30.61 | 36.48
SGSR [52] | 39.38 | 30.09 | 40.07 | 35.28 | 40.56 | 37.90 | 35.97 | 31.71 | 36.37
MRK [59] | 38.98 | 31.01 | 41.61 | 29.60 | 41.46 | 39.99 | 36.97 | 30.11 | 36.22
JASR [53] | 40.31 | 30.30 | 39.47 | 35.72 | 41.44 | 38.33 | 36.22 | 32.04 | 36.73
| AMP-FBM3D [58] | 40.12 | 30.68 | 41.31 | 37.45 | 43.37 | 42.72 | 36.55 | 29.99 | 37.77
| GSC-$w\ell_{p}$ | 40.94 | 30.52 | 41.63 | 36.24 | 42.38 | 39.09 | 36.53 | 32.46 | 37.47

Figure 10: CS recovery of Barbara with 0.2$N$ measurements. (a) Original
image; (b) BCS [48] (PSNR =24.24dB); (c) BM3D-CS [49] (PSNR= 28.83dB); (d)
ADS-CS [50] (PSNR= 32.27dB); (e) ALSB [51] (PSNR= 30.72dB); (f) SGSR [52]
(PSNR= 33.44dB); (g) MRK [59] (PSNR= 27.99dB); (h) JASR [53] (PSNR= 34.16dB);
(i) AMP-FBM3D [58] (PSNR =33.66dB); (j) GSC-$w\ell_{p}$ (PSNR= 34.55dB).

In image CS recovery, we compare the proposed GSC-$w\ell_{p}$ with eight other
competing methods including BCS [48], BM3D-CS [49], ADS-CS [50], ALSB [51],
SGSR [52], MRK[59], JASR [53] and AMP-FBM3D [58]. The PSNR results are shown
in Table VIII. The proposed GSC-$w\ell_{p}$ achieves 6.08dB, 1.95dB, 0.27dB,
1.33dB, 1.01dB, 1.59dB and 0.65dB improvement in average over the BCS,
BM3D-CS, ADS-CS, ALSB, SGSR, MRK and JASR, respectively. Although the PSNR
results of the proposed GSC-$w\ell_{p}$ are slightly lower than AMP-FBM3D
method, the AMP-FBM3D method is based on the pre-filtering BM3D [60]. Note
that BM3D is a well-known image reconstruction method that delivers state-of-
the-art denoising results. Therefore, the CS reconstruction performance of the
AMP-FBM3D method largely depends on the pre-filtering BM3D. However, it is
worth noting that the proposed GSC-$w\ell_{p}$ can outperform AMP-FBM3D in
most cases, except for image House and Lena due to the existence of many
similar regions in these two images. Similarly, the performance of MRK is also
depending on the pre-filtering BM3D. The visual comparison of image Barbara
with 0.2$N$ measurements is shown in Fig. 10. One can observe that the BCS
method generates the worst perceptual result. The BM3D-CS, ADS-CS, ALSB, SGSR,
MRK, JASR and AMP-FBM3D methods still suffer from some undesirable artifacts
or over-smooth phenomena. By contrast, the proposed GSC-$w\ell_{p}$ not only
removes most of the visual artifacts, but also preserves large-scale sharp
edges and small-scale fine image details.

Figure 11: Performance comparison with different matched patch numbers $m$ for
image CS recovery and image inpainting. (a) PSNR results achieved by different
$m$ in the case of the image inpainting with 70% missing sample. (b) PSNR
results achieved by different $m$ in the case of the image CS recovery with
0.2$N$ measurements.

###  5.4 Effect of the Number of Matched Patches

In this subsection, we discuss how to select the best matching patch number
$m$ for the performance of the proposed GSC-$w\ell_{p}$. Specifically, to
investigate the sensitivity of our method against $m$, two experiments were
conducted with different $m$, ranging from 20 to 200, in the case of image
inpainting with 70% pixels missing and image CS with 0.2$N$ measurements,
respectively. The results with different $m$ are shown in Fig. 11. It can be
seen that all the curves are almost flat, showing the performance of the
proposed GSC-$w\ell_{p}$ being relatively insensitive to $m$. The best
performance of each case was usually achieved with $m$ in the range [40, 80].
Therefore, in this paper $m$ was set to be 60.

###  5.5 Comparison Between ADMM and IST

In this subsection, another classical optimization method iterative
shrinkage/theresholding (IST) [54] is exploited to solve the proposed
GSC-$w\ell_{p}$ in Eq. (21) for CS image reconstruction. We perform a
comparison between ADMM and IST with 0.2$N$ and 0.3$N$ measurements for two
images, elaine and Barbara as examples. Fig. 12 shows their progression curves
of the PSNR (dB) achieved by ADMM and IST. It is obvious that ADMM is more
efficient and effective to solve the proposed GSC-$w\ell_{p}$ than IST.

Figure 12: Comparison between ADMM and IST. (a) PSNR results achieved by ADMM
and IST with 0.2$N$ measurements for elaine. (b) PSNR results achieved by ADMM
and IST with 0.3$N$ measurements for Barbara.

Figure 13: Convergence analysis of the proposed scheme. (a) PSNR results
versus iteration number for image CS recovery with 0.2$N$ measurements. (b)
PSNR results versus iteration number for image inpainting with 80% pixels
missing.

###  5.6 Convergence

Since the proposed model is non-convex, it is difficult to provide its
theoretical proof of global convergence. Hereby, we present empirical evidence
to show the convergence of the proposed model. Fig. 13 plots the curves of the
PSNR values versus iteration numbers for image CS (including
$\emph{Peppers},\emph{House},\emph{Fence}$ and Lena) with 0.2$N$ measurements
as well as image inpainting with 80% pixels missing for image
$\emph{Mickey},\emph{Starfish},\emph{Nanna}$ and Golem, respectively. It can
be seen that with the increase of the iteration number, the PSNR curves of the
reconstructed images gradually increase and then become flat and stable.
Therefore, we conclude that the proposed scheme has a good convergence
performance.

##  6 Conclusion

This paper analyzed the group sparsity from the perspective of rank
minimization. A group-based adaptive dictionary learning method has been
proposed, ensuring a low computational complexity. We have proved the
equivalence of the group-based sparse coding and the rank minimization problem
under the proposed dictionary, and thus bridged the gap between sparse-coding
and rank minimization. Four nuclear norm minimization methods including NNM,
SNM, WNNM and WSNM have been adopted to analyze the sparsity of each group and
the solution of WSNM was the best approximation to real singular values of
each group. WSNM has been equivalently transformed into a non-convex weighted
$\ell_{p}$-norm minimization problem in group-based sparse coding. We have
employed the alternating direction method of multipliers algorithm to solve
the non-convex weighted $\ell_{p}$-norm minimization problem. Experimental
results have demonstrated that the proposed scheme is feasible and achieves
performance improvements over the state-of-the-art methods both quantitatively
and qualitatively.

##  Appendix A Proof of the Theorem 1

###### Proof.

The adaptive dictionary ${\textbf{\emph{D}}}_{i}$ is constructed by Eq. (10).
From the unitary property of ${\textbf{\emph{U}}}_{i}$ and
${\textbf{\emph{V}}}_{i}$, we have

$\displaystyle||{\textbf{\emph{Y}}}_{i}-{\textbf{\emph{X}}}_{i}||_{F}^{2}=||{\textbf{\emph{D}}}_{i}({\textbf{\emph{B}}}_{i}-{\textbf{\emph{A}}}_{i})||_{F}^{2}=||{\textbf{\emph{U}}}_{i}{\rm
diag}({\textbf{\emph{B}}}_{i}-{\textbf{\emph{A}}}_{i}){\textbf{\emph{V}}}_{i}||_{F}^{2}$
(42) $\displaystyle={\rm Tr}({\textbf{\emph{U}}}_{i}{\rm
diag}({\textbf{\emph{B}}}_{i}-{\textbf{\emph{A}}}_{i}){\textbf{\emph{V}}}_{i}{\textbf{\emph{V}}}_{i}^{T}{\rm
diag}({\textbf{\emph{B}}}_{i}-{\textbf{\emph{A}}}_{i}){\textbf{\emph{U}}}_{i}^{T})$
$\displaystyle={\rm Tr}({\textbf{\emph{U}}}_{i}{\rm
diag}({\textbf{\emph{B}}}_{i}-{\textbf{\emph{A}}}_{i}){\rm
diag}({\textbf{\emph{B}}}_{i}-{\textbf{\emph{A}}}_{i}){\textbf{\emph{U}}}_{i}^{T})$
$\displaystyle={\rm Tr}({\rm
diag}({\textbf{\emph{B}}}_{i}-{\textbf{\emph{A}}}_{i}){\textbf{\emph{U}}}_{i}{\textbf{\emph{U}}}_{i}^{T}{\rm
diag}({\textbf{\emph{B}}}_{i}-{\textbf{\emph{A}}}_{i}))$ $\displaystyle={\rm
Tr}({\rm diag}({\textbf{\emph{B}}}_{i}-{\textbf{\emph{A}}}_{i}){\rm
diag}({\textbf{\emph{B}}}_{i}-{\textbf{\emph{A}}}_{i}))$
$\displaystyle=||{\textbf{\emph{B}}}_{i}-{\textbf{\emph{A}}}_{i}||_{F}^{2},$

where
${\textbf{\emph{X}}}_{i}={{\textbf{\emph{D}}}_{i}{\textbf{\emph{A}}}_{i}}$ and
${\textbf{\emph{Y}}}_{i}={{\textbf{\emph{D}}}_{i}{\textbf{\emph{B}}}_{i}}$. ∎

##  Appendix B Proof of the Theorem 2

###### Proof.

On the basis of Theorem 1, we have

$\displaystyle{\hat{\textbf{\emph{A}}}}_{i}$
$\displaystyle=\arg\min\limits_{{\textbf{\emph{A}}}_{i}}\left(\frac{1}{2}||{\textbf{\emph{Y}}}_{i}-{\textbf{\emph{D}}}_{i}{\textbf{\emph{A}}}_{i}||_{F}^{2}+\lambda||{\textbf{\emph{A}}}_{i}||_{1}\right)$
(43)
$\displaystyle=\arg\min\limits_{{\textbf{\emph{A}}}_{i}}\left(\frac{1}{2}||{\textbf{\emph{B}}}_{i}-{\textbf{\emph{A}}}_{i}||_{F}^{2}+\lambda||{\textbf{\emph{A}}}_{i}||_{1}\right)$
$\displaystyle=\arg\min\limits_{\boldsymbol{\alpha}_{i}}\left(\frac{1}{2}||{\boldsymbol{\beta}}_{i}-{\boldsymbol{\alpha}}_{i}||_{2}^{2}+\lambda||{\boldsymbol{\alpha}}_{i}||_{1}\right),$

where
${\textbf{\emph{X}}}_{i}={{\textbf{\emph{D}}}_{i}{\textbf{\emph{A}}}_{i}}$ and
${\textbf{\emph{Y}}}_{i}={{\textbf{\emph{D}}}_{i}{\textbf{\emph{B}}}_{i}}$.
${{{{\boldsymbol{\alpha}}}}_{i}}$ and ${{{{\boldsymbol{\beta}}}}_{i}}$ denote
the vectorization of the matrix ${{{\textbf{\emph{A}}}}_{i}}$ and
${{{\textbf{\emph{B}}}}_{i}}$, respectively.

Thus, based on Lemma 1, we have

$\displaystyle{{\boldsymbol{\alpha}}}_{i}$ $\displaystyle={\rm
soft}({{\boldsymbol{\beta}}}_{i},\lambda)={\rm
sgn}({{\boldsymbol{\beta}}}_{i})\odot{\rm
max}(abs({{\boldsymbol{\beta}}}_{i})-\lambda,0).$ (44)

Obviously, according to Eqs. (9) and (10), we have

$\displaystyle{\textbf{\emph{D}}}_{i}{\hat{\textbf{\emph{A}}}}_{i}$
$\displaystyle=\sum\nolimits_{j=1}^{n_{1}}{{\rm
soft}({\boldsymbol{\beta}}}_{i,j},\lambda){\textbf{\emph{d}}}_{i,j}$ (45)
$\displaystyle=\sum\nolimits_{j=1}^{n_{1}}{{\rm
soft}({\boldsymbol{\beta}}}_{i,j},\lambda){\textbf{\emph{u}}}_{i,j}{\textbf{\emph{v}}}_{i,j}^{T}$
$\displaystyle={\textbf{\emph{U}}}_{i}\mathcal{D}_{\lambda}(\boldsymbol{\Sigma}_{i}){\textbf{\emph{V}}}_{i}^{T},$

where ${{\boldsymbol{\beta}}}_{i,j}$ represents the $j$-th element of the
$i$-th group sparse coefficient ${{\boldsymbol{\beta}}}_{i}$, and
$\boldsymbol{\Sigma}_{i}$ is the singular value matrix of the $i$-th group
${\textbf{\emph{Y}}}_{i}$.

Following this, and based on _Lemma 2_ , we have proved that the group-based
sparse coding is equivalent to the rank minimization problem, i.e.

$\displaystyle{\hat{\textbf{\emph{A}}}}_{i}$
$\displaystyle=\arg\min\limits_{{\textbf{\emph{A}}}_{i}}\left(\frac{1}{2}||{\textbf{\emph{Y}}}_{i}-{\textbf{\emph{D}}}_{i}{\textbf{\emph{A}}}_{i}||_{F}^{2}+\lambda||{\textbf{\emph{A}}}_{i}||_{1}\right)$
(46) $\displaystyle\ \ \ \ \ \ \ \ \ \ \ \ \ \Updownarrow$
$\displaystyle{\hat{\textbf{\emph{X}}}}_{i}$
$\displaystyle=\arg\min_{\textbf{\emph{X}}_{i}}\left(\frac{1}{2}||{\textbf{\emph{Y}}}_{i}-{\textbf{\emph{X}}}_{i}||_{F}^{2}+\tau||{\textbf{\emph{X}}}_{i}||_{*}\right).$

∎

##  Appendix C Proof of the Theorem 3

###### Proof.

Owing to the assumption that $e_{j}$ follows an independent zero mean Gaussian
distribution with variance $\sigma^{2}$, namely, $\mathbb{E}[e_{j}]$ and
$\textbf{\rm{Var}}[{e_{j}}]=\sigma^{2}$, it can be deduced that each
${e_{j}}^{2}$ is also independent, and the mean of each ${e_{j}}^{2}$ is

$\mathbb{E}[e_{j}^{2}]=\textbf{\rm{Var}}[{e_{j}}]+[\mathbb{E}[e_{j}]]^{2}=\sigma^{2},\quad\emph{j}=1,2,...,\emph{N}.$
(47)

By invoking the law of large numbers in probability theory, for any
$\epsilon>0$, it leads to
$\lim\limits_{\emph{N}\rightarrow\infty}{\textbf{\emph{P}}}\\{|\frac{1}{\emph{N}}\Sigma_{\emph{j}=1}^{\emph{N}}e_{j}^{2}-\sigma^{2}|<\frac{\epsilon}{2}\\}=1$,
namely,

$\lim\limits_{\emph{N}\rightarrow\infty}{\textbf{\emph{P}}}\\{|\frac{1}{\emph{N}}||\textbf{\emph{x}}-\textbf{\emph{l}}||_{2}^{2}-\sigma^{2}|<\frac{\epsilon}{2}\\}=1.$
(48)

Next, we denote the concatenation of all the groups ${\textbf{\emph{X}}}_{i}$
and ${\textbf{\emph{L}}}_{i},\ \emph{i}=1,2,...,\emph{n}$, by X and L,
respectively. Meanwhile, we denote the error of each element of
${\textbf{\emph{X}}}-{\textbf{\emph{L}}}$ by $e_{s},\
\emph{s}=1,2,...,\emph{S}$. We have also assumed $e_{s}$ following an
independent zero mean Gaussian distribution with variance $\sigma^{2}$.

Therefore, the same process applied to $e_{s}^{2}$ yields
$\lim\limits_{\emph{S}\rightarrow\infty}{\textbf{\emph{P}}}\\{|\frac{1}{\emph{S}}\Sigma_{\emph{s}=1}^{\emph{S}}e_{s}^{2}-\sigma^{2}|<\frac{\varepsilon}{2}\\}=1$,
i.e.,

$\lim\limits_{\emph{S}\rightarrow\infty}{\textbf{\emph{P}}}\\{|\frac{1}{\emph{S}}\Sigma_{\emph{i}=1}^{\emph{n}}||{\textbf{\emph{X}}}_{i}-{\textbf{\emph{L}}}_{i}||_{F}^{2}-\sigma^{2}|<\frac{\varepsilon}{2}\\}=1.$
(49)

Obviously, considering Eqs. (48) and (49) together, we have proved Eq. (33). ∎

## References

  * [1] Aharon M, Elad M, Bruckstein A. $rmk$-SVD: An algorithm for designing overcomplete dictionaries for sparse representation[J]. IEEE Transactions on signal processing, 2006, 54(11): 4311-4322.
  * [2] Elad M, Aharon M. Image denoising via sparse and redundant representations over learned dictionaries[J]. IEEE Transactions on Image processing, 2006, 15(12): 3736-3745.
  * [3] Bao C, Ji H, Quan Y, et al. Dictionary learning for sparse coding: Algorithms and convergence analysis[J]. IEEE transactions on pattern analysis and machine intelligence, 2016, 38(7): 1356-1369.
  * [4] Jiang Z, Lin Z, Davis L S. Label consistent K-SVD: Learning a discriminative dictionary for recognition[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2013, 35(11): 2651-2664.
  * [5] Mairal J, Bach F, Ponce J, et al. Online dictionary learning for sparse coding[C]//Proceedings of the 26th annual international conference on machine learning. ACM, 2009: 689-696.
  * [6] Mairal J, Ponce J, Sapiro G, et al. Supervised dictionary learning[C]//Advances in neural information processing systems. 2009: 1033-1040.
  * [7] Wen B, Ravishankar S, Bresler Y. Structured overcomplete sparsifying transform learning with convergence guarantees and applications[J]. International Journal of Computer Vision, 2015, 114(2-3): 137-167.
  * [8] Ophir B, Lustig M, Elad M. Multi-scale dictionary learning using wavelets[J]. IEEE Journal of Selected Topics in Signal Processing, 2011, 5(5): 1014-1024.
  * [9] Zhang Q, Li B. Discriminative K-SVD for dictionary learning in face recognition[C]//Computer Vision and Pattern Recognition (CVPR), 2010 IEEE Conference on. IEEE, 2010: 2691-2698.
  * [10] Jiang Z, Lin Z, Davis L S. Label consistent K-SVD: Learning a discriminative dictionary for recognition[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2013, 35(11): 2651-2664.
  * [11] Lun D P K. Robust fringe projection profilometry via sparse representation[J]. IEEE Transactions on Image Processing, 2016, 25(4): 1726-1739.
  * [12] Mairal J, Bach F, Ponce J, et al. Non-local sparse models for image restoration[C]//Computer Vision, 2009 IEEE 12th International Conference on. IEEE, 2009: 2272-2279.
  * [13] Zhang J, Zhao D, Gao W. Group-based sparse representation for image restoration[J]. IEEE Transactions on Image Processing, 2014, 23(8): 3336-3351.
  * [14] Dong W, Shi G, Ma Y, et al. Image restoration via simultaneous sparse coding: Where structured sparsity meets gaussian scale mixture[J]. International Journal of Computer Vision, 2015, 114(2-3): 217-232.
  * [15] Q. Wang, X. Zhang, Y. Wu, L. Tang and Z. Zha, ”Nonconvex Weighted $ell_{p}$ Minimization Based Group Sparse Representation Framework for Image Denoising,” in IEEE Signal Processing Letters, vol. 24, no. 11, pp. 1686-1690, Nov. 2017.
  * [16] Candes E J, Wakin M B, Boyd S P. Enhancing sparsity by reweighted $\ell_{1}$ minimization[J]. Journal of Fourier analysis and applications, 2008, 14(5): 877-905.
  * [17] Cand s E J, Romberg J, Tao T. Robust uncertainty principles: Exact signal reconstruction from highly incomplete frequency information[J]. IEEE Transactions on information theory, 2006, 52(2): 489-509.
  * [18] Cai J F, Cand s E J, Shen Z. A singular value thresholding algorithm for matrix completion[J]. SIAM Journal on Optimization, 2010, 20(4): 1956-1982.
  * [19] Gu S, Zhang L, Zuo W, et al. Weighted nuclear norm minimization with application to image denoising[C]//Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition. 2014: 2862-2869.
  * [20] Nie F, Huang H, Ding C H Q. Low-Rank Matrix Recovery via Efficient Schatten p-Norm Minimization[C]//AAAI. 2012.
  * [21] Xie Y, Gu S, Liu Y, et al. Weighted Schatten $p$-norm minimization for image denoising and background subtraction[J]. IEEE transactions on image processing, 2016, 25(10): 4842-4857.
  * [22] Zha Z, Liu X, Huang X, et al. Analyzing the group sparsity based on the rank minimization methods[C]//Multimedia and Expo (ICME), 2017 IEEE International Conference on. IEEE, 2017: 883-888.
  * [23] Srebro N, Jaakkola T. Weighted low-rank approximations[C]//Proceedings of the 20th International Conference on Machine Learning (ICML-03). 2003: 720-727.
  * [24] Eriksson A, Van Den Hengel A. Efficient computation of robust low-rank matrix approximations in the presence of missing data using the L 1 norm[C]//Computer Vision and Pattern Recognition (CVPR), 2010 IEEE Conference on. IEEE, 2010: 771-778.
  * [25] Zhao Q, Meng D, Xu Z, et al. $L_{1}$-Norm Low-Rank Matrix Factorization by Variational Bayesian Method[J]. IEEE transactions on neural networks and learning systems, 2015, 26(4): 825-839.
  * [26] Mnih A, Salakhutdinov R R. Probabilistic matrix factorization[C]//Advances in neural information processing systems. 2008: 1257-1264.
  * [27] Kong Y, Shao M, Li K, et al. Probabilistic Low-Rank Multitask Learning[J]. IEEE transactions on neural networks and learning systems, 2017.
  * [28] Li C, Yin W, Zhang Y. User s guide for TVAL3: TV minimization by augmented lagrangian and alternating direction algorithms[J]. CAAM report, 2009, 20: 46-47.
  * [29] Chen C, Tramel E W, Fowler J E. Compressed-sensing recovery of images and video using multihypothesis predictions[C]//Signals, Systems and Computers (ASILOMAR), 2011 Conference Record of the Forty Fifth Asilomar Conference on. IEEE, 2011: 1193-1198.
  * [30] Zha Z, Liu X, Zhou Z, et al. Image denoising via group sparsity residual constraint[C]//Acoustics, Speech and Signal Processing (ICASSP), 2017 IEEE International Conference on. IEEE, 2017: 1787-1791.
  * [31] Wen B, Ravishankar S, Bresler Y. FRIST flipping and rotation invariant sparsifying transform learning and applications[J]. Inverse Problems, 2017, 33(7): 074007.
  * [32] Zhou M, Chen H, Ren L, et al. Non-parametric Bayesian dictionary learning for sparse image representations[C]//Advances in neural information processing systems. 2009: 2295-2303.
  * [33] Dong W, Shi G, Li X, et al. Compressive sensing via nonlocal low-rank regularization[J]. IEEE Transactions on Image Processing, 2014, 23(8): 3618-3632.
  * [34] Boyd S, Parikh N, Chu E, et al. Distributed optimization and statistical learning via the alternating direction method of multipliers[J]. Foundations and Trends? in Machine Learning, 2011, 3(1): 1-122.
  * [35] Chartrand R, Wohlberg B. A nonconvex ADMM algorithm for group sparsity with sparse groups[C]//Acoustics, Speech and Signal Processing (ICASSP), 2013 IEEE International Conference on. IEEE, 2013: 6009-6013.
  * [36] Zhao C, Zhang J, Ma S, et al. Nonconvex Lp nuclear norm based ADMM framework for compressed sensing[C]//Data Compression Conference (DCC), 2016. IEEE, 2016: 161-170.
  * [37] Afonso M V, Bioucas-Dias J M, Figueiredo M A T. Fast image recovery using variable splitting and constrained optimization[J]. IEEE Transactions on Image Processing, 2010, 19(9): 2345-2356.
  * [38] Avriel M. Nonlinear programming: analysis and methods[M]. Courier Corporation, 2003.
  * [39] Zuo W, Meng D, Zhang L, et al. A generalized iterated shrinkage algorithm for non-convex sparse coding[C]//Proceedings of the IEEE international conference on computer vision. 2013: 217-224.
  * [40] Chang S G, Yu B, Vetterli M. Adaptive wavelet thresholding for image denoising and compression[J]. IEEE transactions on image processing, 2000, 9(9): 1532-1546.
  * [41] Hu W, Li X, Cheung G, et al. Depth map denoising using graph-based transform and group sparsity[C]//Multimedia Signal Processing (MMSP), 2013 IEEE 15th International Workshop on. IEEE, 2013: 001-006.
  * [42] Dong W, Zhang L, Shi G, et al. Nonlocally centralized sparse representation for image restoration[J]. IEEE Transactions on Image Processing, 2013, 22(4): 1620-1630.
  * [43] Afonso M V, Bioucas-Dias J M, Figueiredo M A T. An augmented Lagrangian approach to the constrained optimization formulation of imaging inverse problems[J]. IEEE Transactions on Image Processing, 2011, 20(3): 681-695.
  * [44] Zhou M, Chen H, Paisley J, et al. Nonparametric Bayesian dictionary learning for analysis of noisy and incomplete images[J]. IEEE Transactions on Image Processing, 2012, 21(1): 130-144.
  * [45] Ram I, Elad M, Cohen I. Image processing using smooth ordering of its patches[J]. IEEE transactions on image processing, 2013, 22(7): 2764-2774.
  * [46] Zhang J, Zhao D, Xiong R, et al. Image restoration using joint statistical modeling in a space-transform domain[J]. IEEE Transactions on Circuits and Systems for Video Technology, 2014, 24(6): 915-928.
  * [47] Jin K H, Ye J C. Annihilating filter-based low-rank Hankel matrix approach for image inpainting[J]. IEEE Transactions on Image Processing, 2015, 24(11): 3498-3511.
  * [48] Mun S, Fowler J E. Block compressed sensing of images using directional transforms[C]//Image Processing (ICIP), 2009 16th IEEE International Conference on. IEEE, 2009: 3021-3024.
  * [49] Egiazarian K, Foi A, Katkovnik V. Compressed sensing image reconstruction via recursive spatially adaptive filtering[C]//Image Processing, 2007. ICIP 2007. IEEE International Conference on. IEEE, 2007, 1: I-549-I-552.
  * [50] Dong W, Shi G, Li X, et al. Image reconstruction with locally adaptive sparsity and nonlocal robust regularization[J]. Signal Processing: Image Communication, 2012, 27(10): 1109-1122.
  * [51] Zhang J, Zhao C, Zhao D, et al. Image compressive sensing recovery using adaptively learned sparsifying basis via L0 minimization[J]. Signal Processing, 2014, 103: 114-126.
  * [52] Zhang J, Zhao D, Jiang F, et al. Structural group sparse representation for image compressive sensing recovery[C]//Data Compression Conference (DCC), 2013. IEEE, 2013: 331-340.
  * [53] Eslahi N, Aghagolzadeh A. Compressive sensing image restoration using adaptive curvelet thresholding and nonlocal sparse regularization[J]. IEEE Transactions on Image Processing, 2016, 25(7): 3126-3140.
  * [54] Beck A, Teboulle M. Fast gradient-based algorithms for constrained total variation image denoising and deblurring problems[J]. IEEE Transactions on Image Processing, 2009, 18(11): 2419-2434.
  * [55] Krishnan D, Fergus R. Fast image deconvolution using hyper-Laplacian priors[C]//Advances in Neural Information Processing Systems. 2009: 1033-1041.
  * [56] Eldar Y C, Kuppinger P, Bolcskei H. Block-sparse signals: Uncertainty relations and efficient recovery[J]. IEEE Transactions on Signal Processing, 2010, 58(6): 3042-3054.
  * [57] Wang Z, Bovik A C, Sheikh H R, et al. Image quality assessment: from error visibility to structural similarity[J]. IEEE transactions on image processing, 2004, 13(4): 600-612.
  * [58] Metzler C A, Maleki A, Baraniuk R G. From denoising to compressed sensing[J]. IEEE Transactions on Information Theory, 2016, 62(9): 5117-5144.
  * [59] Canh T N, Dinh K Q, Jeon B. Multi-scale/multi-resolution Kronecker compressive imaging[C]//Image Processing (ICIP), 2015 IEEE International Conference on. IEEE, 2015: 2700-2704.
  * [60] Dabov K, Foi A, Katkovnik V, et al. Image denoising by sparse 3-D transform-domain collaborative filtering[J]. IEEE Transactions on image processing, 2007, 16(8): 2080-2095.
  * [61] Cand s E J, Li X, Ma Y, et al. Robust principal component analysis?[J]. Journal of the ACM (JACM), 2011, 58(3): 11.
  * [62] Liao X, Li H, Carin L. Generalized Alternating Projection for Weighted-2,1 Minimization with Applications to Model-Based Compressive Sensing[J]. SIAM Journal on Imaging Sciences, 2014, 7(2): 797-823.