# Analysis Sparse Representation for Nonnegative Signals Based on Determinant Measure by DC Programming

Authors: Yujie Li; Benying Tan; Atsunori Kanemura; Shuxue Ding; Wuhui Chen
Journal: Complexity
 (2018)

---

## Abstract

Analysis sparse representation has recently emerged as an alternative approach to the synthesis sparse model. Most existing algorithms typically employ thel0-norm, which is generally NP-hard. Other existing algorithms employ the l1-norm to relax the l0-norm, which sometimes cannot promote adequate sparsity. Most of these existing algorithms focus on general signals and are not suitable for nonnegative signals. However, many signals are necessarily nonnegative such as spectral data. In this paper, we present a novel and efficient analysis dictionary learning algorithm for nonnegative signals with the determinant-type sparsity measure which is convex and differentiable. The analysis sparse representation can be cast in three subproblems, sparse coding, dictionary update, and signal update, because the determinant-type sparsity measure would result in a complex nonconvex optimization problem, which cannot be easily solved by standard convex optimization methods. Therefore, in the proposed algorithms, we use a difference of convex (DC) programming scheme for solving the nonconvex problem. According to our theoretical analysis and simulation study, the main advantage of the proposed algorithm is its greater dictionary learning efficiency, particularly compared with state-of-the-art algorithms. In addition, our proposed algorithm performs well in image denoising.


---

## Body

## 1. Introduction

Real signals around our daily life are always distributed in a high dimensional space; however low-dimensional structures are found in the signals, then we can represent the signals with a proper model by only a few parameters [1]. A proper model should be simple while matching the signals. In the past decades, the sparse and redundant representation model has been proven to be an efficient and beneficial model [2–5]. The theoretical background for sparse models is given by compressed sensing (CS) [6–8]. CS mathematically declares that if a signal is sparse or compressive, this original signal can be reconstructed by a few measurements, which are much fewer than the counts suggested by previous theories [6, 7, 9–11]. Sparse representation has also been described as an extraordinary powerful solution for a wide range of real-word applications, especially in image processing, such as image denoising, deblurring, inpainting, restoration, superresolution, and also in the field of machine learning, computer vision, and so on [12–21].Sparse representation can be formulated by either a synthesis model or an analysis model. The synthesis model is popular and mature. The analysis model has been less investigated for sparse representation, although several analysis dictionary learning algorithms have been proposed, such as the analysis K-SVD [12], Greedy Analysis Pursuit (GAP) [22], and the analysis thresholding algorithm [23].In practice, some signals such as chemical concentrations in experimental results and pixels in video frames and images have inherent nonnegativity, and dedicated factorization methods have been proposed [24, 25]. The above analysis sparse representation algorithms are all for general signals which contain nonnegative and negative elements. The methods for general signals directly applied to nonnegative signals cannot achieve satisfying results. An existing analysis dictionary learning method for nonnegative signals [26], which uses blocked determinants as the sparseness measure, is quite difficult or computationally expensive. The purpose of this paper is to address the problem on nonnegative analysis sparse representation.In this paper, we present a novel algorithm of analysis sparse representation for nonnegative signals, which is parallel to the synthesis sparse representation in the principle and structure. Though this model has been studied in the past, there is still not a matured field for nonnegative analysis representation, while the algorithms designed for general signal cannot sufficiently be applied to the nonnegative signals. Thus, we focus on the nonnegative sparse representation with the analysis model. We cast the analysis sparse representation into three subproblems (analysis dictionary update, sparse coding, and signal recovery) and use an alternating scheme to obtain an optimization solution. We utilize the determinant-type of sparseness measure as the sparseness constraint, which is convex and differentiable. The objective function for sparse coding is nonconvex, and standard convex optimization methods cannot be employed. Fortunately the objective function is the difference of two convex functions, then we can introduce difference of convex (DC) programming to solve this nonconvex optimization problem.The remainder of this paper is organized as follows. The conventional sparse representation problem is reviewed in Section2. In Section 3, we introduce the analysis representation. In Section 4, we describe the problem formulation for analysis sparse representation and present the optimization framework. The experiments described in Section 5 demonstrate the practical advantages of the proposed algorithms compared with state-of-the-art algorithms both with artificial and real-world datasets. Finally, we present our conclusions in Section 6.


### 1.1. Notations

Here we list notations used in this paper. A boldface uppercase letter likeX is defined as a matrix, and a lowercase letter like xij is defined as the ijth entry of X. A boldface lowercase letter, such as x, is defined as a vector, and a lowercase letter xj is defined as the jth entry of x. Matrix slices Xi: and X:j are defined as the ith row and the jth column of matrix X, respectively. The Frobenius norm of matrix X is defined as XF=∑i,j|xij|21/2. The determinant value of a matrix is denoted by det(·). Note that, in this paper, all parameters take real values.


## 1.1. Notations

Here we list notations used in this paper. A boldface uppercase letter likeX is defined as a matrix, and a lowercase letter like xij is defined as the ijth entry of X. A boldface lowercase letter, such as x, is defined as a vector, and a lowercase letter xj is defined as the jth entry of x. Matrix slices Xi: and X:j are defined as the ith row and the jth column of matrix X, respectively. The Frobenius norm of matrix X is defined as XF=∑i,j|xij|21/2. The determinant value of a matrix is denoted by det(·). Note that, in this paper, all parameters take real values.


## 2. Preliminaries

### 2.1. Sparse Representation

Sparse representation decomposes observed signals into a product of a dictionary matrix which contains signal bases and a sparse coefficient matrix [13–17], and there are two different structures: synthesis model and analysis model. The synthesis model is the first proposed sparse model and more popular. We first review it in this section.Assume that we want to model the signalsX∈Rm×N, where m is the signal dimensionality and N is the number of measurements. The synthesis sparse model suggests that the signals could be expressed as(1)X=DHor(2)X≈DH,s.t.X-DHF2≤ε,where D∈Rm×n refer to as a dictionary, H∈Rn×N is a representation coefficient matrix, and ε≥0 is a small residual [27]. Here, n is the number of bases, which are also called dictionary atoms. We further assume that the representation matrix H is sparse (i.e., many zero entries) to obtain sparse representations of the signals. Equations (1) or (2) mean that each signal can be represented as a linear combination of a few atoms from the dictionary matrix D.A key issue in the sparse representation is the choice of the dictionary which the observed signals are used to decompose. One choice is a predefined dictionary, such as discrete Fourier transform (DFT), discrete cosine transform (DCT), and wavelets [28], which can be employed for learning a signal-specific dictionary from observed signals. Another choice, the learned dictionary, results in better matching to the contents of signals. In addition, the learned dictionary often exhibits better performance compared to predefined dictionaries in real-world applications [29, 30].Intriguingly, there exists a “twin” of the synthesis model called the analysis model [31]. Assume that there is a matrix Ω∈Rn×m that produces a sparse coefficient matrix H by being multiplied to the signal matrix: H=ΩX. This equation can be obtained as the solution to a minimization problem of the error function H-ΩXF. Remarkably, this error function is convex, and standard optimization methods can be employed. Since error functions in the synthesis model are nonconvex, optimization in the analysis model is often easier. We call Ω∈Rn×m the analysis dictionary. Atoms in the analysis dictionary Ω are its rows, rather columns in the synthesis dictionary D. The term “analysis” means the dictionary analyzes the signal to produce a sparse result [32]. To emphasize the difference between the analysis and synthesis models, the term “cosparsity” has been introduced in the literature [31, 33], which counts the number of 0-valued elements of ΩX, that is, zero elements coproduced by Ω and X [34]. The analysis sparse model is also called the cosparse model, and then the analysis dictionary is also called the cosparse dictionary.Now we look more closely at the analysis sparse model. The analysis model for one signalx∈Rm, which is a column in the signal matrix X, can be represented using a proper analysis dictionary Ω∈Rn×m. The ith row, namely, ith atom, in Ω is denoted by ωi. We want to make the analysis representation vector h=Ωx sparse. This is formulated by introducing a sparsity measure M(h), so that it negatively behaves with the sparsity of h, and minimizing M(h) yields the sparsest solution:(3)Ω=argminΩMh,s.t.h=Ωx.Although employing the l0-norm, that is, setting M(h)=h0, yields the sparsest solution [35], the optimization problem is combinatorial and often NP-hard. Therefore other sparsity measures such as the l1-norm are employed to have easier optimization problems. Nevertheless, it is known that the l1-norm often overpenalizes large elements and solutions are too sparse.


### 2.2. Sparseness Measure

Thelp-norms, where p=0,1, or 2, are popular measures for assessing the sparseness of a vector. Since the l0-norm yields an NP-hard problem, its convex relaxation, the l1-norm, is often preferred [36, 37]. The l1-norm of a vector h is defined to be the sum of the absolute values of h; namely, h1=∑i|hi|. If the vector is nonnegative, that is, h∈R+, the l1-norm of h is just h1=∑ihi. For nonnegative vectors, their l1-norm is differentiable and smooth, and gradient methods can be used in optimization. Some authors introduce the l2-norm with nonnegative matrix factorization since the nonnegative constraints yield sparse solutions. However, the results with the l2-norm are not sparser than those with the l0-norm or l1-norm [38].The sparsity measures mentioned above can reflect the instantaneous sparseness of one single signal [35], but they are not suitable for evaluating sparsity across different measurements [39]. In order to describe the joint sparseness of the nonnegative sources, we introduce determinant-type of sparsity measure. In spectral unmixing for remote sensing image interpretation, where signals are nonnegative, the determinant-type of sparsity measure [40] can get good results similar to the other sparseness-based methods from the results of numerical experiments [41]. Thus, the determinant-type measure can explicitly measure the sparseness of nonnegative matrices.The determinant-type sparse measure has several good qualities. If a nonnegative matrix is normalized, we can find that the determinant value of the nonnegative matrix is well bounded and its value interpolates monotonously between two extremes of0 and 1, along with the increasing of the sparsity. For instance, if the nonnegative matrix V is nonsparse with its rows and satisfies sum-to-one, then the determinant of VVT, det⁡VVT, is close to 0. On the other hand, det⁡VVT approaches to 1 if and only if the matrix is the most sparse [42]. Namely, the determinant value satisfies that 0≤det⁡VVT≤1, where det⁡VVT=0 if all entries of VVT are the same, and det⁡VVT=1 when the following two criteria are satisfied at the same time:(1)
For alli∈1,2,…,m, only one element in vi is nonzero.(2)
For alli,j∈1,2,…,m and i≠j, vi and vj are orthogonal, that is, viTvj=0.The detailed proof can be found in [40]. Thus we can use the determinant measure in the cost function. Figure 1 illustrates the sparseness degrees of three different matrices gauged by the determinant measure. The determinant values of the matrices from left to right are 0.0625, 0.5, and 1. We can see that the sparser the matrix is, the larger value the determinant measure is. Thus the sparse coding problem with determinant constraints can be expressed as an optimization problem(4)maxVdetVVT=minV-detVVT.Figure 1
Illustration of various degrees of sparseness.


### 2.3. Related Works

The existing methods for sparse representation with the analysis model employ various sparsity constraints. The analysis K-SVD algorithm [12] minimizes the error between the noisy (observed) signals and the estimated (reconstructed) signals with the l0-norm as the sparsity constraint. The optimal backward greedy algorithm (OBG) is employed to estimate the analysis dictionary Ω, which has higher complexity. In [43–46], the l1-norm is imposed as sparse constraint on the sparse coefficients and a projected subgradient-based algorithm is employed to learn the analysis dictionary. The analysis operator learning (AOL) algorithm [43] utilizing the l1-norm constraint restricts the dictionary to a uniform normalized tight frame (UNTF) and learns the analysis dictionary as entire matrix by solving a cheap soft thresholding and then projecting the dictionary onto the UNTF set. Li et al. [26] propose a novel analysis sparse model based on the determinant-type measure, where the optimization problem is solved by an iterative sparseness maximization scheme. In their work, the problem can be cast into row-to-row optimization with respect to the analysis atoms and then utilize the quadratic programming (QP) technique to solve the optimization problem with respect to each row. However this method has no signal recovery stage and cannot apply to denoising and other applications. In recently, DC programming is introduced to deal with the nonconvex optimization problems for sparse representation [47]. DC programming and DC algorithm (DCA) constitute the backbone of smoothness and nonsmoothness, nonconvex programming, and global optimization [48]. Thus it is considered to be a powerful tool for nonconvex optimizations [48, 49]. The exiting DC programming based sparse representation algorithms are with synthesis model, and we first propose DCA to analysis model.


## 2.1. Sparse Representation

Sparse representation decomposes observed signals into a product of a dictionary matrix which contains signal bases and a sparse coefficient matrix [13–17], and there are two different structures: synthesis model and analysis model. The synthesis model is the first proposed sparse model and more popular. We first review it in this section.Assume that we want to model the signalsX∈Rm×N, where m is the signal dimensionality and N is the number of measurements. The synthesis sparse model suggests that the signals could be expressed as(1)X=DHor(2)X≈DH,s.t.X-DHF2≤ε,where D∈Rm×n refer to as a dictionary, H∈Rn×N is a representation coefficient matrix, and ε≥0 is a small residual [27]. Here, n is the number of bases, which are also called dictionary atoms. We further assume that the representation matrix H is sparse (i.e., many zero entries) to obtain sparse representations of the signals. Equations (1) or (2) mean that each signal can be represented as a linear combination of a few atoms from the dictionary matrix D.A key issue in the sparse representation is the choice of the dictionary which the observed signals are used to decompose. One choice is a predefined dictionary, such as discrete Fourier transform (DFT), discrete cosine transform (DCT), and wavelets [28], which can be employed for learning a signal-specific dictionary from observed signals. Another choice, the learned dictionary, results in better matching to the contents of signals. In addition, the learned dictionary often exhibits better performance compared to predefined dictionaries in real-world applications [29, 30].Intriguingly, there exists a “twin” of the synthesis model called the analysis model [31]. Assume that there is a matrix Ω∈Rn×m that produces a sparse coefficient matrix H by being multiplied to the signal matrix: H=ΩX. This equation can be obtained as the solution to a minimization problem of the error function H-ΩXF. Remarkably, this error function is convex, and standard optimization methods can be employed. Since error functions in the synthesis model are nonconvex, optimization in the analysis model is often easier. We call Ω∈Rn×m the analysis dictionary. Atoms in the analysis dictionary Ω are its rows, rather columns in the synthesis dictionary D. The term “analysis” means the dictionary analyzes the signal to produce a sparse result [32]. To emphasize the difference between the analysis and synthesis models, the term “cosparsity” has been introduced in the literature [31, 33], which counts the number of 0-valued elements of ΩX, that is, zero elements coproduced by Ω and X [34]. The analysis sparse model is also called the cosparse model, and then the analysis dictionary is also called the cosparse dictionary.Now we look more closely at the analysis sparse model. The analysis model for one signalx∈Rm, which is a column in the signal matrix X, can be represented using a proper analysis dictionary Ω∈Rn×m. The ith row, namely, ith atom, in Ω is denoted by ωi. We want to make the analysis representation vector h=Ωx sparse. This is formulated by introducing a sparsity measure M(h), so that it negatively behaves with the sparsity of h, and minimizing M(h) yields the sparsest solution:(3)Ω=argminΩMh,s.t.h=Ωx.Although employing the l0-norm, that is, setting M(h)=h0, yields the sparsest solution [35], the optimization problem is combinatorial and often NP-hard. Therefore other sparsity measures such as the l1-norm are employed to have easier optimization problems. Nevertheless, it is known that the l1-norm often overpenalizes large elements and solutions are too sparse.


## 2.2. Sparseness Measure

Thelp-norms, where p=0,1, or 2, are popular measures for assessing the sparseness of a vector. Since the l0-norm yields an NP-hard problem, its convex relaxation, the l1-norm, is often preferred [36, 37]. The l1-norm of a vector h is defined to be the sum of the absolute values of h; namely, h1=∑i|hi|. If the vector is nonnegative, that is, h∈R+, the l1-norm of h is just h1=∑ihi. For nonnegative vectors, their l1-norm is differentiable and smooth, and gradient methods can be used in optimization. Some authors introduce the l2-norm with nonnegative matrix factorization since the nonnegative constraints yield sparse solutions. However, the results with the l2-norm are not sparser than those with the l0-norm or l1-norm [38].The sparsity measures mentioned above can reflect the instantaneous sparseness of one single signal [35], but they are not suitable for evaluating sparsity across different measurements [39]. In order to describe the joint sparseness of the nonnegative sources, we introduce determinant-type of sparsity measure. In spectral unmixing for remote sensing image interpretation, where signals are nonnegative, the determinant-type of sparsity measure [40] can get good results similar to the other sparseness-based methods from the results of numerical experiments [41]. Thus, the determinant-type measure can explicitly measure the sparseness of nonnegative matrices.The determinant-type sparse measure has several good qualities. If a nonnegative matrix is normalized, we can find that the determinant value of the nonnegative matrix is well bounded and its value interpolates monotonously between two extremes of0 and 1, along with the increasing of the sparsity. For instance, if the nonnegative matrix V is nonsparse with its rows and satisfies sum-to-one, then the determinant of VVT, det⁡VVT, is close to 0. On the other hand, det⁡VVT approaches to 1 if and only if the matrix is the most sparse [42]. Namely, the determinant value satisfies that 0≤det⁡VVT≤1, where det⁡VVT=0 if all entries of VVT are the same, and det⁡VVT=1 when the following two criteria are satisfied at the same time:(1)
For alli∈1,2,…,m, only one element in vi is nonzero.(2)
For alli,j∈1,2,…,m and i≠j, vi and vj are orthogonal, that is, viTvj=0.The detailed proof can be found in [40]. Thus we can use the determinant measure in the cost function. Figure 1 illustrates the sparseness degrees of three different matrices gauged by the determinant measure. The determinant values of the matrices from left to right are 0.0625, 0.5, and 1. We can see that the sparser the matrix is, the larger value the determinant measure is. Thus the sparse coding problem with determinant constraints can be expressed as an optimization problem(4)maxVdetVVT=minV-detVVT.Figure 1
Illustration of various degrees of sparseness.


## 2.3. Related Works

The existing methods for sparse representation with the analysis model employ various sparsity constraints. The analysis K-SVD algorithm [12] minimizes the error between the noisy (observed) signals and the estimated (reconstructed) signals with the l0-norm as the sparsity constraint. The optimal backward greedy algorithm (OBG) is employed to estimate the analysis dictionary Ω, which has higher complexity. In [43–46], the l1-norm is imposed as sparse constraint on the sparse coefficients and a projected subgradient-based algorithm is employed to learn the analysis dictionary. The analysis operator learning (AOL) algorithm [43] utilizing the l1-norm constraint restricts the dictionary to a uniform normalized tight frame (UNTF) and learns the analysis dictionary as entire matrix by solving a cheap soft thresholding and then projecting the dictionary onto the UNTF set. Li et al. [26] propose a novel analysis sparse model based on the determinant-type measure, where the optimization problem is solved by an iterative sparseness maximization scheme. In their work, the problem can be cast into row-to-row optimization with respect to the analysis atoms and then utilize the quadratic programming (QP) technique to solve the optimization problem with respect to each row. However this method has no signal recovery stage and cannot apply to denoising and other applications. In recently, DC programming is introduced to deal with the nonconvex optimization problems for sparse representation [47]. DC programming and DC algorithm (DCA) constitute the backbone of smoothness and nonsmoothness, nonconvex programming, and global optimization [48]. Thus it is considered to be a powerful tool for nonconvex optimizations [48, 49]. The exiting DC programming based sparse representation algorithms are with synthesis model, and we first propose DCA to analysis model.


## 3. Formulation

Now we turn to describe the problem of analysis sparse representation. We consider the following assumption: given an observed signal vectory∈R+m, we assume that y is a noisy version of a signal x∈R+m. Thus, y=x+u, where u is additive positive white Gaussian noise. Using an analysis dictionary Ω∈Rn×m, each row of which defines 1×m analysis atom, we assume that x satisfies Ωx0=m-l, where l is the cosparsity of the signal defied to be the number of zero elements. Then we extend to signals matrix, and we use matrix X to define signals with each column as one signal. Here we use M(·) as the sparse measure. Taking into account the noise in the measured signals, we formulate an optimization task for analysis dictionary learning by(5)minΩ,XMΩX,s.t.Y-XF2≤σ,Ω∈L,where σ is a noise-level parameter, L is the constraint on the analysis dictionary, and M is the sparse regularization. We prefer to use an alternative, regularized version of above equation with penalty multipliers. Here we employ Z as an approximation of ΩX, which makes the learning easier and faster in practice. Thus, the analysis sparse coding is cheap and can be obtained exactly by thresholding the product of ΩX and the sparsity measure on Z. Thus the analysis sparse representation can be rewritten as(6)minΩ,X,ZMZ+λY-XF2+βΩX-ZF2,s.t.ωi2=1,∀i,where Z∈Rn×N is the representation coefficient matrix. Having a sparse representation means the representation matrix Z is sparse. We introduce normalization constraint (∀iωi2=1) to analysis dictionary which helps remove a scale ambiguity.We can cast the entire problem into three variable-wise optimization subproblems. The first one is the analysis dictionary update subproblem and the next two problems are sparse coefficient matrix and signal update subproblems.A pseudocode for such an analysis dictionary learning is presented in Algorithm1 (ADLA).Algorithm 1:Analysis dictionary learning algorithm (ADLA).
(1) Initialization: Ω0,Z0,X0=Y,i=0, (2) while not converged do (3) Ωi+1=minΩΩX-ZF2, s.t.∀iωi2=1 (4) Zi+1=minZMZ+βΩX-ZF2 (5) Xi+1=minXλY-XF2+βΩX-ZF2 (6) i=i+1 (7) end while


### 3.1. Analysis Sparse Representation with Determinant Constraint

In this section, we introduce a novel determinant-type constrained sparse method to learn an analysis dictionary for sparse representation of nonnegative signals. What is more, we set the parametersλ and β in (6) as positive constants. Considering these factors, our minimization problem for analysis sparse dictionary learning with the determinant-type constraint can be expressed as(7)minΩ,X,Z-det⁡ZZT+λY-XF2+βΩX-ZF2,s.t.Z>0;ωi2=1,zi2=1,∀i.The above objective function is nonconvex, which is hard to solve by traditional convex optimization methods.


## 3.1. Analysis Sparse Representation with Determinant Constraint

In this section, we introduce a novel determinant-type constrained sparse method to learn an analysis dictionary for sparse representation of nonnegative signals. What is more, we set the parametersλ and β in (6) as positive constants. Considering these factors, our minimization problem for analysis sparse dictionary learning with the determinant-type constraint can be expressed as(7)minΩ,X,Z-det⁡ZZT+λY-XF2+βΩX-ZF2,s.t.Z>0;ωi2=1,zi2=1,∀i.The above objective function is nonconvex, which is hard to solve by traditional convex optimization methods.


## 4. Proposed Algorithm

The analysis representation with determinant-type constraint problem can be cast into three subproblems: an analysis dictionary update stage, a sparse coefficient coding stage, and a signal recovery stage. The corresponding formulations are as follows.Analysis Dictionary Update Stage (8) m i n Ω  Ω X - Z F 2 , s.t.  ω i 2 = 1 ,  ∀ i .Sparse Coefficient Coding Stage (9) m i n Z  - det ⁡ Z Z T + β Ω X - Z F 2 , s.t.  Z > 0 ; (10) z i 2 = 1 ,  ∀ i .Signal Recovery Stage (11) m i n X  λ Y - X F 2 + β Ω X - Z F 2 .We will describe each stage in detail in the following subsections.


### 4.1. Analysis Dictionary Update

We use a projected subgradient type algorithm to solve the analysis dictionary update subproblem as follows:(12)minΩΩX-ZF2,s.t.ωi2=1,∀i.Since the objective function above is a quadratic function ofΩ, the solution can be analytically found as the zero-gradient point. The gradient of the objective function is(13)∂fΩ∂Ω=ΩX-ZXT=ΩXXT-ZXT.By solving ∂fΩ/∂Ω=0, we obtain(14)Ω=ZXTXXT-1.The projection of a dictionary onto a space with fixed row norms can be easily done for nonzero rows by scaling each row to have a unit norm. We usePUN to denote this projection. If a row is zero, we set the row to a normalized random vector. Namely, PUN is not uniquely defined. This is due to the fact that the set of uniformly normalized vectors is not convex. The projection can be found by(15)PUNΩ=PUNωii,PUNω=ωω2ω2≠0νotherwise,where ν is a random vector on the unit sphere.


### 4.2. Sparse Coding by DC Programming

Optimization for estimating sparse coefficientZ is a core problem. The formulation is the subtraction of two convex functions, making the objective function not generally nonconvex. Thus we cannot use traditional convex optimization methods to solve this problem.In this paper, to solve the objective function, we introduce the DC programming scheme to translate the minimization optimization problem into DC programming problem. According to the theory of DC programming [48, 49], we construct a DC function for our problem. Then the reformulated DC objective function F can be expressed as(16)FZ=f1Z-f2Z,where(17)f1Z=βΩX-ZF2,f2Z=det⁡ZZT.Here f1(Z) and f2(Z) are two convex functions. Then, the sparse coding problem can be reformulated as a DC program:(18)minf1Z+χR+n×NZ-f2Z:Z∈R+n×N,where χR+n(Z) is an indicator function, which is defined by χR+n(Z)=0 if Z∈R+n×N and +∞ otherwise.We utilize the scheme of DCA [48]. At each iteration k,(19)Z~k=∇f2Zk=detZZTZZT-1Z.At the iteration k+1,(20)Zk+1=argminZ⁡f1Z-Z~k,Z:Z∈R+n=argminZ⁡βΩX-ZF2-Z~k,Z:Z∈R+n.Consider that Z(k+1) is separable according to the columns of Z, the above equation can be rewritten as(21)Zk+1=argminZ⁡∑j=1NβΩX:jTΩX:j-2βΩX:jTZ:j+βZ:jTZ:j-Z~:jkTZ:j:Z∈R+n.For the sparse coding stage in iteration scheme, we fix the dictionaryΩ and signals X and update only Z in (16) and (17). To keep the coefficient matrix Z nonnegative, the update procedure of sparse coefficient Z can be briefly described as follows:(22)Z:jk+1=ΩX:j+12βZ~:jk+,∀j,where (·)+=max(0,·) takes the positive part. Algorithm 2 shows the procedures of the proposed algorithm for sparse coding based on DC programming.Algorithm 2:Sparse coding based on DC programming (SCDC).
Require: m×N matrix X, n×m matrix Ω, and m<n<N. (1) Initialize Z, let k=1 (2) whilenot converged do (3)Compute Z~k using (19). (4)Update Zk+1 using (22). (5) end while


### 4.3. Signal Recovery

Then we consider the signal recovery stage. In this stage the analysis dictionaryΩ and the coefficients Z are fixed. The optimization problem for signal recovery is formulated as(23)minXfX=λY-XF2+βΩX-ZF2.The above objective function (23) is a quadratic function of signals X. Thus, the optimal solution of above objective function can be analytically obtained by setting its gradient equal to zero. The gradient of the objective function is(24)∂fX∂X=λX-Y+βΩTΩX-Z.By solving ∂fX/∂X=0, we obtain(25)X=λY+βΩTZλI+βΩTΩ.


## 4.1. Analysis Dictionary Update

We use a projected subgradient type algorithm to solve the analysis dictionary update subproblem as follows:(12)minΩΩX-ZF2,s.t.ωi2=1,∀i.Since the objective function above is a quadratic function ofΩ, the solution can be analytically found as the zero-gradient point. The gradient of the objective function is(13)∂fΩ∂Ω=ΩX-ZXT=ΩXXT-ZXT.By solving ∂fΩ/∂Ω=0, we obtain(14)Ω=ZXTXXT-1.The projection of a dictionary onto a space with fixed row norms can be easily done for nonzero rows by scaling each row to have a unit norm. We usePUN to denote this projection. If a row is zero, we set the row to a normalized random vector. Namely, PUN is not uniquely defined. This is due to the fact that the set of uniformly normalized vectors is not convex. The projection can be found by(15)PUNΩ=PUNωii,PUNω=ωω2ω2≠0νotherwise,where ν is a random vector on the unit sphere.


## 4.2. Sparse Coding by DC Programming

Optimization for estimating sparse coefficientZ is a core problem. The formulation is the subtraction of two convex functions, making the objective function not generally nonconvex. Thus we cannot use traditional convex optimization methods to solve this problem.In this paper, to solve the objective function, we introduce the DC programming scheme to translate the minimization optimization problem into DC programming problem. According to the theory of DC programming [48, 49], we construct a DC function for our problem. Then the reformulated DC objective function F can be expressed as(16)FZ=f1Z-f2Z,where(17)f1Z=βΩX-ZF2,f2Z=det⁡ZZT.Here f1(Z) and f2(Z) are two convex functions. Then, the sparse coding problem can be reformulated as a DC program:(18)minf1Z+χR+n×NZ-f2Z:Z∈R+n×N,where χR+n(Z) is an indicator function, which is defined by χR+n(Z)=0 if Z∈R+n×N and +∞ otherwise.We utilize the scheme of DCA [48]. At each iteration k,(19)Z~k=∇f2Zk=detZZTZZT-1Z.At the iteration k+1,(20)Zk+1=argminZ⁡f1Z-Z~k,Z:Z∈R+n=argminZ⁡βΩX-ZF2-Z~k,Z:Z∈R+n.Consider that Z(k+1) is separable according to the columns of Z, the above equation can be rewritten as(21)Zk+1=argminZ⁡∑j=1NβΩX:jTΩX:j-2βΩX:jTZ:j+βZ:jTZ:j-Z~:jkTZ:j:Z∈R+n.For the sparse coding stage in iteration scheme, we fix the dictionaryΩ and signals X and update only Z in (16) and (17). To keep the coefficient matrix Z nonnegative, the update procedure of sparse coefficient Z can be briefly described as follows:(22)Z:jk+1=ΩX:j+12βZ~:jk+,∀j,where (·)+=max(0,·) takes the positive part. Algorithm 2 shows the procedures of the proposed algorithm for sparse coding based on DC programming.Algorithm 2:Sparse coding based on DC programming (SCDC).
Require: m×N matrix X, n×m matrix Ω, and m<n<N. (1) Initialize Z, let k=1 (2) whilenot converged do (3)Compute Z~k using (19). (4)Update Zk+1 using (22). (5) end while


## 4.3. Signal Recovery

Then we consider the signal recovery stage. In this stage the analysis dictionaryΩ and the coefficients Z are fixed. The optimization problem for signal recovery is formulated as(23)minXfX=λY-XF2+βΩX-ZF2.The above objective function (23) is a quadratic function of signals X. Thus, the optimal solution of above objective function can be analytically obtained by setting its gradient equal to zero. The gradient of the objective function is(24)∂fX∂X=λX-Y+βΩTΩX-Z.By solving ∂fX/∂X=0, we obtain(25)X=λY+βΩTZλI+βΩTΩ.


## 5. Experiments and Discussion

This section presents the results of numerical experiments to evaluate the performance of the proposed algorithms. The programs were coded in Matlab (R2016b) and run on a machine with a 3.3 GHz Intel Core i7 CPU and 16 GB of memory under Microsoft Windows 10.


### 5.1. Phase Transition

The goal of this phase transition experiment is to study how the proposed algorithm with the determinant-type sparsity measure can identify nonzero elements in a sparse matrixZ∈Rm×N. Specifically, we examine when the success or failure of nonzero element identification switches according to the sparsity of the matrix. We varied the number s of nonzero elements in sparse matrix Z, the number m of the dimensionality of the dictionary atoms, and the number of measurements N. The range for s was from 1 to 10, m from 1 to 10, and N from 50 to 200.Figure2 compares the phase transition diagrams of the determinant-type measure and the l1-norm. The white regions indicate success of identifying nonzero elements, whereas the black regions indicate failure. It can be seen that the area of white for the determinant-type measure is larger than that of the l1-norm. It demonstrates that the determinant-type measure outperforms the l1-norm especially when the number of measurements N increases.Figure 2
Illustration of phase transition: (a) determinant-type measure,N=50,100,150,200; (b) l1-norm, N=50,100,150,200 (from left to right).
(a) (b)


### 5.2. Dictionary Recovery

This subsection examines if the proposed algorithm can recover the true analysis dictionary. To quantitatively evaluate the performance, we used synthetic signals with a known ground-truth dictionary.Then, to evaluate the sparsity of the coefficient, we use the Hoyer sparsity [50], which can be normalized to satisfy more of the sparsity constraints [51]:(26)HoyerSparsityx=n-∑xi/∑xi2n-1,where x is a column of the coefficient matrix. The Hoyer sparsity for a matrix is defined as(27)HoyerSparsityX=1N∑i=1NHoyerSparsityxi.The larger the Hoyer sparsity measure, the sparser the coefficient matrix. Note that the sparse representation optimization problem with Hoyer sparsity constraint is hard to solve; thus it is generally used for evaluation.


#### 5.2.1. Experimental Setup

A ground-truth dictionary and observed signals were built as follows. A random synthesis dictionaryW∈R+m×m was generated by taking the absolute values of i.i.d. zero mean, unit variance normal random variables. The analysis dictionary was set as Ω=W-1. A set of observation signals X∈R+m×N was generated by X=WZ; namely, each signal column x was generated by a linear combination of s different atoms in the dictionary, with s nonnegative corresponding coefficients in unity random and independent locations. Naturally, the elements of the observed signals became nonnegative with different sparsities. In this experiment, we chose a set of size N=1000 of such observational signal matrices.To initialize the proposed algorithm, we used a linear model to generate the initial estimate by combining the ground-truth dictionaryΩ0 and a normalized random matrix ϵ, that is, Ωinit=(1-ρ)Ω0+ρϵ, and then projecting it to satisfy the uniformly normalized and orthogonal constraints. When ρ is zero, we actually initialize Ωinit with the ground-truth dictionary Ω0 and when ρ=1, the initial analysis dictionary will be random.The learned analysis dictionary by our algorithm was compared with the ground-truth dictionary. Since there is a row-shuffle indeterminacy, we find corresponding rows by sweeping all rows of the learned dictionary and ground-truth dictionary and finding the closest rows between the two dictionaries. The distance less than 0.01 was considered as a success:(28)maxj⁡mini⁡1-Ωi′TΩ0j<0.01,where Ωi′ was an atom from the learned dictionary, and Ωj was an atom from the ground-truth dictionary.First we use different number of nonzeross. We set s=1,2,3,4,5,6 and ρ=0.9 to see the performance between different sparsity. The Hoyer sparsities of ground-truth coefficient matrices are 1 (s=1), 0.95 (s=2), 0.91 (s=3), 0.87 (s=4), 0.84 (s=5), and 0.81 (s=6). Figure 3 presents the recovery curves of the analysis dictionary Ω0 of size 50×50, from which we can see that the results can reach to 100% in the cases of s=1,5, and 6 and more than 99% in the cases of s=2,3, and 4. Figure 4 presents the Hoyer sparsity of the learned sparse coefficients, which shows the convergence of Hoyer sparsity value of different s and they nearly converge to the Hoyer sparsities of ground-truth coefficient matrices.Figure 3
The recovery curves.Figure 4
The Hoyer sparsity.Next, we investigated the role ofρ. We chose ρ=0.7,0.8,0.9,1.0,1.1,1.2 with s=3 and drew the recovery curves and the Hoyer sparsity. Figure 5 shows the recovery curves of the analysis dictionary with different ρ. From this figure, we can see that the ratio of recovery can reach about 100% in many different situations. Figure 6 presents the Hoyer sparsity of the learned sparse coefficient, which shows the Hoyer sparsity converges to the same value which nearly equal to the ground-truth Hoyer sparsity 0.91 (s=3).Figure 5
The recovery curves.Figure 6
The Hoyer sparsity.Then we compared our proposed algorithm with the existing determinant-type based algorithm SADL-DET [26], which is also applied for nonnegative signals. We compared the recovery rate and the Hoyer sparsity for these algorithms in the case of s=1,3,5. Figure 7 shows the results in the case of s=1, which shows our proposed algorithm converges faster than SADL-DET. Figure 8 shows the results in the case of s=3, which shows our proposed algorithm also converge faster in the recovery curve and can obtain a better recovery rate. Figure 9 shows the results in the case of s=5, which shows that our proposed algorithm can achieve good results.Figure 7
The comparison with SADL-DET whens=1.Figure 8
The comparison with SADL-DET whens=3.Figure 9
The comparison with SADL-DET whens=5.We compared the computational consumption. Figure10 indicates that our proposed algorithm is nearly 103 times faster compared with SADL-DET.Figure 10
The computational consumption.


### 5.3. Image Denoising

We tested our proposed method with a practical problem of image denoising [18]. The noise level and the quality of denoising were evaluated by the peak signal-to-noise ratios (PSNRs (PSNR (dB) is defined as 10log10⁡(2552/x-y), where x and y denote the original signal and the signal polluted by noise, resp.)). The tested images, as also the tested noise levels, are from the Cropped Yale face database (from http://vision.ucsd.edu/extyaleb/CroppedYaleBZip/CroppedYale.zip). Note that, to make sure that the observed signals are nonnegative, the noises we added to the original images are nonnegative uniformly distributed pseudorandom values.Figure11 shows original, noisy, and denoised images by our proposed algorithm. Then, we compare our proposed algorithm with the analysis model based algorithm, Constrained Overcomplete Analysis Operator Learning (COAOL), and we also represent the denoised results using fixed Finite Difference (FD) operator. The average PSNRs of the denoised results for different face cases are presented in Table 1, which shows that our algorithm performs well in image denoising. To intuitively see the denoising performance with different methods, we take faces 05, 10, 15, and 20, for instance. Figure 12 shows the original faces, noisy faces, and denoised faces with different methods, COAOL, ours, and FD. Although COAOL has a good performance for general signals, it cannot achieve good results for nonnegative noise. Our proposed algorithm has outstanding advantage in nonnegative image denoising.Table 1
Image denoising performance of PSNR (dB).
Face ID Noisy level COAOL Proposed FD 01 10.7662 11.0553 19.2743 11.0553 02 10.7675 11.0686 19.0550 11.0152 03 10.7381 11.0324 18.7899 10.9849 04 10.7542 11.0452 18.9949 11.0025 05 10.7918 11.0881 18.4613 11.0410 06 10.7502 11.0408 18.9840 10.9959 07 10.7844 11.0838 19.2423 11.0335 08 10.8030 11.0926 18.7126 11.0541 09 10.7905 11.0792 18.5088 11.0400 10 10.7528 11.0408 18.3358 11.0000 11 10.7764 11.0641 18.7527 11.0242 12 10.7623 11.0429 18.6075 11.0092 13 10.7268 11.0181 17.4434 10.9735 15 10.8005 11.0786 18.9708 11.0487 16 10.7784 11.0660 18.6266 11.0261 17 10.7745 11.0626 19.1770 11.0224 18 10.7546 11.0398 19.0336 11.0031 19 10.7442 11.0307 19.2140 10.9920 20 10.7765 11.0703 18.9491 11.0255Figure 11
Face image denoising. (a) Original face images. (b) Noisy images. (c) Denoised faces using our proposed algorithm.
(a) (b) (c)Figure 12
Face image denoising. (a) Original face images. (b) Noisy images. (c) Denoised faces using COAOL. (d) Denoised faces using our proposed algorithm. (e) Denoised faces using FD.
(a) (b) (c) (d) (e)


## 5.1. Phase Transition

The goal of this phase transition experiment is to study how the proposed algorithm with the determinant-type sparsity measure can identify nonzero elements in a sparse matrixZ∈Rm×N. Specifically, we examine when the success or failure of nonzero element identification switches according to the sparsity of the matrix. We varied the number s of nonzero elements in sparse matrix Z, the number m of the dimensionality of the dictionary atoms, and the number of measurements N. The range for s was from 1 to 10, m from 1 to 10, and N from 50 to 200.Figure2 compares the phase transition diagrams of the determinant-type measure and the l1-norm. The white regions indicate success of identifying nonzero elements, whereas the black regions indicate failure. It can be seen that the area of white for the determinant-type measure is larger than that of the l1-norm. It demonstrates that the determinant-type measure outperforms the l1-norm especially when the number of measurements N increases.Figure 2
Illustration of phase transition: (a) determinant-type measure,N=50,100,150,200; (b) l1-norm, N=50,100,150,200 (from left to right).
(a) (b)


## 5.2. Dictionary Recovery

This subsection examines if the proposed algorithm can recover the true analysis dictionary. To quantitatively evaluate the performance, we used synthetic signals with a known ground-truth dictionary.Then, to evaluate the sparsity of the coefficient, we use the Hoyer sparsity [50], which can be normalized to satisfy more of the sparsity constraints [51]:(26)HoyerSparsityx=n-∑xi/∑xi2n-1,where x is a column of the coefficient matrix. The Hoyer sparsity for a matrix is defined as(27)HoyerSparsityX=1N∑i=1NHoyerSparsityxi.The larger the Hoyer sparsity measure, the sparser the coefficient matrix. Note that the sparse representation optimization problem with Hoyer sparsity constraint is hard to solve; thus it is generally used for evaluation.


### 5.2.1. Experimental Setup

A ground-truth dictionary and observed signals were built as follows. A random synthesis dictionaryW∈R+m×m was generated by taking the absolute values of i.i.d. zero mean, unit variance normal random variables. The analysis dictionary was set as Ω=W-1. A set of observation signals X∈R+m×N was generated by X=WZ; namely, each signal column x was generated by a linear combination of s different atoms in the dictionary, with s nonnegative corresponding coefficients in unity random and independent locations. Naturally, the elements of the observed signals became nonnegative with different sparsities. In this experiment, we chose a set of size N=1000 of such observational signal matrices.To initialize the proposed algorithm, we used a linear model to generate the initial estimate by combining the ground-truth dictionaryΩ0 and a normalized random matrix ϵ, that is, Ωinit=(1-ρ)Ω0+ρϵ, and then projecting it to satisfy the uniformly normalized and orthogonal constraints. When ρ is zero, we actually initialize Ωinit with the ground-truth dictionary Ω0 and when ρ=1, the initial analysis dictionary will be random.The learned analysis dictionary by our algorithm was compared with the ground-truth dictionary. Since there is a row-shuffle indeterminacy, we find corresponding rows by sweeping all rows of the learned dictionary and ground-truth dictionary and finding the closest rows between the two dictionaries. The distance less than 0.01 was considered as a success:(28)maxj⁡mini⁡1-Ωi′TΩ0j<0.01,where Ωi′ was an atom from the learned dictionary, and Ωj was an atom from the ground-truth dictionary.First we use different number of nonzeross. We set s=1,2,3,4,5,6 and ρ=0.9 to see the performance between different sparsity. The Hoyer sparsities of ground-truth coefficient matrices are 1 (s=1), 0.95 (s=2), 0.91 (s=3), 0.87 (s=4), 0.84 (s=5), and 0.81 (s=6). Figure 3 presents the recovery curves of the analysis dictionary Ω0 of size 50×50, from which we can see that the results can reach to 100% in the cases of s=1,5, and 6 and more than 99% in the cases of s=2,3, and 4. Figure 4 presents the Hoyer sparsity of the learned sparse coefficients, which shows the convergence of Hoyer sparsity value of different s and they nearly converge to the Hoyer sparsities of ground-truth coefficient matrices.Figure 3
The recovery curves.Figure 4
The Hoyer sparsity.Next, we investigated the role ofρ. We chose ρ=0.7,0.8,0.9,1.0,1.1,1.2 with s=3 and drew the recovery curves and the Hoyer sparsity. Figure 5 shows the recovery curves of the analysis dictionary with different ρ. From this figure, we can see that the ratio of recovery can reach about 100% in many different situations. Figure 6 presents the Hoyer sparsity of the learned sparse coefficient, which shows the Hoyer sparsity converges to the same value which nearly equal to the ground-truth Hoyer sparsity 0.91 (s=3).Figure 5
The recovery curves.Figure 6
The Hoyer sparsity.Then we compared our proposed algorithm with the existing determinant-type based algorithm SADL-DET [26], which is also applied for nonnegative signals. We compared the recovery rate and the Hoyer sparsity for these algorithms in the case of s=1,3,5. Figure 7 shows the results in the case of s=1, which shows our proposed algorithm converges faster than SADL-DET. Figure 8 shows the results in the case of s=3, which shows our proposed algorithm also converge faster in the recovery curve and can obtain a better recovery rate. Figure 9 shows the results in the case of s=5, which shows that our proposed algorithm can achieve good results.Figure 7
The comparison with SADL-DET whens=1.Figure 8
The comparison with SADL-DET whens=3.Figure 9
The comparison with SADL-DET whens=5.We compared the computational consumption. Figure10 indicates that our proposed algorithm is nearly 103 times faster compared with SADL-DET.Figure 10
The computational consumption.


## 5.2.1. Experimental Setup

A ground-truth dictionary and observed signals were built as follows. A random synthesis dictionaryW∈R+m×m was generated by taking the absolute values of i.i.d. zero mean, unit variance normal random variables. The analysis dictionary was set as Ω=W-1. A set of observation signals X∈R+m×N was generated by X=WZ; namely, each signal column x was generated by a linear combination of s different atoms in the dictionary, with s nonnegative corresponding coefficients in unity random and independent locations. Naturally, the elements of the observed signals became nonnegative with different sparsities. In this experiment, we chose a set of size N=1000 of such observational signal matrices.To initialize the proposed algorithm, we used a linear model to generate the initial estimate by combining the ground-truth dictionaryΩ0 and a normalized random matrix ϵ, that is, Ωinit=(1-ρ)Ω0+ρϵ, and then projecting it to satisfy the uniformly normalized and orthogonal constraints. When ρ is zero, we actually initialize Ωinit with the ground-truth dictionary Ω0 and when ρ=1, the initial analysis dictionary will be random.The learned analysis dictionary by our algorithm was compared with the ground-truth dictionary. Since there is a row-shuffle indeterminacy, we find corresponding rows by sweeping all rows of the learned dictionary and ground-truth dictionary and finding the closest rows between the two dictionaries. The distance less than 0.01 was considered as a success:(28)maxj⁡mini⁡1-Ωi′TΩ0j<0.01,where Ωi′ was an atom from the learned dictionary, and Ωj was an atom from the ground-truth dictionary.First we use different number of nonzeross. We set s=1,2,3,4,5,6 and ρ=0.9 to see the performance between different sparsity. The Hoyer sparsities of ground-truth coefficient matrices are 1 (s=1), 0.95 (s=2), 0.91 (s=3), 0.87 (s=4), 0.84 (s=5), and 0.81 (s=6). Figure 3 presents the recovery curves of the analysis dictionary Ω0 of size 50×50, from which we can see that the results can reach to 100% in the cases of s=1,5, and 6 and more than 99% in the cases of s=2,3, and 4. Figure 4 presents the Hoyer sparsity of the learned sparse coefficients, which shows the convergence of Hoyer sparsity value of different s and they nearly converge to the Hoyer sparsities of ground-truth coefficient matrices.Figure 3
The recovery curves.Figure 4
The Hoyer sparsity.Next, we investigated the role ofρ. We chose ρ=0.7,0.8,0.9,1.0,1.1,1.2 with s=3 and drew the recovery curves and the Hoyer sparsity. Figure 5 shows the recovery curves of the analysis dictionary with different ρ. From this figure, we can see that the ratio of recovery can reach about 100% in many different situations. Figure 6 presents the Hoyer sparsity of the learned sparse coefficient, which shows the Hoyer sparsity converges to the same value which nearly equal to the ground-truth Hoyer sparsity 0.91 (s=3).Figure 5
The recovery curves.Figure 6
The Hoyer sparsity.Then we compared our proposed algorithm with the existing determinant-type based algorithm SADL-DET [26], which is also applied for nonnegative signals. We compared the recovery rate and the Hoyer sparsity for these algorithms in the case of s=1,3,5. Figure 7 shows the results in the case of s=1, which shows our proposed algorithm converges faster than SADL-DET. Figure 8 shows the results in the case of s=3, which shows our proposed algorithm also converge faster in the recovery curve and can obtain a better recovery rate. Figure 9 shows the results in the case of s=5, which shows that our proposed algorithm can achieve good results.Figure 7
The comparison with SADL-DET whens=1.Figure 8
The comparison with SADL-DET whens=3.Figure 9
The comparison with SADL-DET whens=5.We compared the computational consumption. Figure10 indicates that our proposed algorithm is nearly 103 times faster compared with SADL-DET.Figure 10
The computational consumption.


## 5.3. Image Denoising

We tested our proposed method with a practical problem of image denoising [18]. The noise level and the quality of denoising were evaluated by the peak signal-to-noise ratios (PSNRs (PSNR (dB) is defined as 10log10⁡(2552/x-y), where x and y denote the original signal and the signal polluted by noise, resp.)). The tested images, as also the tested noise levels, are from the Cropped Yale face database (from http://vision.ucsd.edu/extyaleb/CroppedYaleBZip/CroppedYale.zip). Note that, to make sure that the observed signals are nonnegative, the noises we added to the original images are nonnegative uniformly distributed pseudorandom values.Figure11 shows original, noisy, and denoised images by our proposed algorithm. Then, we compare our proposed algorithm with the analysis model based algorithm, Constrained Overcomplete Analysis Operator Learning (COAOL), and we also represent the denoised results using fixed Finite Difference (FD) operator. The average PSNRs of the denoised results for different face cases are presented in Table 1, which shows that our algorithm performs well in image denoising. To intuitively see the denoising performance with different methods, we take faces 05, 10, 15, and 20, for instance. Figure 12 shows the original faces, noisy faces, and denoised faces with different methods, COAOL, ours, and FD. Although COAOL has a good performance for general signals, it cannot achieve good results for nonnegative noise. Our proposed algorithm has outstanding advantage in nonnegative image denoising.Table 1
Image denoising performance of PSNR (dB).
Face ID Noisy level COAOL Proposed FD 01 10.7662 11.0553 19.2743 11.0553 02 10.7675 11.0686 19.0550 11.0152 03 10.7381 11.0324 18.7899 10.9849 04 10.7542 11.0452 18.9949 11.0025 05 10.7918 11.0881 18.4613 11.0410 06 10.7502 11.0408 18.9840 10.9959 07 10.7844 11.0838 19.2423 11.0335 08 10.8030 11.0926 18.7126 11.0541 09 10.7905 11.0792 18.5088 11.0400 10 10.7528 11.0408 18.3358 11.0000 11 10.7764 11.0641 18.7527 11.0242 12 10.7623 11.0429 18.6075 11.0092 13 10.7268 11.0181 17.4434 10.9735 15 10.8005 11.0786 18.9708 11.0487 16 10.7784 11.0660 18.6266 11.0261 17 10.7745 11.0626 19.1770 11.0224 18 10.7546 11.0398 19.0336 11.0031 19 10.7442 11.0307 19.2140 10.9920 20 10.7765 11.0703 18.9491 11.0255Figure 11
Face image denoising. (a) Original face images. (b) Noisy images. (c) Denoised faces using our proposed algorithm.
(a) (b) (c)Figure 12
Face image denoising. (a) Original face images. (b) Noisy images. (c) Denoised faces using COAOL. (d) Denoised faces using our proposed algorithm. (e) Denoised faces using FD.
(a) (b) (c) (d) (e)


## 6. Conclusion

In this study, we have proposed a novel and efficient analysis sparse representation algorithm with the determinant-type sparse measure, which focuses on nonnegative signals processing. We separated the whole problem into three subproblems: analysis dictionary updates, sparse coding, and signals recovery. In the sparse coding stage, we employ DC programming to solve the nonconvex minimization problems. The experimental results verify the effectiveness of the proposed algorithm and the determinant measure of sparsity. Remarkable advantages of the proposed algorithm include the faster running time and good performance in image denoising. Moving forward, we can employ the proposed algorithm for more applications, such as image inpainting, superresolution, and other applications.



---

*Source: 2685745-2018-04-24.xml*