1

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

arXiv:1709.03979v2 [] 8 Nov 2017

Zhiyuan Zha, Xin Yuan, Senior Member, IEEE
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 `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.

F

1

I NTRODUCTION

T

RADITIONAL patch-based sparse coding has been
widely used in image processing tasks and has achieved
excellent results [1–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–11]. Another parallel research is using the
rank minimization models for image processing [24, 33, 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

Z. Zha is with the department of Electronic Science and Engineering, Nanjing
University, Nanjing 210023, China. E-mail: zhazhiyuan.mmd@gmail.com.
X. Yuan is with Nokia Bell Labs, 600 Mountain Avenue, Murray Hill, NJ,
07974, USA. E-mail: xyuan@bell-labs.com.

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)1 have
demonstrated great potentials in various image processing
tasks [12–15]. The GSC is a powerful mechanism to integrate
local sparsity and nonlocal similarity
√ of image patches.
√
it
Taking a gray-scale image X ∈ R N × N as an
√ example,
√
is divided into n overlapping patches of size d × d, and
each patch is denoted by a vector xi ∈ Rd , i = 1, 2, ..., n.
Then for each patch xi , its m similar patches are selected
from a searching window with C × C pixels to form a set
Si . Following this, all patches in Si are stacked into a matrix
X i ∈ Rd×m , i.e.,
X i = {xi,1 , xi,2 , ..., xi,m }.

(1)

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


1
Âi = arg min
||X i − Di Ai ||2F + λ||Ai ||0 ,
(2)
Ai
2
1. This group-based sparse coding is different from the block-sparse
signal [56], where all items in one block are zeros or non-zeros.

2

where λ is the regularization parameter, || ||2F denotes
the Frobenius norm, and || ||0 signifies the `0 -norm2 , i.e.,
counting the nonzero entries in Ai .
Since `0 -norm minimization is NP-hard, it is often replaced by the `1 -norm or the weighted `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, Candès et al. [17] proved that solving `1 norm optimization problem can recover a K -sparse signal
x ∈ RN 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 `1 -norm minimization. Meanwhile, advanced minimization problems, like the
weighted `1 -norm [16] and weighted `1,2 -norm [62], are
also proposed to solve the `0 -norm minimization problem.
However, no matter which method is used, it is just an
estimate to the `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. `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 `p -norm minimization problem
in group-based sparse coding. We develop algorithms to
solve this weighted `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
`p -norm minimization problem based on the alternating
direction method of multipliers (ADMM) framework. Section 5 presents experimental results. Section 6 concludes the
2. Though `0 is not a strict norm, we follow the terminology convention in the literature.

paper. The preliminary work has appeared in [22]3 .

D  [ D1 , D2 ,

, Dn ]

Fig. 1. Correspondence between group-based sparse coding and rank
minimization via the proposed adaptive dictionary learning approach,
where ||X ||∗ and ||X ||1 represent nuclear norm and `1 -norm, respectively; ||X ||Sp and ||X ||p represent Schatten p-norm and `p -norm, respectively; ||X ||w,∗ and ||W X ||1 represent the weighted nuclear norm
and weighted `1 -norm, respectively; ||X ||w,Sp and ||W X ||p represent
the weighted Schatten p-norm and weighted `p -norm, respectively.

2
2.1

BACKGROUND AND R ELATED W ORK
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–27] and the
rank minimization methods [18–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 `2 -norm [23], robust LRMF
methods under `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
3. Significant 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.

3

to Y as possible under F -norm data fidelity with a nuclear
norm constraint,


1
X̂ = arg min
||Y − X ||2F + λR(X ) ,
(3)
X
2

3#
4#

where λ is a parameter to balance the loss function and the
low rank regularization induced by the nuclear norm R(X ),
which will be introduced in detail below.
(a) Original image

1#

(c) comparison of NNM, WNNM and WSNM

3#
4#
2#
(a) Original image

(c) comparison of NNM, WNNM and WSNM

(b) Initial image

(d) comparison of NNM, SNM and WSNM

Fig. 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.2N 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.

(b) 80% pixels misisng

(d) comparison of NNM, SNM and WSNM

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

2.2

i=1

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

min{m,n}
||X||w,* =
wi σi = Tr(W∆).
(7)
i=1

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,
X ∈ Rm×n , is

||X||w,Sp =

Definition 3. The Schatten p-norm [20] of a matrix X can be
represented by setting w = [1, 1, ..., 1] in Eq. (4),
1
X

 p1
min{m,n} p p
p
σi
||X||Sp =
= Tr((XT X) 2 ) . (6)

X

min{m,n}
i=1

wi σip

 p1

,

(4)

where 0 < p ≤ 1, and σi is the i-th singular value of X. w =
[w1 , ..., wmin{m,n} ], and wi ≥ 0 is a weight assigned to σi .
Definition 2. The weighted Schatten p-norm of X with power
p is
Xmin{m,n}
||X||pw,Sp =
wi σip = Tr(W∆p ),
(5)
i=1

where W and ∆ are diagonal matrices whose diagonal entries are
composed of wi and σi , respectively; Tr( ) calculates the trace of
the matrix in ( ).

Definition 5. A widely used standard nuclear norm [18] of a
matrix X can be represented by setting p=1 and w = [1, 1, ..., 1]
in Eq. (4),
Xmin{m,n}
1
(8)
||X||∗ =
σi = Tr((XT X) 2 ).
i=1

3

A NALYSING THE S PARSITY OF G ROUP BASED
R ANK M INIMIZATION

ON THE

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.

4

3.1

Adaptive dictionary learning

An adaptive dictionary learning method is now proposed,
that is, for each group X i , its adaptive dictionary can be
learned from its observation Y i ∈ Rd×m . Specifically, we
apply the SVD to Y i ,
X n1
Y i = U i Σi V Ti =
σi,j ui,j vTi,j ,
(9)

According to the above design of the adaptive dictionary
Di , we have the following theorem.
Theorem 1.

||Yi − Xi ||2F = ||Bi − Ai ||2F ,

(18)

where Yi = Di Bi and Xi = Di Ai .

j=1

where Σi = diag(σi,1 , σi,2 , ..., σi,n1 ) is a diagonal matrix,
n1 = min(d, m), and ui,j , vi,j are the columns of U i and V i ,
respectively.
Following this, we define each dictionary atom di,j of
the adaptive dictionary Di for each group Y i by:
di,j = ui,j vTi,j ,

j = 1, 2, ..., n1 .

(10)

Till now, we have learned an adaptive dictionary
Di = [di,1 , di,2 , ..., di,n1 ]

(11)

from each group 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.

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 Di ,
i.e.,


1
Âi = arg min
||Yi − Di Ai ||2F + λ||Ai ||1
Ai
2
m
(19)


1
||Yi − Xi ||2F + τ ||Xi ||∗ .
X̂i = arg min
Xi
2
Proof. See Appendix B.
Similar to Theorem 2, we have the following conclusion.

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


1
x̂ = arg min
||x − a||22 + τ ||x||1
x
2

Corollary 1. The weighted `1 -norm, `p -norm and weighted `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.

(12)

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.

(13)

3.3 Analyze the Sparsity of Group with the Nuclear
Norm Minimization

has a closed-form solution
x̂ = soft(a, τ ) = sgn(a)
where

max(abs(a) − τ, 0),

denotes the element-wise (Hadamard) product.

Proof. See [28].
Consider the SVD of a matrix X ∈ Rd×m with rank r
X = U ΣV T ,

Σ = diag({σi }1≤i≤r )

d×r

(14)

m×r

where U ∈ R
and V ∈ R
are orthogonal matrices;
σi is the i-th singular value of X. For any τ ≥ 0, the softthresholding operator Dτ is defined as

Dτ (X ) = U Dτ (Σ)V T ,

Dτ (Σ) = soft(σi , τ ).

(15)

Then, we have the following Lemma.
Lemma 2. For any τ ≥ 0, and Y ∈ Rd×m , the singular value
shrinkage operator in Eq. (15) satisfies


1
Dτ (Y) = arg min
||Y − X||2F + τ ||X||∗ .
(16)
X
2
Proof. See [18].
Recalling the adaptive dictionary defined in Eq. (11), the
classical `1 -norm group-based sparse coding problem can
be represented as


1
2
Âi = arg min
(17)
||Y i − Di Ai ||F + λ||Ai ||1 .
Ai
2

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.2N
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
`p -norm minimization problem.

5

4 G ROUP - BASED S PARSE C ODING FOR I MAGE
R ESTORATION WITH W EIGHTED `p - NORM M INIMIZA TION

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,
Y = HX + κ,

(20)

where H is a non-invertible linear degradation operator and
κ 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,

1
Â = arg min ||Y − HDA||22 + λ||WA||p ,
A 2

(21)

where W represents the weights in the weighted `p -norm
and λ is a regularization parameter.
4.1 ADMM based Algorithm for Weighted `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

Z∈RN ,A∈RM

f (Z) + g(A),

s.t.

Z = GA,

(22)

where G ∈ RM×N and f : RN → R, g : RM → R. The basic
ADMM regime is shown in Algorithm 1.
Algorithm 1 The ADMM Algorithm
Require: A and Z
1: Initial ρ > 0, b
2: for t = 0 to Max-Iter do
3:
Zt+1 = arg min f (Z) + ρ2 ||Z − GAt − bt ||22 .
Z

4:

At+1 = arg min g(A) + ρ2 ||Zt+1 − GA − bt ||22 .
t+1

t

5:
b
=b
6: end for

A

− (Zt+1 − GAt+1 ).

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,

1
Â = arg min ||Y − HZ||22 + λ||WA||p , s.t. Z = DA. (23)
Z,A 2
Following this, Eq. (23) can be transformed into three iterative steps:

1
ρ
Zt+1 = arg min ||Y − HZ||22 + ||Z − DAt − bt ||22 , (24)
Z 2
2
ρ
At+1 = arg min λ||WA||p + ||Zt+1 − DA − bt ||22 ,
(25)
A
2
bt+1 = bt − (Zt+1 − DAt+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 subproblem, 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

ρ
1
min Q1 (Z) = min ||Y − HZ||22 + ||Z − DA − b||22 . (27)
Z
Z 2
2
This is a quadratic form and has a closed-form solution,
Ẑ = (H T H + ρI)−1 (H T Y + ρ(DA + 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),
Ẑ = Z − η q,

(29)

where q is the gradient direction of the objective function
Q1 (Z), and η represents the step size. Thereby, in image CS
recovery, we only need an iterative calculation to solve the
Z sub-problem,
Ẑ = Z − η(H T HZ − H T Y + ρ(Z − DA − b)),

(30)

where H T H and H T Y can be pre-calculated.
4.1.2 A sub-problem
Given Z, the A sub-problem in Eq. (25) can be rewritten as

λ
1
min Q2 (A) = min ||DA − L||22 + ||WA||p ,
A
A 2
ρ

(31)

where L = Z − b.
However, due to the complicated structure of ||WA||p ,
it is difficult to solve Eq. (31). Let X = DA, Eq. (31) can be
rewritten as
1
λ
min L2 (A) = min ||X − L||22 + ||WA||p .
(32)
A
A 2
ρ
In order to achieve a tractable solution to Eq. (32), a general
assumption is made, and with which even a closed-form

6

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 E = X − L follows an independent zeromean Gaussian distribution with variance σ 2 . Provided this
assumption, we have the following theorem.
Theorem 3. Define x, l ∈ RN , Xi , Li ∈ Rd×m , and ej denoting
the j -th element of the error vector e ∈ RN , where e = x −
l. Assume that ej follows an independent zero mean Gaussian
distribution with variance σ 2 , and thus for any ε >
P 0, we can
1
represent the relationship between N
||x − l||22 and S1 ni=1 ||Xi −
Li ||2F by the following property,


1
1 Xn
2
2
||x − l||2 −
lim P
||Xi − Li ||F < ε = 1,
N →∞
i=1
N
S
S→∞
(33)
where P( ) represents the probability and S = d × m × 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,
1
1 Xn
||x − l||22 =
||X i − Li ||2F .
(34)
i=1
N
S
Now replacing x, l with {X , L}, along with Eq. (32), we
have
1
λ
min ||X − L||22 + ||WA||p
A 2
ρ

X
n
1
||X i − Li ||2F + τi ||W i Ai ||p
= min
(35)
i=1 2
Ai

X
n
1
||Li − Di Ai ||2F + τi ||W i Ai ||p ,
= min
i=1 2
Ai
where τi = λρiNS , Di is a dictionary, and here we abused the pnorm for matrix. Clearly, Eq. (35) can be viewed as a sparse
coding problem by solving n sub-problems for each group
X i . Based on Theorem 1, Eq. (35) can be rewritten as:

X
n
1
||Ri − Ai ||2F + τi ||W i Ai ||p
Âi = min
i=1 2
Ai
X

(36)
n
1
2
||γ i − αi ||2 + τi ||wi αi ||p ,
= min
i=1 2
αi
where X i = Di Ai and Li = Di Ri ; αi , γ i and wi denote the
vectorization of the matrix Ai , Ri and W i , respectively.
Therefore, the minimization problem of Eq. (31) can be
simplified to solve the minimization problem in Eq. (36).

4.2 Generalized Soft-Thresholding (GST) Algorithm for
Weighted `p -norm Minimization
The generalized soft-thresholding (GST) algorithm [39] is
employed to solve Eq. (36). Specifically, given p, γi,j and
wi,j , there exists a specific threshold,
1

p−1

τpGST (wi,j ) = (2wi,j (1 − p)) 2−p + wi,j p(2wi,j (1 − p)) 2−p ,
(37)
where γi,j , αi,j and wi,j are the j -th element of γ i , αi
and wi , respectively. Then, if γi,j < τpGST (wi,j ), αi,j = 0
is the global minimum. Otherwise, the optimum will be
obtained at a non-zero point. According to [39], for any
γi,j ∈ (τpGST (wi,j ), +∞), Eq. (36) has one unique minimum

Algorithm 2 Generalized Soft-Thresholding (GST) Algorithm [39].
Require: γi,j , wi,j , p, K
p−1
1
1: τpGST (wi,j ) = (2wi,j (1 − p)) 2−p + wi,j p(2wi,j (1 − p)) 2−p .

|γi,j | ≤ τpGST (wi,j ) then
T GST
p (γi,j ; wi,j ) = 0;
else
k = 0, αi,j (k) = |γi,j |
for k = 0 to K do
p−1

.
αi,j (k+1) = |γi,j | − wi,j p αi,j (k)
GST
(k)
T p (γi,j ; wi,j ) = sgn(γi,j )αi,j .
end for
end if
Output: T GST
p (γi,j ; wi,j )

2: if
3:
4:
5:
6:
7:
8:
9:
10:
11:

T GST
p (γi,j ; wi,j ), which can be obtained by solving the following equation,

p−1
GST
T GST
(γ
;
w
)−γ
+w
p
T
(γ
;
w
)
= 0. (38)
i,j
i,j
i,j
i,j
i,j
i,j
p
p
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

αi,j = GST(γi,j , τi,j wi,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 αi,j 3 + γi,j 2 αi,j − 2γi,j αi,j 2 − τi,j 2 wi,j 2 /4 = 0. Similarly,
for the case of p = 2/3, the closed-form solution of Eq. (36)
can be solved by αi,j 4 + 3γi,j 2 αi,j 2 − 3γi,j αi,j 3 − γi,j 3 αi,j +
8τi,j 3 wi,j 3 /27 = 0 [55].
Algorithm 3 ADMM for weighted `p -norm minimization
Require: The observed image Y and the measurement matrix H.
1: Initial t, b, Z, α, C, K, d, m, ρ, p, σ ,  and ε.
2: for t = 0 to Max-Iter do
3:
if H is mask operator then
4:
Update Zt+1 by Eq. (28);
5:
else if H is random projection operator then
6:
Update Zt+1 by Eq. (30);
7:
end if
8:
for Each group Li do
9:
Construct dictionary Di by computing Eq. (10);
10:
Update λi t+1 by computing Eq. (41);
11:
Update τit+1 computing by τi = λρiNS ;
12:
Update wt+1
by computing Eq. (40);
i
13:
Update Ai t+1 computing by Eq. (39);
14:
end for
15:
Update Dt+1 by concatenating all Di .
16:
Update At+1 by concatenating all αi .
17:
Update bt+1 by computing Eq. (26).
18: end for
19: Output: The final restored image X̂ = DA.

7

5.1

Fig. 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 αi usually depict major edge
and texture information [16], in order to reconstruct X i from
its degraded one, we should shrink the larger values less,
while shrinking smaller ones more. Therefore, we let

1
,
(40)
|γ i | + 
with  as a small positive constant.
The regularization parameter λ that balances the fidelity
term and the regularization term should be adaptively determined for better reconstruction performance. Inspired by
[40], λi of each group Li is set as:
√
2 2σ 2
λi =
,
(41)
δi + ε
where δi denotes the estimated variance of γ i , and ε is a
small positive constant.
After solving the two sub-problems, we summarize the
overall algorithm for Eq. (21) in Algorithm 3.
wi =

TABLE 1
Detailed setting of ρ, λ for inpainting and CS recovery with proposed
adaptive dictionary learning approach.
ADL
Parameters
80%
70%
60%
50%
ADL
Parameters
0.2
0.3
0.4
0.5

5

Image Inpainting
`p -norm
ρ
λ
0.006
0.07
0.008
0.07
7e-5
3e-6
0.0001
7e-6
Image CS Recovery
`1 -norm
`p -norm
ρ
λ
ρ
λ
0.001
5e-5
0.003
5e-4
0.003
7e-4
0.01
3e-4
0.003
5e-4
0.006
3e-4
0.003
5e-4
0.006
3e-4
`1 -norm
ρ
λ
7e-5
5e-6
1e-4
7e-6
1e-5
1e-6
5e-5
1e-5

w`1 -norm
ρ
0.1
0.1
0.1
0.1

w`p -norm
ρ
0.0003
0.0003
0.03
0.04

w`1 -norm
ρ
0.1
0.1
0.1
0.2

w`p -norm
ρ
0.0005
0.05
0.05
0.05

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 × 8. The similar patch number
m is √
set to 60. The searching window C × C is set to 25 × 25;
σ = 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. 
and ε are set as 0.35, 0.35 and 0.1, 0.3 for w`1 -norm and
w`p -norm, respectively. The detailed settings of ρ and λ are
shown on the upper part of Table 1. However, due to the
existence of the weight W, λ is computed by Eq. (41) in
w`1 -norm and w`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 × 32 [29].
The patch size is set to be 7 × 7. The similar patch number
√
m = 60, and the search window is set to 20 × 20; σ = 2
and K = 2; p is set to 0.5, 0.95, 0.95 and 0.95 with 0.2N ,
0.3N , 0.4N and 0.5N measurements, respectively.  and ε
are set as 0.35, 0.35 and 0.1, 0.4 for w`1 -norm and w`p -norm,
respectively. Similarly, λ is computed by Eq. (41) in w`1 norm and w`p -norm. The detailed settings of ρ and λ are
shown at the lower part of Table 1.
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.

(a)

(b)

(c)

(d)

(e)

(f)

E XPERIMENTAL R ESULTS

To demonstrate the feasibility of the proposed scheme, in
this section, we report extensive experiments to evaluate the
performance of the proposed weighted `p -norm (w`p -norm)
minimization and compare it with many existing norm
minimization methods, including `1 -norm minimization,
weighted `1 -norm (w`1 -norm) minimization, and `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.

Fig. 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) `1 -norm (PSNR= 25.97dB);
(d) `p -norm (PSNR= 26.74dB); (e) w`1 -norm (PSNR= 26.66dB); (f) w`p norm (PSNR= 26.92dB).

5.2 Comparisons of `1 -norm, Weighted `1 -norm, `p norm and Weighted `p -norm
We firstly compare four norm minimization methods, i.e.,
`1 -norm minimization, w`1 -norm minimization, `p -norm
(a) Original Image

(b) Degraded image

(c) GSR-L1 (25.97dB)

8

(a)

(b)

recovery are shown in Table 2 and Table 3, respectively. It
can be seen that the w`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.2N measurements. We can observe
that the w`p -norm obtains better perceptual quality than
other three norms. Therefore, these experimental results are
consistent with our theoretical analysis.

(c)

TABLE 4
Detailed setting of ρ, λ for inpainting and CS recovery, with the
graph-based dictionary learning [41] and PCA dictionary learning [42].

(d)

(e)

(f)

Fig. 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) `1 -norm (PSNR= 24.11dB); (d) `p -norm (PSNR= 24.82dB); (e) w`1 norm (PSNR= 24.82dB); (f) w`p -norm (PSNR= 25.06dB).

minimization and w`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

Graph
Parameters
80%
70%
60%
50%
PCA
Parameters
0.2
0.3
0.4
0.5

Image Inpainting
`1 -norm
`p -norm
ρ
λ
ρ
λ
0.008
1e-5
0.003
7e-5
0.003
1e-5
0.003
7e-5
0.006
7e-5
0.003
5e-5
0.003
7e-5
0.003
9e-5
Image CS Recovery
`1 -norm
`p -norm
ρ
λ
ρ
λ
0.03
1e-6
0.003
7e-5
0.008
1e-6
0.006
7e-5
0.008
1e-6
0.008
1e-5
0.008
1e-6
0.008
1e-5

w`1 -norm
ρ
0.15
0.1
0.07
0.05

w`p -norm
ρ
0.06
0.05
0.09
0.05

w`1 -norm
ρ
0.09
0.07
0.05
0.05

w`p -norm
ρ
0.07
0.09
0.05
0.05

Next, in order to prove the universality of the proposed
scheme, instead of using the proposed ADL method, we

TABLE 2
PSNR (dB) comparison of `1 -norm, `p -norm, w`1 -norm and w`p -norm, based on the proposed ADL scheme for image inpainting.
Miss pixels
Methods
Butterfly
(a) Original Image
(b) GSR-L1
(24.11dB)Mickey
(c) GSR-Lp
(24.82dB)Fence
`1 -norm
25.97
25.61
28.90
`p -norm
26.74
26.36
29.47
80%
w`1 -norm
26.66
26.39
29.98
w`p -norm
26.92
26.52
30.00
`1 -norm
27.86
27.86
30.72
`p -norm
29.04
29.10
31.54
70%
w`1 -norm
29.16
29.21
31.83
w`p -norm
29.29
29.28
31.85
`1 -norm
29.61
29.82
32.29
`p -norm
29.85
30.16
32.51
60%
(d) GSR-WL1 (24.82dB)
(e) GSR-WLp(25.06dB)
w`1 -norm
31.44
31.40
33.65
w`p -norm
31.46
31.54
33.67
`1 -norm
31.62
31.46
33.78
`p -norm
31.88
31.78
33.97
50%
w`1 -norm
33.98
33.16
35.30
w`p -norm
34.01
33.26
35.25

Starfish
26.98
27.54
28.00
28.05
29.02
30.25
30.54
30.56
30.78
31.14
32.93
33.02
32.62
32.99
34.99
35.05

Nanna
25.46
25.87
25.73
25.95
27.32
28.31
28.07
28.39
29.02
29.22
30.42
30.56
30.68
30.89
32.38
32.53

Zebra
22.33
23.05
22.39
23.06
24.26
25.19
24.82
25.13
25.93
26.13
27.04
27.21
27.65
27.86
29.12
29.26

fireman
25.39
25.63
25.68
25.80
27.05
27.69
27.81
27.84
28.53
28.69
29.74
29.77
30.13
30.28
31.31
31.32

Golem
25.29
25.69
26.12
26.26
27.40
28.37
28.53
28.62
28.93
29.16
30.27
30.35
30.48
30.70
31.88
31.91

Average
25.74
26.29
26.37
26.57
27.69
28.69
28.75
28.87
29.36
29.61
30.86
30.95
31.05
31.29
32.76
32.82

TABLE 3
PSNR (dB) comparison of `1 -norm, `p -norm, w`1 -norm and w`p -norm, based on the proposed ADL scheme for image CS Recovery.
Ratio

(a) Original Image

Methods
Barbara bridge elaine
`1 -norm
32.24
25.03
34.59
`p -norm
34.31
25.13
35.75
0.2
w`1 -norm
34.53
25.04
36.22
w`p -norm
34.55
25.28
36.00
`1 -norm
34.49
26.49
36.76
`p -norm
34.86
26.59
37.07
0.3
w`1 -norm
37.10
27.25
38.26
w`p -norm
37.23
27.22
38.30
`1 -norm
36.79
27.94
38.58
`p -norm
37.15
28.06
38.87
0.4
w`1 -norm
39.04
28.90
40.03
(b) GSR-NNM
(24.11dB)
w`p -norm
39.13 (c) GSR-SNM
28.85 (24.82dB)
40.05
`1 -norm
38.80
29.38
40.26
`p -norm
39.19
29.51
40.54
0.5
w`1 -norm
40.84
30.51
41.52
w`p -norm
40.94
30.52
41.63

Fence
29.31
29.99
30.19
30.38
31.16
31.42
32.50
32.53
32.84
33.09
34.50
34.42
34.50
34.75
36.29
36.24

House
36.01
37.15
37.07
36.92
37.94
38.29
39.07
39.23
39.70
39.98
40.82
40.93
41.27
41.52
42.25
42.38

lena
30.77
31.50
31.49
31.62
32.97
33.15
34.26
34.29
34.76
34.95
36.58
36.66
36.56
36.78
38.99
39.09

peppers
30.00
30.79
31.22
31.32
31.93
32.22
33.39
33.32
33.63
33.91
35.10
35.00
35.18
35.43
36.56
36.53

straw
24.11
24.82
24.82
25.06
26.11
26.23
27.84
27.89
27.95
28.10
30.30
30.28
29.88
30.07
32.49
32.46

Average
30.26
31.18
31.32
31.39
32.23
32.48
33.71
33.75
34.03
34.26
35.66
35.67
35.73
35.97
37.43
37.47

9

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 ρ and λ, which
are now shown in Table 4. The PSNR comparison results for
image inpainting of four competing methods are shown in
Table 5. It can be observed that the w`p -norm consistently
outperforms the other three norms for most testing images
(the only exception is the image Zebra for which the w`1 norm is slightly higher than the w`p -norm in the scene
of 80% and 70% pixels missing). The PSNR comparison
results of image CS recovery are shown in Table 6, and we
can observe that the w`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.2N measurements
for image CS recovery based on PCA dictionary learning
method is shown in Fig. 8. It is clearly demonstrated that
the w`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`p -norm are usually a little bit (∼0.1dB)
better than those of w`1 -norm, which has also been observed
in [21]. Similar phenomenons can also be found between
`p -norm and `1 -norm. In addition, comparing Tables 5-6
with Tables 2-3, 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.
5.3

(a)

(b)

(c)

(d)

(e)

(f)

Fig. 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) `1 -norm (PSNR=
22.92dB); (d) `p -norm (PSNR= 25.83dB); (e) w`1 -norm (PSNR=
26.67dB); (f) w`p -norm (PSNR= 26.99dB).

(a)

(b)

(c)

Comparison with Other Leading Algorithms

We now validate the performance of the proposed scheme,
i.e., group-based sparse coding with non-convex w`p -norm
(c) (b) Degraded image (d) (c) Graph-NNM (22.92dB)
(e)
(a) Original Image
(GSC-w`p ) minimization for image inpainting and image Fig. 8. CS recovery performance comparison with 0.2N measurements
CS recovery with the proposed adaptive dictionary learning on the image peppers based on PCA dictionary learning method. (a)
method, by comparing it with recent state-of-the-art meth- Original image; (b) Initial image by [29] (PSNR= 28.61dB); (c) `1 norm (PSNR= 30.08dB); (d) `p -norm (PSNR= 30.87dB); (e) w`1 -norm
ods.
(PSNR= 31.10dB); (f) w`p -norm (PSNR= 31.31dB).

TABLE 5
PSNR (dB) comparison of `1 -norm, `p -norm, w`1 -norm and w`p -norm, based on the graph-based dictionary learning method for image inpainting.
Miss pixels
80%

70%

60%

50%

Methods
`1 -norm
`p -norm
w`1 -norm
w`p -norm
`1 -norm
`p -norm
w`1 -norm
w`p -norm
`1 -norm
`p -norm
w`1 -norm
w`p -norm
`1 -norm
`p -norm
w`1 -norm
w`p -norm

Mickey
24.63
25.20
25.30
25.40
26.31
27.21
27.37
27.49
27.58
27.72
28.79
28.80
29.14
29.31
30.68
30.71

Butterfly
23.62
24.51
24.63
24.74
25.75
26.88
27.00
27.19
27.50
27.66
28.84
28.91
29.24
29.40
30.62
30.69

Fence
Starfish
Nanna
Zebra (26.67dB)
fireman (f)
Golem
Average
(d) Graph-SNM
(25.83dB)
(e) Graph-WNNM
Graph-WSNM(26.99dB)
22.92
26.27
25.52
20.45
24.59
23.57
23.82
25.83
26.41
24.79
20.79
24.88
24.31
24.59
26.67
26.20
24.75
20.98
24.88
24.44
24.73
26.99
26.43
24.92
20.97
25.00
24.60
24.88
25.06
28.07
26.21
21.84
26.08
25.33
25.58
28.27
28.33
26.58
22.43
26.50
26.43
26.58
28.89
27.92
26.58
22.80
26.55
26.65
26.72
29.12
28.50
26.81
22.77
26.77
26.84
26.93
27.48
29.46
27.61
23.37
27.38
26.80
27.15
28.09
29.47
27.65
23.46
27.41
26.93
27.30
30.74
29.68
28.22
24.72
28.05
28.39
28.43
30.79
29.81
28.29
24.75
28.11
28.45
28.49
29.73
30.93
29.13
24.84
28.78
28.37
28.77
30.24
30.86
29.12
24.98
28.80
28.50
28.90
32.65
31.51
29.76
26.61
29.64
30.04
30.19
32.71
31.56
29.82
26.62
29.70
30.08
30.24
(a) Original Image
(b) PCA-NNM (30.08dB)
(c) GSR-SNM (30.87dB)

10

TABLE 6
PSNR (dB) comparison of `1 -norm, `p -norm, w`1 -norm and w`p -norm, based on PCA dictionary learning scheme for image CS Recovery.
Ratio
0.2

0.3

0.4

0.5

Methods
`1 -norm
`p -norm
w`1 -norm
w`p -norm
`1 -norm
`p -norm
w`1 -norm
w`p -norm
`1 -norm
`p -norm
w`1 -norm
w`p -norm
`1 -norm
`p -norm
w`1 -norm
w`p -norm

Barbara
32.13
34.07
32.89
34.09
34.38
34.50
35.53
35.69
36.69
37.03
37.63
37.74
38.72
39.09
39.53
39.64

bridge
25.05
25.24
25.25
25.29
26.53
26.60
26.95
27.04
28.01
28.13
28.39
28.45
29.46
29.60
29.95
30.00

elaine
34.60
35.74
33.32
35.74
36.80
36.84
34.94
37.25
38.65
38.92
39.03
39.11
40.32
40.59
40.59
40.67

Fence
29.12
29.87
29.87
30.14
31.08
31.19
31.73
31.84
32.84
33.09
33.43
33.51
34.55
34.80
35.13
35.21

In image inpainting, we compare GSC-w`p with five
other competing methods: SALSA [43], BPFA [44], IPPO
[45], JSM [46] and Aloha [47]. Table 7 lists the PSNR results
for a collection of 8 color images for these five methods.
The average gains of the proposed GSC-w`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`p not only preserves sharp
edges and fine details, but also eliminates the ringing effects.

(a)

(b)

(c)

(d)

(e)

(f)

(g)

(h)

Fig. 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`p (PSNR= 23.06dB).

In image CS recovery, we compare the proposed GSCw`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 re(d)
(a) shown in Table
(b) 8. The proposed
(c) GSC-w`p achieves
sults are
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`p are slightly lower
than AMP-FBM3D method, the AMP-FBM3D method is
(e)

(f)

(g)

(h)

House
35.92
36.76
36.23
36.75
38.05
38.04
38.04
38.07
39.80
40.07
39.75
39.84
41.36
41.59
41.25
41.33

lena
30.78
31.46
31.23
31.48
33.03
33.09
33.69
33.80
34.83
35.04
35.46
35.57
36.64
36.88
37.45
37.56

peppers
30.08
30.87
31.10
31.31
32.10
32.24
32.99
33.06
33.85
34.10
34.59
34.65
35.45
35.66
36.09
36.14

straw
24.10
24.74
24.50
24.89
26.09
26.18
27.05
27.28
27.96
28.10
29.07
29.21
29.89
30.07
31.16
31.30

(a)

(b)

(c)

(f)

(g)

(h)

Average
30.22
31.10
30.55
31.21
32.26
32.34
32.61
33.01
34.08
34.31
34.67
34.76
35.80
36.03
36.39
36.48

(d)

(i)

(e)

(j)

Fig. 10. CS recovery of Barbara with 0.2N 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`p (PSNR= 34.55dB).

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`p can outperform AMPFBM3D 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
(d)
(a)
(b)
(c)
pre-filtering BM3D. The visual comparison of image Barbara
with 0.2N 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 undesir(h)
(e)
(f)
(g)
able artifacts or over-smooth phenomena. By contrast, the
proposed GSC-w`p not only removes most of the visual
artifacts, but also preserves large-scale sharp edges and
small-scale fine image details.
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`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.2N
measurements, respectively. The results with different m are

11

TABLE 7
PSNR (dB) comparison of SALSA [43], BPFA [44], IPPO [45], JSM [46], ALoha [47] and GSC-w`p for image inpainting.
Miss pixels

80%

70%

60%

50%

Methods
SALSA [43]
BPFA [44]
IPPO [45]
JSM [46]
Aloha [47]
GSC-w`p
SALSA [43]
BPFA [44]
IPPO [45]
JSM [46]
Aloha [47]
GSC-w`p
SALSA [43]
BPFA [44]
IPPO [45]
JSM [46]
Aloha [47]
GSC-w`p
SALSA [43]
BPFA [44]
IPPO [45]
JSM [46]
Aloha [47]
GSC-w`p

Mickey
24.46
24.53
26.33
26.09
25.33
26.92
25.98
26.16
28.59
28.25
27.11
29.29
27.41
27.83
30.76
29.85
28.59
31.46
28.98
29.43
32.74
31.96
30.33
34.00

Butterfly
22.85
24.04
25.13
25.57
24.88
26.52
25.06
26.68
27.68
27.97
27.29
29.28
26.79
28.88
29.85
29.83
29.16
31.54
28.52
30.98
31.69
31.47
30.78
33.26

Fence
21.80
26.24
27.98
28.59
28.88
30.00
23.57
28.87
30.08
30.46
30.57
31.85
25.45
30.79
32.14
32.23
32.33
33.67
27.25
32.82
33.95
33.75
33.79
35.25

Starfish
25.70
26.79
26.30
27.07
26.33
28.05
27.55
28.93
28.91
29.36
28.22
30.56
29.09
30.98
31.09
31.40
30.19
33.02
30.90
33.13
33.10
33.24
31.85
35.05

Nanna
24.12
24.71
25.60
25.33
25.54
25.95
25.44
26.62
27.44
27.34
27.43
28.39
26.94
28.63
29.41
29.09
29.51
30.56
28.53
30.68
31.17
30.75
31.24
32.53

Zebra
19.68
20.90
22.71
21.88
22.72
23.06
21.41
22.78
24.76
23.95
24.55
25.13
22.80
24.53
26.79
25.90
26.24
27.21
24.42
26.37
28.42
27.77
27.67
29.26

fireman
24.38
24.88
25.56
25.31
25.03
25.80
25.82
26.55
27.44
27.16
26.52
27.84
27.15
28.23
29.13
28.79
28.24
29.77
28.54
30.12
30.82
30.37
29.88
31.32

Golem
23.15
24.13
25.66
25.40
25.23
26.26
25.00
26.46
27.92
27.59
27.33
28.61
26.66
28.30
29.57
29.24
28.92
30.35
28.20
30.46
31.11
30.89
30.28
31.91

Average
23.27
24.53
25.66
25.65
25.49
26.57
24.98
26.63
27.85
27.76
27.38
28.87
26.54
28.52
29.84
29.54
29.15
30.95
28.17
30.50
31.63
31.27
30.73
32.82

TABLE 8
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`p
for image CS recovery.
Ratio

0.2

0.3

0.4

0.5

Methods
BCS [48]
BM3D-CS [49]
ADS-CS [50]
ALSB [51]
SGSR [52]
MRK [59]
JASR [53]
AMP-FBM3D [58]
GSC-w`p
BCS [48]
BM3D-CS [49]
ADS-CS [50]
ALSB [51]
SGSR [52]
MRK [59]
JASR [53]
AMP-FBM3D [58]
GSC-w`p
BCS [48]
BM3D-CS [49]
ADS-CS [50]
ALSB [51]
SGSR [52]
MRK [59]
JASR [53]
AMP-FBM3D [58]
GSC-w`p
BCS [48]
BM3D-CS [49]
ADS-CS [50]
ALSB [51]
SGSR [52]
MRK [59]
JASR [53]
AMP-FBM3D [58]
GSC-w`p

Barbara
24.24
28.83
32.27
30.72
33.44
27.99
34.16
33.66
34.55
25.59
33.00
35.81
35.00
35.91
32.64
36.59
36.41
37.23
27.10
35.92
38.34
38.34
37.70
36.17
37.39
38.34
39.13
28.67
38.43
40.19
39.26
39.38
38.98
40.31
40.12
40.94

Bridge
23.61
23.77
25.39
24.97
24.72
25.70
25.18
25.00
25.28
25.00
26.59
27.36
26.83
26.80
27.62
27.19
26.97
27.22
26.31
28.52
29.40
29.10
28.46
29.24
28.69
28.82
28.85
27.64
30.68
30.83
30.03
30.09
31.01
30.30
30.68
30.52

Elaine
31.18
33.75
35.78
32.56
34.85
35.94
35.66
36.14
36.00
33.68
37.23
37.91
34.30
36.87
38.40
36.83
38.25
38.30
35.66
39.23
39.50
39.60
38.63
40.02
38.28
39.74
40.05
37.51
41.01
40.92
41.18
40.07
41.61
39.47
41.31
41.63

Fence
21.57
22.57
28.37
28.41
29.42
22.20
29.95
30.15
30.38
23.24
30.68
31.29
30.83
31.56
24.44
31.87
33.05
32.53
24.81
33.83
34.02
32.83
33.34
26.63
33.96
35.42
34.42
26.20
36.21
36.20
34.81
35.28
29.60
35.72
37.45
36.24

House
30.54
35.04
35.76
36.08
35.81
36.36
35.88
37.75
36.92
32.85
36.84
38.21
38.34
37.37
38.35
38.04
39.92
39.23
34.65
38.08
40.30
40.25
38.99
40.04
38.80
41.63
40.93
36.29
40.34
41.86
41.93
40.56
41.46
41.44
43.37
42.38

Lena
28.15
30.30
33.92
30.68
30.89
32.58
31.19
34.86
31.62
30.16
35.01
37.20
33.36
33.27
35.69
34.05
38.01
34.29
32.06
38.46
39.63
35.47
35.68
38.14
36.12
40.60
36.66
33.78
39.19
41.60
37.79
37.90
39.99
38.33
42.72
39.09

Peppers
27.15
31.09
31.01
29.96
30.51
31.83
31.06
31.74
31.32
29.05
33.62
33.26
32.37
32.71
33.91
33.09
33.75
33.32
30.77
35.20
34.96
34.44
34.47
35.50
34.70
35.20
35.00
32.31
36.80
36.46
36.21
35.97
36.97
36.22
36.55
36.53

Straw
20.69
20.04
23.74
24.33
24.54
23.02
24.95
23.28
25.06
22.19
22.37
26.58
26.61
27.33
25.52
27.87
26.24
27.89
23.71
24.38
28.80
28.54
29.63
27.69
30.04
28.32
30.28
25.30
26.94
30.88
30.61
31.71
30.11
32.04
29.99
32.46

Average
25.89
28.17
30.78
29.71
30.52
29.45
31.00
31.57
31.39
27.72
31.92
33.45
32.21
32.73
32.07
33.19
34.07
33.75
29.38
34.20
35.59
34.58
34.61
34.18
34.75
36.01
35.67
30.96
36.20
37.37
36.48
36.37
36.22
36.73
37.77
37.47

12

(a)

(b)

Fig. 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.2N measurements.

shown in Fig. 11. It can be seen that all the curves are almost
flat, showing the performance of the proposed GSC-w`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`p in Eq. (21) for CS image
reconstruction. We perform a comparison between ADMM
and IST with 0.2N and 0.3N 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`p than IST.

(a)

(a)

(b)

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

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

C ONCLUSION

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

(b)

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

A PPENDIX A
P ROOF OF THE T HEOREM 1
Proof. The adaptive dictionary Di is constructed by Eq. (10).
From the unitary property of U i and V i , we have

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
Peppers, House, Fence and Lena) with 0.2N measurements as
well as image inpainting with 80% pixels missing for image
Mickey, Starfish, Nanna and Golem, respectively. It can be seen
that with the increase of the iteration number, the PSNR

||Y i − X i ||2F = ||Di (Bi − Ai )||2F = ||U i diag(Bi − Ai )V i ||2F
= Tr(U i diag(Bi − Ai )V i V Ti diag(Bi − Ai )U Ti )
= Tr(U i diag(Bi − Ai )diag(Bi − Ai )U Ti )
= Tr(diag(Bi − Ai )U i U Ti diag(Bi − Ai ))
= Tr(diag(Bi − Ai )diag(Bi − Ai ))
= ||Bi − Ai ||2F ,
where X i = Di Ai and Y i = Di Bi .

(42)

13

Therefore, the same process applied to e2s yields
lim P{| 1S ΣSs=1 e2s − σ 2 | < 2ε } = 1, i.e.,

A PPENDIX B
P ROOF OF THE T HEOREM 2

S→∞

Proof. On the basis of Theorem 1, we have


1
Âi = arg min
||Y i − Di Ai ||2F + λ||Ai ||1
Ai
2


1
2
= arg min
||Bi − Ai ||F + λ||Ai ||1
Ai
2


1
||β i − αi ||22 + λ||αi ||1 ,
= arg min
αi
2

1
ε
lim P{| Σni=1 ||X i − Li ||2F − σ 2 | < } = 1.
S
2

S→∞

(43)

max(abs(β i ) − λ, 0). (44)

Obviously, according to Eqs. (9) and (10), we have
X n1
Di Âi =
soft(β i,j , λ)di,j
j=1
X n1
soft(β i,j , λ)ui,j vTi,j
=

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

R EFERENCES

where X i = Di Ai and Y i = Di Bi . αi and β i denote the
vectorization of the matrix Ai and Bi , respectively.
Thus, based on Lemma 1, we have

αi = soft(β i , λ) = sgn(β i )

[1]
[2]
[3]
[4]

(45)

[5]

j=1

= U i Dλ (Σi )V Ti ,

[6]

where β i,j represents the j -th element of the i-th group
sparse coefficient β i , and Σi is the singular value matrix
of the i-th group 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.


1
||Y i − Di Ai ||2F + λ||Ai ||1
Âi = arg min
Ai
2
m
(46)


1
X̂ i = arg min
||Y i − X i ||2F + τ ||X i ||∗ .
Xi
2

[7]

[8]
[9]
[10]
[11]
[12]

A PPENDIX C
P ROOF OF THE T HEOREM 3

[13]

Proof. Owing to the assumption that ej follows an independent zero mean Gaussian distribution with variance σ 2 ,
namely, E[ej ] and Var[ej ] = σ 2 , it can be deduced that each
ej 2 is also independent, and the mean of each ej 2 is
E[e2j ] = Var[ej ] + [E[ej ]]2 = σ 2 ,

j = 1, 2, ..., N.

1

lim P{| ||x − l||22 − σ 2 | < } = 1.
N
2

[14]

[15]

(47)

By invoking the law of large numbers in probability the
2
2
ory, for any  > 0, it leads to lim P{| N1 ΣN
j=1 ej − σ | < 2 } =
N→∞
1, namely,
N→∞

(49)

[16]
[17]

(48)

Next, we denote the concatenation of all the groups X i
and Li , i = 1, 2, ..., n, by X and L, respectively. Meanwhile, we denote the error of each element of X − L by
es , s = 1, 2, ..., S. We have also assumed es following an
independent zero mean Gaussian distribution with variance
σ2 .

[18]
[19]

[20]

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.
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.
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.
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.
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.
Mairal J, Ponce J, Sapiro G, et al. Supervised dictionary learning[C]//Advances in neural information processing systems.
2009: 1033-1040.
Wen B, Ravishankar S, Bresler Y. Structured overcomplete sparsifying transform learning with convergence guarantees and applications[J]. International Journal of Computer Vision, 2015, 114(23): 137-167.
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.
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.
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.
Lun D P K. Robust fringe projection profilometry via sparse
representation[J]. IEEE Transactions on Image Processing, 2016,
25(4): 1726-1739.
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.
Zhang J, Zhao D, Gao W. Group-based sparse representation for
image restoration[J]. IEEE Transactions on Image Processing, 2014,
23(8): 3336-3351.
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(23): 217-232.
Q. Wang, X. Zhang, Y. Wu, L. Tang and Z. Zha, ”Nonconvex
Weighted ellp Minimization Based Group Sparse Representation
Framework for Image Denoising,” in IEEE Signal Processing Letters, vol. 24, no. 11, pp. 1686-1690, Nov. 2017.
Candes E J, Wakin M B, Boyd S P. Enhancing sparsity by
reweighted `1 minimization[J]. Journal of Fourier analysis and
applications, 2008, 14(5): 877-905.
Cands 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): 489509.
Cai J F, Cands E J, Shen Z. A singular value thresholding algorithm
for matrix completion[J]. SIAM Journal on Optimization, 2010,
20(4): 1956-1982.
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.
Nie F, Huang H, Ding C H Q. Low-Rank Matrix Recovery via
Efficient Schatten p-Norm Minimization[C]//AAAI. 2012.

14

[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: 883888.
[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. L1 -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. Users 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 lowrank 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 graphbased 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): 24192434.
[55] Krishnan D, Fergus R. Fast image deconvolution using hyperLaplacian 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] Cands 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.

