Sage Journals: Discover world-class research

Abstract

Recently, a sparse representation model - called an analysis sparse model - where the signal is multiplied by an analysis dictionary and the outcome is assumed to be sparse, has received increasing attention since it has potential and extensive applications in the area of signal processing. The performance of the analysis model significantly depends on an appropriately chosen dictionary. Most existing analysis dictionary learning algorithms are based on the assumption that the original signals are known or can be estimated from their noisy versions. Generally, however, the original signals are unknown or need to be estimated by using greedy-like algorithms with heavy computation. To solve the problems, we introduce a subset pursuit algorithm for analysis dictionary learning, where the observed signals are directly employed to learn the analysis dictionary. Next, a weighted split Bregman iteration algorithm is proposed to estimate original signals by the learned analysis dictionary. The experimental results demonstrate the competitive performance of the proposed algorithms compared with the state-of-art algorithms.

Keywords

Sparse representation synthesis model analysis model dictionary learning image denoising

1. Introduction

Sparse representation has become a well-known topic in a wide range of fields, such as image processing [1], compressed sensing [2], sensor networks [3], robotics [4, 5, 6, 7, 8], and more. A popular model for sparse representation is the synthesis model. In this model, a signal x ∊ R^M is represented as x = Da, where D ∊ R^MxN is a possibly over-complete dictionary (N ≥ M) and a ∊ R^N is the coefficient vector which is assumed to be sparse, i.e., ∥ a ∥₀ = L ≪ N, where the ℓ₀ quasi-norm ∥ · ∥ ₀ counts the number of non-zero components in its argument. In the synthesis model, the signal x can be described as a linear combination of only a few columns (i.e., atoms) of D. In the past decade, the synthesis model has been extensively studied [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]. In robotics, face recognition is used to satisfy person identification tasks and sparse representation-based classification can deal with facial recognition very well. The basic idea is to combine the sub-dictionaries which are learned from various classes’ images and then represent the query image using a small number of atoms indicating the class of the image [5]. Sparse representation-based classification can also be applied to action recognition for human-robot interaction [6, 7] and object classification for robot perception [8].

Recently, an alternative form of the sparse representation model called the ‘analysis model’ was proposed in [13, 14, 15, 16, 17, 18, 19, 20, 21]. In this model, an analysis dictionary (or analysis operator) Ω ∊ R^PxM (P ≥ M) is sought in order to transform the signal vector x to a high-dimensional space, i.e., Ωx = z, where the analysis coefficient vector z ∊ R^P is the analysis representation of x and is assumed to be sparse, i.e., ∥ z ∥₀ ≪ P, while the total number of the zeros of z characterizes co-sparsity [13]. In the model, the signal x is described by the zero elements of z - in other words, zero entries in z define a subspace that the signal x belongs to as opposed to the few non-zero entries of a in the synthesis model.

Similar to the synthesis model, the performance of the analysis model relies on the sparse representation of the signals with an appropriately chosen dictionary and a signal recovery method. Compared to the extensive studies of synthesis dictionary learning, however, the problem of analysis dictionary learning (ADL) has received much less attention, with only a few algorithms proposed recently [15, 16, 17, 18, 20, 21]. Based on the fact that a row of Ω is orthogonal to a subset X_j of signals X, where X=[x₁,x₂, …, x_K] ∊ R^MxK, a sequential minimal eigenvalue algorithm has been proposed for ADL [15]. Once X, is found, the corresponding j -th row of the dictionary can be updated with the eigenvector associated with the smallest eigenvalue of the Gram matrix of X_j. However, the computational cost of this ADL method increases considerably if P becomes larger. In fact, the original signals X cannot be accurately observed. In[17, 16], a projected sub-gradient algorithm is proposed for analysis operator learning and an augmented Lagrangian (AL) algorithm is utilized to recover the signals X. In this algorithm, however, a uniformly normalized tight frame is also employed as a constraint on the dictionary to avoid the trivial solution. This constraint limits the possible Ω to be learned. In [18], the analysis K-SVD (AK-SVD) algorithm was proposed for ADL using the observed signals Y=[y₁,y₂, …, y_K] ∊ R^{M × K} measured in the presence of additive noise as

$Y = X + V$ (1)

where V=[v₁,v₂, …, v_K] ∊ R^MxK is a zero-mean white-Gaussian additive noise matrix. The optimization scheme in the AK-SVD algorithm is based on a two-phase alternating iterative approach. In the first phase, the optimal backward greedy (OBG) algorithm is applied to estimate X while keeping Ω fixed. In the second phase, Ω is updated by using the estimation of X. The AK-SVD algorithm is effective but the phase of pre-estimate X leads to a computationally slow process. The learning over-complete sparsifying transform (LOST) algorithm was proposed for ADL by directly using noisy signal Y [20]. It is noted in the LOST algorithm that the null dictionary matrix can also lead to a trivial solution to the optimization problem. To eliminate such a trivial solution, the full-rank constraint on Ω is employed in [20], but the ill-conditioned Ω^TΩ may degrade the performance of the LOST algorithm.

In this paper, we introduce a subset pursuit algorithm to learn the analysis dictionary by directly employing the observed data to compute the approximate analysis sparse representation of the original signals [22]. The algorithm eliminates the need for estimating the original signals as otherwise required in the algorithms mentioned above. According to the absolute values of the analysis sparse representation, the observed data can be assigned into multiple subsets which are then used to update the analysis dictionary. To improve the performance of the signal recovery with the learned dictionary, a weighted split Bregman iterative (WSBI) algorithm is proposed to reconstruct the original signals in the analysis model, where the ℓ₁ minimization has been replaced by the weighted ℓ₁ minimization to promote the sparsity of the analysis representation of x. The simulations’ results demonstrate the competitive performance of the proposed algorithm compared with those of the state-of-art algorithms, such as AK-SVD [18], the noise-aware analysis operator learning algorithm (NAAOLA) [16, 17], and the LOST [20] and OBG [18] algorithms.

The paper is organized as follows. In Section 2, the analysis model and subset pursuit algorithm for ADL are described. In Section 3, the WSBI algorithm is proposed to reconstruct the original signals. Some experimental results are shown in Section 4, before concluding the paper in Section 5.

2. Subset pursuit algorithm for analysis dictionary learning

In this section, we present a subset pursuit algorithm for ADL by directly using the observed data without having to pre-estimate X (as done in [18]). More specifically, we exploit the analysis representation of Y to obtain the subset Y_j rather than using the estimation of X to determine Y_j.

2.1 The analysis model

The analysis model can be described as follows: for a signal x ∊ R^M and a fixed redundant analysis dictionary Ω ∊ R^PxM (P > M), the co-sparsity l of the analysis model is

$l = P - {‖ Ω x ‖}_{0}$ (2)

The quantity l denotes the number of zeros in the vector Ω x , which implies that l rows in Ω are orthogonal to the signal x, and these rows define the co-support Λ, i.e., Ω_Λ x =0, where Ω_Λ is a sub-matrix of Ω that contains the rows from Ω indexed by Λ. In this case, the signal x is said to be l -co-sparse and characterized by its co-support Λ. It is clear that the dimension of the subspace that signal x resides in is r = M − l. Generally, we can assume that X has the same co-rank M − r related to the dictionary Ω.

2.2 Subset pursuit algorithm

Suppose we measure a signal of the form

$y_{i} = x_{i} + v_{i} i = 1,2,…, K$ (3)

where v_i is a zero-mean white-Gaussian additive noise vector with a bounded ℓ₂ norm - say ∥ v_i = ∥ ₂ ≤ σ - where σ denotes the noise level. According to Eq.(2), the task of ADL can be formed as

$\min {‖ Ω x_{i} ‖}_{0}$ (4)

This problem is NP-complete [2, 23]. Just like in the synthesis case, one might replace the ℓ₀ quasi-norm with the ℓ₁ norm

$\min {‖ Ω x_{i} ‖}_{1}$ (5)

where ∥ · ∥₁ is the ℓ₁ norm that sums the absolute values of a vector. In general, if the noise v_i is stationary and bounded, the analysis model Eq.(5) has an approximate analysis model

$\min {‖ Ω y_{i} ‖}_{1}$ (6)

Proof: Using Eq.(6), the analysis model is therefore written as

$z_{i} = Ω y_{i}$ (7)

where $z_{i} = {[z_{1 i} z_{2 i} \cdot \cdot \cdot z_{P i}]}^{T} \in R^{P \times 1}$ is the analysis representation of y_i. Considering a single row ω_j^T in the analysis dictionary Ω, Eq.(7) can be rewritten as

$z_{i j} = ω_{j}^{T} y_{i}$ (8)

Accordingly, the absolute value of z_ji is

$| z_{j i} | = | ω_{j}^{T} y_{i} | = | ω_{j}^{T} x_{i} + ω_{j}^{T} v_{i} |$ (9)

We know that $| ω_{j}^{T} x_{i} + ω_{j}^{T} v_{i} | \leq | ω_{j}^{T} x_{i} | + | ω_{j}^{T} v_{i} |$ . In general, the absolute values of z_ji have a small value when ω_j is orthogonal to the signal x_i, i.e., ω_j^T x_i = 0. Thus, the analysis sparse representation of y_t can be used to determine whether ω_j^T is orthogonal to x_i.

Therefore, we can compute the analysis sparse representation of the observed data y_i to find whether ω_j^T is orthogonal with the signal x_i, rather than using ${\hat{x}}_{i}$ which otherwise has to be estimated from y_i. Because the co-rank is assumed to be M − r − which implies that M − r rows in Ω may be orthogonal to the data y_i − we can regard M − r smallest values in | Ωy_i | as zeros. The Λ_i: = {j | | ω_j^T y_i | ≈0}, which is the co-support of y_i, can be obtained by the locations of the zero entries in Ωy_i. As such, y_i can be assigned into the sub-set Y_j, ∀ j ∊ Λ_i. After Y_j is found, ω_j is updated as follows [18]:

${\hat{ω}}_{j} = \underset{ω_{j}}{arg \min} {‖ ω_{j}^{T} Y_{j} ‖}_{2}^{2} s.t . {‖ ω_{j} ‖}_{2} = 1$ (10)

For the optimization problem, ω_j can be updated using the eigenvector associated with the smallest eigenvalue of Y_jY_j^T. This algorithm is described in the Algorithm 1 table.

Algorithm 1:

SP-ADL

3. The WSBI algorithm for recovering original signals based on the analysis model

In the analysis model, the estimation of x can be obtained from its noise version y by solving the optimization problem

$\underset{x}{\arg \min} {‖ Ω x ‖}_{1} subject to {‖ y - x ‖}_{2}^{2} \leq ε$ (11)

where ε is an estimated upper bound on the noise power ∥ v ∥ ₂². The OBG algorithm [18] and some pursuit methods, such as analysis iterative hard thresholding (AIHT), analysis hard thresholding pursuit (AHTP), analysis subspace pursuit (ASP) and analysis compressive sampling matching pursuit (ACoSaMP), have been proposed to solve the optimization problem [24]. Due to the use of the greedy-like methods, the estimation of x is computationally slow and also becomes unreliable with any increase of noise in y. In [17], the AL method is applied to estimate the original signal x. Indeed, the AL method is identical to the split Bregman iteration (SBI) algorithm [25]; however, the simulation results demonstrate that the performance of the AL algorithm is limited [17]. To solve the signal recovery problem, a WSBI algorithm is proposed whereby the weighted ℓ₁ minimization would lead to a more accurate solution than that obtained by the ℓ₁ minimization [26]. To begin with in the next section, we introduce the SBI algorithm, while the WSBI is proposed subsequently.

3.1 Split Bregman iterative algorithm

Recovering x in the analysis model is based on the optimization problem Eq.(11), and the constrained optimization problem can be transformed into an unconstrained optimization problem with the Lagrange multiplier μ. This leads to the following optimization problem:

$\underset{x}{\arg \min} ({‖ Ω x ‖}_{1} + \frac{μ}{2} {‖ y - x ‖}_{2}^{2})$ (12)

Setting z = Ωx, Eq.(12) can be written as

$\underset{z, x}{\arg \min} ({‖ z ‖}_{1} + \frac{μ}{2} {‖ y - Ω x ‖}_{2}^{2}) subject to z = Ω x$ (13)

For simplicity, we set $E (z, x) = {‖ z ‖}_{1} + \frac{μ}{2} {‖ y - Ω x ‖}_{2}^{2}$ , and as such Eq.(13) can be transformed into the following problem:

$\underset{z, x}{\arg \min} E (z, x) subject to z = Ω x$ (14)

The Lagrange method can also be used to transform the constrained optimization problem (14) into an unconstrained one as follows,

$\underset{z, x}{\arg \min} (E (z, x) + \frac{η}{2} {‖ z - Ω x ‖}_{2}^{2})$ (15)

where η is Lagrange multiplier. In order to apply the SBI algorithm, we introduce the Bregman distance which is defined as [27]

$\begin{array}{l} D_{E}^{q^{t}} (z, x, z^{t}, x^{t}) = E (z, x) - E (z^{t}, x^{t}) - 〈 q_{z}^{t}, z - z^{t} 〉 \\ - 〈 q_{x}^{t}, x - x^{t} 〉 \end{array}$ (16)

where (q_z^t,q_x^t) = ∂ E (z^t,x^t), 〈 · 〉 stands for the inner product operator and t is the number of iterations. The unconstrained optimization problem (15) is equivalent to the following problem:

$\underset{z, x}{\arg \min} (D_{E}^{q^{t}} (z, x, z^{t}, x^{t}) + \frac{η}{2} {‖ z - Ω x ‖}_{2}^{2})$ (17)

The variates in Eq.(17) are separable and the SBI algorithm can be used to solve the problem (17) as [25]

$x^{t + 1} = \underset{x}{\arg \min} (\frac{μ}{2} {‖ y - x ‖}_{2}^{2} + \frac{η}{2} {‖ z^{t} - Ω x - b^{t} ‖}_{2}^{2})$ (18)

$z^{t + 1} = \underset{z}{\arg \min} ({‖ z ‖}_{1} + \frac{η}{2} {‖ z - Ω x^{t + 1} - b^{t} ‖}_{2}^{2})$ (19)

$b^{t + 1} = b^{t} + Ω x^{t + 1} - z^{t + 1}$ (20)

Generally, the initial values of x, z and b are equal to zero vectors. The convergence of the SBI algorithm has been proved in [25], and it stops when the stopping criterion, i.e., $\frac{{‖ x^{t + 1} - x^{t} ‖}_{2}}{{‖ x^{t} ‖}_{2}} \leq ρ$ , is met, where ρ > 0 is an arbitrary small constant. The SBI algorithm is summarized in the Algorithm 2 table.

Algorithm 2:

SBI

3.2 Weighted split Bregman iterative algorithm

To improve the performance of the SBI algorithm, the ℓ₁ minimization can be replaced by the weighted ℓ₁ minimization based on the synthesis model [28]. In this subsection, the WSBI algorithm has been introduced for analysis sparse representation. The WSBI algorithm is based on the weighted ℓ₁ minimization, which can promote sparsity and improve the performance of sparse representation. The optimization problem (12) can be transformed into a new form as

$\underset{x}{\arg \min} ({‖ Ω x ‖}_{w, 1} + \frac{μ}{2} {‖ y - x ‖}_{2}^{2})$ (21)

In Eq.(21), ∥ · ∥_w,1 is the weighted ℓ₁ norm, i.e., ${‖ z ‖}_{w, 1} = \sum_{i = 1}^{P} w_{i} | z_{i} |$ , where w_i and z_i are the i-th elements of the weighting coefficient vector w and signal z, respectively. The iteration algorithm for the problem (21) is similar to the problem (12) as

$x^{t + 1} = \underset{x}{\arg \min} (\frac{μ}{2} {‖ y - x ‖}_{2}^{2} + \frac{η}{2} {‖ z^{t} - Ω x - b^{t} ‖}_{2}^{2})$ (22)

$z^{t + 1} = \underset{z}{\arg \min} ({‖ z ‖}_{w, 1} + \frac{η}{2} {‖ z - Ω x^{t + 1} - b^{t} ‖}_{2}^{2})$ (23)

$b^{t + 1} = b^{t} + Ω x^{t + 1} - z^{t + 1}$ (24)

The initial values of x, z and b are equal to zero vectors and the weighting coefficients are equal to one. Next, the weighting coefficients are updated by w_i = 2δ / (δ + | z_i |), where 6 is a standard deviation of z [29]. In order to solve the least squares problem (22), the first-order derivative of the cost function in Eq.(22) is set to zero and then x is updated by

$x^{t + 1} = {(μ I + η Ω^{T} Ω)}^{- 1} (μ y + η Ω^{T} (z^{t} - b^{t}))$ (25)

In each iteration, z can be obtained by thresholding (Ωx^t+1 + b^t) as

$z_{i}^{t + 1} = {\begin{array}{l} {(Ω x^{t + 1} + b^{t})}_{i} & - \frac{w_{i}}{η}, {(Ω x^{t + 1} + b^{t})}_{i} > \frac{w_{i}}{η}; \\ 0, & - \frac{w_{i}}{η} < {(Ω x^{t + 1} + b^{t})}_{i} < \frac{w_{i}}{η}; \\ {(Ω x^{t + 1} + b^{t})}_{i} & + \frac{w_{i}}{η}, {(Ω x^{t + 1} + b^{t})}_{i} < - \frac{w_{i}}{η} . \end{array}$ (26)

The stopping criterion of the WSBI algorithm is the same as that of the SBI algorithm. The proposed WSBI algorithm is summarized in the Algorithm 3 table.

Algorithm 3.

WSBI

4. Computer simulations

In this section, two categories of the experimental results are presented. In the first part, we present experiments on synthetic data to show the ability of the proposed SPA-DL algorithm to recover a dictionary that has been used to produce the set of training data, and we then consider the real images and a piecewise-constant (PWC) image de-noising problem. In the second part, the image de-noising performances of the proposed WSBI algorithm are also tested on real images and a PWC image based on the learned dictionary. In these experiments, Ω₀ ∊ R^PxM is the initial dictionary in which each row is orthogonal to a random set of M − 1 training data and is also normalized [18].

4.1 Experiments for the SP-ADL algorithm

4.1.1 Recovering the ground-truth analysis dictionary

In the experiments, we use the same experiment protocol as in [18]. Ω ∊ R^50×25 is generated with random Gaussian entries and the training dataset consists of K =50000 signals for each co-rank l = 21 with both a noise-free setup and a noisy setup (σ = 0.04, SNR = 25 dB). If $\min_{i} (1 - | {\hat{ω}}_{i}^{T} ω_{j} |) < 0.01$ , a row ω_i^T in the true dictionary Ω is regarded as recovered, where ${\hat{ω}}_{i}^{T}$ is an atom of the trained dictionary. The co-rank is considered to be known. Using the SP-ADL algorithm to recover the true dictionary Ω, the results are presented in Fig. 1 and Fig. 2. It can be observed from Fig. 1(a) and Fig. 2(a) that the SP-ADL algorithm is convergent after 300 iterations, and 90% of the rows in the true dictionary Ω are reconstructed for the noise-free setup and 78% for the noisy one. Compared with the state-of-art algorithms, i.e., the AK-SVD, NAAOLA and LOST algorithms, their parameters are set the same as those in the original works, and it can be seen from Fig. 1(b)–(d) that these algorithms are convergent after 100, 200 and 300 iterations for the AK-SVD, NAAOLA and LOST algorithms, respectively¹. Therefore, these algorithms have different iteration numbers. After 100, 200 and 300 iterations for the AK-SVD, NAAOLA and LOST algorithms, it is observed from Fig. 2(b)–(d) that 92%, 40% and 66% of the rows in the true dictionary Ω are recovered for the noise-free setup and 84%, 2% and 64% for the noisy one, respectively. The experimental results demonstrate that the recovery percentage of the SP-ADL algorithm is relatively higher than those of the NAAOLA and LOST algorithms but is slightly lower than that of the AK-SVD algorithm. However, the running time in each iteration of the AK-SVD algorithm is significantly higher than that of the SP-ADL algorithm. The total runtime of our algorithm for 300 iterations is about 3,297 and 3,276 seconds for the noise-free and the noisy cases respectively. In contrast, the AK-SVD algorithm takes about 30,030 and 30,380 seconds respectively for only 100 iterations (Computer OS: Windows XP, CPU: Pentium(R) Dual-Core T4300 @ 2.10 GHz; RAM 1.96 GB). The main reason is that X does not need to be estimated for our algorithm in each iteration, as opposed to the AK-SVD algorithm.

Figure 1.

The convergent curves of the ADL algorithms

Figure 2.

The recovery percentage curves of the ADL algorithms

4.1.2 Image de-noising

Using a test set consisting of four images commonly used in de-noising (Lena, House, Peppers and PWC), we compare the image de-noising performance of the SP-ADL algorithm with those of the AK-SVD, NAAOLA and LOST algorithms. In this experiment, the de-noising performance is evaluated by the peak signal-to-noise ratio (PSNR), defined as PSNR = 10log₁₀( $PSNR = 10 \log_{10} (\frac{255^{2} K M}{\sum_{i = 1}^{K} \sum_{j = 1}^{M} {({\hat{x}}_{i j} - x_{i j})}^{2}})$ (dB), where x_ij and ${\hat{x}}_{i j}$ are the ij th pixel values in the noisy and de-noising images respectively.

In this experiment, a training set of 20,000 image patches each of 7 × 7 pixels, obtained from four images contaminated by noise with different noise levels σ, varying from 5 to 20, is employed for ADL by using the SP-ADL, AK-SVD, NAAOLA and LOST algorithms, respectively. The dictionary of size 63 × 49 is learned from the training data and the co-rank is assumed as l = 7. The examples of the learned analysis dictionaries are shown in Fig. 3. Based on the learned dictionaries, the OBG algorithm is utilized to recover the images from their noise versions. The parameters of the OBG algorithm are set the same as those in [18]. In the NAAOLA algorithm, the parameters are set the same as the original works except that Λ=3(σ=5), Λ=1(σ=10, 15) and Λ=0.5(σ=20), and σ=10⁻¹¹, Λ = η = 10⁵ and q = 20 in the LOST algorithm. The results, averaged over five trials, are presented in Table 1. It can be observed from Table 1 that the SP-ADL algorithm outperforms the NAAOLA and LOST algorithms. The de-noising performance of the SP-ADL algorithm is better than the AK-SVD algorithm if the noise level is increased.

Figure 3.

The learned analysis dictionaries of size 63×49 using the SP-ADL, AK-SVD, NAAOLA and LOST algorithms on the four images with a noise level δ=5. The SP-ADL algorithms’ results are shown on the top row followed by the AK-SVD, NAAOLA and LOST algorithms.

4.1.3 Comparison with the synthesis model

In this experiment, the K-SVD algorithm - which is a state-of-art synthesis dictionary learning algorithm - is applied for image de-noising. The parameters of the K-SVD algorithm are set the same as those in [30]. The synthesis dictionary D ∊ R^49×256 is learned from the same training data used in ADL. The examples of the learned synthesis dictionaries are shown in Fig. 4. Employing the learned dictionary D, the original images are reconstructed using the OMP algorithm [30]. The results, averaged over five trials, are presented in Table 1, from which we can see that the image de-noising performance of the K-SVD algorithm is better than that of the analysis methods. When the noise level σ = 5, however, the image de-noising performance of the SP-ADL and AK-SVD algorithms outperforms the K-SVD algorithm for the images of Peppers and the PWC. The results show that the analysis method provides a better modelling platform than the synthesis method.

Figure 4.

The learned synthesis dictionaries of size 49×256 using the K-SVD algorithm on the four images with the noise level δ=5

Table 1.

Image de-noising results (PSNR dB)

σ	Noisy	Method	Lena	House	Peppers	PWC
		SP-ADL	38.39	38.87	37.80	44.45
		AK-SVD	38.45	39.17	37.97	45.42
5	34.15	NAAOLA	37.36	37.04	35.93	37.28
		LOST	38.16	38.50	37.47	42.42
		K-SVD	38.63	39.60	37.75	43.63
		SP-ADL	35.07	35.19	33.87	37.61
		AK-SVD	34.84	35.34	33.83	38.40
10	28.13	NAAOLA	32.73	32.61	31.12	31.61
		LOST	34.75	34.77	33.61	36.43
		K-SVD	35.53	36.08	34.83	39.26
		SP-ADL	33.20	33.16	31.65	33.53
		AK-SVD	32.57	32.98	31.28	32.23
15	24.61	NAAOLA	30.87	30.82	29.22	29.48
		LOST	32.88	32.82	31.38	32.58
		K-SVD	33.66	34.38	33.31	35.59
		SP-ADL	31.90	31.88	30.05	30.53
		AK-SVD	31.42	31.53	29.77	29.59
20	22.11	NAAOLA	29.65	29.22	27.40	27.24
		LOST	31.64	31.47	29.84	29.93
		K-SVD	32.29	33.14	32.20	32.87

4.2 Experiments for the WSBI algorithm

We employ the SP-ADL algorithm to learn the analysis dictionary and then the learned dictionaries are utilized to recover the signals by using the WSBI, SBI and OBG algorithms. In the WSBI algorithm, the parameters are set as η = 0.1, ρ = 10⁻⁴, k_max = 2 and μ = 0.3(σ = 5),. 0.1(σ = 10), 0.05(σ = 15), 0.03(σ = 20) The parameters of the SBI algorithm are the same as those in the WSBI algorithm. In the OBG algorithm, the parameters are set as those originally suggested in [18]. The results, averaged over five trials, are presented in Table 2 and Table 3.

Table 2.
Image de-noising results (PSNR dB)

σ Noisy Method Lena House Peppers PWC

WSBI 38.12 38.78 37.35 42.28

5 34.15 SBI 37.66 38.28 36.95 40.38

OBG 38.39 38.87 37.80 44.45

WSBI 34.89 35.24 33.60 36.49

10 28.13 SBI 34.46 34.83 33.25 35.04

OBG 35.08 35.18 33.87 37.61

WSBI 33.13 33.50 31.54 32.75

15 24.61 SBI 32.94 33.15 31.26 31.46

OBG 33.20 33.16 31.65 33.53

WSBI 32.00 32.18 30.13 29.57

20 22.11 SBI 31.82 31.90 29.91 28.75

OBG 31.90 31.88 30.05 30.53

σ	Noisy	Method	Lena	House	Peppers	PWC
		WSBI	38.12	38.78	37.35	42.28
5	34.15	SBI	37.66	38.28	36.95	40.38
		OBG	38.39	38.87	37.80	44.45
		WSBI	34.89	35.24	33.60	36.49
10	28.13	SBI	34.46	34.83	33.25	35.04
		OBG	35.08	35.18	33.87	37.61
		WSBI	33.13	33.50	31.54	32.75
15	24.61	SBI	32.94	33.15	31.26	31.46
		OBG	33.20	33.16	31.65	33.53
		WSBI	32.00	32.18	30.13	29.57
20	22.11	SBI	31.82	31.90	29.91	28.75
		OBG	31.90	31.88	30.05	30.53

Table 3.

Image de-noising results (Time sec.)

σ	Noisy	Method	Lena	House	Peppers	PWC
		WSBI	688	126	157	11
5	34.15	SBI	48	9	10	5
		OBG	3374	727	847	616
		WSBI	491	93	119	18
10	28.13	SBI	45	8	9	6
		OBG	2500	536	712	583
		WSBI	354	69	107	94
15	24.61	SBI	40	7	10	7
		OBG	2022	442	603	526
		WSBI	325	61	93	96
20	22.11	SBI	37	7	10	9
		OBG	1680	378	526	525

From Table 2, it can be seen that the image de-noising performance of the WSBI algorithm is better than that of the SBI algorithm. The simulation results demonstrate that the image de-noising performance can be improved using weighted ℓ₁ minimization. The WSBI algorithm is equivalent to the SBI algorithm when the weights are one, so the first outer iteration of the WSBI algorithm performs the same as the SBI algorithm. As such, WSBI algorithm is inevitably slower than the standard SBI algorithm, as shown in Table 3. From Table 2, the experimental results show that the image de-noising performance of the WSBI algorithm is similar to that of the OBG algorithm. However, the running time of the WSBI algorithm is far less than that of the OBG algorithm, as shown in Table 3.

5. Conclusion

For the analysis sparse representation model, we present a new algorithm for ADL and for recovering the original signal. The analysis dictionary is learned directly from the observed noisy data using the SP-ADL algorithm, and then the learned dictionary is utilized to recover the original signal using the WSBI algorithm where the ℓ₁ minimization is replaced by the weighted ℓ₁ minimization. As with the synthesis sparse representation, the analysis sparse representation model can also be applied in wide fields, especially face, gesture and action recognition in robotics.

Footnotes

6.

This work was supported by the National Natural Science Foundation of China (Grant Nos. 61162014,61210306074) and the Natural Science Foundation of Jiangxi (Grant No. 20122BAB201025,20151BAB207005).

1

The terms used to measure the convergence of these algorithms are slightly different in these original works.

References

Aharon

Elad

, and Bruckstein

. K-svd: An algorithm for designing overcomplete dictionaries for sparse representation. IEEE Transactions on Signal Processing, 54(11):4311–4322, 2006.

Donoho and David

. Compressed sensing. IEEE Transactions on Information Theory, 52(4):1289–1306, 2006.

Liang

Zhang

Zeng

, and Yu

. Distributed dictionary learning for sparse representation in sensor networks. IEEE Transactions on Image Processing, 23(6):2528–2541, 2014.

Argall

Chernova

Veloso

, and Browning

. A survey of robot learning from demonstration. Robotics and autonomous systems, 57(5):469–483, 2009.

Zhong

Zhu

Han

, and Li

. An improved robust sparse coding for face recognition with disguise. International Journal of Advanced Robotic Systems, 9:126, 2012.

Boyali

and Hashimoto

. Block-sparse representation classification based gesture recognition approach for a robotic wheelchair. In Intelligent Vehicles Symposium Proceedings, IEEE, pages 2209–2215, September 2014.

Sean

Ilaria

Giorgio

, and Francesca

. Keep it simple and sparse: real-time action recognition. The Journal of Machine Learning Research, 14(1):2617–2640, 2013.

Kira

. Transfer of sparse coding representations and object classifiers across heterogeneous robots. In IEEE/RSJ International Conference on Intelligent Robots and Systems, pages 1133–1138, June 2014.

Engan

Aase

, and Husoy

. Method of optimal directions for frame design. In IEEE International Conference on Acoustics, Speech, and Signal Processing, volume 5, pages 2443–2446, 1999.

10.

Skretting

and Engan

. Recursive least squares dictionary learning algorithm. IEEE Transactions on Signal Processing, 58(4):2121–2130, 2010.

11.

Dai

, and Wang

. Simultaneous codeword optimization (simco) for dictionary update and learning. IEEE Transactions on Signal Processing, 60(12):6340–6353, 2011.

12.

Yaghoobi

Blumensath

, and Davies

. Dictionary learning for sparse approximations with the majorization method. IEEE Transactions on Signal Processing, 57(6):2178–2191, 2009.

13.

Elad

Milanfar

, and Rubinstein

. Analysis versus synthesis in signal priors. Inverse problems, 23(3):947–968, 2007.

14.

Nam

Davies

Elad

, and Gribonval

. Cosparse analysis modeling - uniqueness and algorithms. In IEEE International Conference on Acoustics, Speech and Signal Processing, pages 5804–5807, 2011.

15.

Ophir

Elad

Bertin

, and Plumbley

. Sequential minimal eigenvalues: An approach to analysis dictionary learning. In European Signal Processing Conference, pages 1465–1469, 2011.

16.

Yaghoobi

Nam

Gribonval

, and Davies

. Noise aware analysis operator learning for approximately cosparse signals. In IEEE International Conference on Acoustics, Speech and Signal Processing, pages 5409–5412, 2012.

17.

Yaghoobi

Nam

Gribonval

, and Davies

. Constrained overcomplete analysis operator learning for cosparse signal modelling. IEEE Transactions on Signal Processing, 61(9):2341–2355, 2013.

18.

Rubinstein

Peleg

, and Elad

. Analysis k-svd: A dictionary-learning algorithm for the analysis sparse model. IEEE Transactions on Signal Processing, 61(3):661–677, 2013.

19.

Ravishankar

and Bresler

. Learning sparsifying transforms. IEEE Transactions on Signal Processing, 61(5):1072–1086, 2013.

20.

Ravishankar

and Bresler

. Learning overcomplete sparsifying transforms for signal processing. In IEEE International Conference on Acoustics, Speech and Signal Processing, pages 3088–3092, 2013.

21.

Zhang

Wang

, and Sanei

. K-plane clustering algorithm for analysis dictionary learning. In IEEE International Workshop on Machine Learning for Signal Processing, pages 1–4, 2013.

22.

Zhang

Wang

, and Wang

. Subset pursuit for analysis dictionary learning. In European Signal Processing Conference, pages 1–5, 2013.

23.

Tropp

. Just relax: convex programming methods for identifying sparse signals in noise. IEEE Transactions on Information Theory, 52(3):1030–1051, 2006.

24.

Giryes

Nam

Elad

Gribonval

, and Davies

. Greedy-like algorithms for the cosparse analysis model. Linear Algebra and its Applications, 441:22–60, 2013.

25.

Cai

Osher

, and Shen

. Split bregman methods and frame based image restoration. Multiscale modeling & simulation, 8(2):337–369, 2009.

26.

Candes

Wakin

, and Boyd

. Enhancing sparsity by reweighted l₁ minimization. Journal of Fourier Analysis and Applications, 14(5–6):877–905, 2008.

27.

Yin

Osher

Goldfarb

, and Darbon

. Bregman iterative algorithms for l₁-minimization with applications to compressed sensing. SIAM Journal on Imaging Sciences, 1(1):143–168, 2008.

28.

Zhao

and Li

. Reweighted l₁-minimization for sparse solutions to underdetermined linear systems. SIAM Journal on Optimization, 22(3):1065–1088, 2012.

29.

Arberet

Vandergheynst

Carrillo

Thiran

, and Wiaux

. Sparse reverberant audio source separation via reweighted analysis. IEEE Transactions on Audio, Speech, and Language Processing, 21(7): 1391–1402, 2013.

30.

Elad

and Aharon

. Image denoising via sparse and redundant representations over learned dictionaries. IE EE Transactions on Image Processing, 15(12):3736–3745, 2006.

Analysis Sparse Representation Based on Subset Pursuit and Weighted Split Bregman Iteration Algorithm

Abstract

Keywords

1. Introduction

2.1 The analysis model

4.1 Experiments for the SP-ADL algorithm

4.1.1 Recovering the ground-truth analysis dictionary

Footnotes

6.

1

References