Dictionary learning with the cosparse analysis model based on summation of blocked determinants as the sparseness measure

Abstract

Dictionary learning is crucially important for sparse representation of signals. Most existing methods are based on the so called synthesis model, in which the dictionary is column redundant. This paper addresses the dictionary learning and sparse representation with the so-called analysis model. In this model, the analysis dictionary multiplying the signal can lead to a sparse outcome. Though it has been studied in the literature, there is still not an investigation in the context of dictionary learning for nonnegative signal representation, while the algorithms designed for general signal are found not sufficient when applied to the nonnegative signals. In this paper, for a more efficient dictionary learning, we propose a novel cost function that is termed as the summation of blocked determinants measure of sparseness (SBDMS). Based on this measure, a new analysis sparse model is derived, and an iterative sparseness maximization scheme is proposed to solve this model. In the scheme, the analysis sparse representation problem can be cast into row-to-row optimizations with respect to the analysis dictionary, and then the quadratic programming (QP) technique is used to optimize each row. Therefore, we present an algorithm for the dictionary learning and sparse representation for nonnegative signals. Numerical experiments on recovery of analysis dictionary show the effectiveness of the proposed method.

Introduction

Many natural signals are distributed in a high dimensional space. They can be modeled using low-dimensional structures and be represented using just a few parameters in an appropriate model [1]. Signal models are the cores of various signal and image processing tasks, such as compression, denoising, sampling, inpainting and so on [2]. Essentially, a signal model is a set of mathematical properties that the data is believed to satisfy [3]. A good model should be simple while matching the signals. In the past decade, the sparse and redundant representation model has been proved to be important and useful [4], [5]. Most existing methods for these are based on a so called synthesis model for describing signals. Here we describe this model briefly.

Assume that we are to model the signal $\mathbf{X}\in {\Re }^{m\times N}$. The synthesis model suggests that the signal could be described as

$$\mathbf{X}=\mathbf{DH},$$

or

$$\mathbf{X}\approx \mathbf{DH},\text{<mi mathvariant="italic" is="true">s.t.</mi>}{\Vert \mathbf{X}-\mathbf{DH}\Vert }_F\le \epsilon ,$$

where $\mathbf{D}\in {\Re }^{m\times n}$ is a possible dictionary [6]. Since $(m\le n)$, where it contains n atoms of size $m\times 1$, the dictionary is column overcomplete, i.e., redundant. Here $\mathbf{H}\in {\Re }^{n\times N}$ is the representation coefficient matrix. If the purpose is for a sparse representation, it is assumed that the representation H is sparse. That is, most elements are 0-valued, which means each signal element can be represented as a linear combination of few columns of the dictionary D. The name “synthesis” comes from the relation $\mathbf{X}=\mathbf{DH}$, with the interpretation that the model describes a way to synthesize signals X [3].

There have been many publications that are based on the synthesis model; a long series of applications in signal and image processing with this model demonstrate state-of-the-art results [8]. It can be safely said that the synthesis model is a mature and stable field [3]. And this model has been heavily investigated in the last decade and many remarkable results achieved in almost all signal processing applications, the examples in [8], [9]. However, in this model, the error ${\Vert \mathbf{X}-\mathbf{DH}\Vert }_F$ as the cost function is usually non-convex so that the optimization problem with the mode is hard to solve mathematically, and the deduced algorithm is complicated in computation.

Interestingly, the synthesis model has a “twin” model that takes an analysis point of view [3]. Assume that there is $\mathbf{\Omega }\in {\Re }^{n\times m}$ so that Ω can be used to find sparse H so that $\mathbf{H}=\mathbf{\Omega }\mathbf{X}$. This analysis model can be converted as a minimization problem of the error function ${\Vert \mathbf{H}-\mathbf{\Omega }\mathbf{X}\Vert }_F$. Remarkable, this error function is convex, contrasting the nonconvexity of the synthesis model, and the optimization will become easier so that it can be solved by some simpler optimization methods. To emphasize the difference with that in the synthesis model, the term “co-sparsity” has been introduced in literature [3], [7], which simply counts the number of zero elements of $\mathbf{\Omega }\mathbf{X}$ [10]. The analysis model relies on a matrix $\mathbf{\Omega }\in {\Re }^{n\times m}$, which we refer to as the analysis dictionary. Here “analysis” means the dictionary analyzes the signal to produce a sparser result [11]. Different from the synthesis model, the rows of analysis dictionary represent analysis atoms.

Now we look carefully at the analysis model mentioned above. It seems to be similar to the synthesis model. First, let $\mathbf{\Omega }\in {\Re }^{n\times m}$ be a signal transformation or an analysis operator. Its rows are the row vectors which will be applied to the signal. To capture various aspects of the information in the signal by shorten signal, we typically have $m\le n$. Since there is a relationship between the synthesis sparse dictionary and the analysis sparse dictionary by the equation $\mathbf{D}={\mathbf{\Omega }}^{†}$. Then we can use the result obtained from the analysis model for obtaining a result for the synthesis model, in some special cases ($m=n$ or ${\mathbf{\Omega }}^{†}$ existing). The analysis model plays important roles in applications, such as low-dimensional signal model [41], image denoising or inpainting, bimodal super-resolution and image registration [2], [21], [37], [38].

In the past decade, a great deal of effort has been dedicated to learn the dictionary for the synthesis model; however, the analysis dictionary learning problem has received less attention with only a few algorithms proposed recently [2], [11], [12], [13], [14], [15]. Exploiting the fact that a row of the analysis dictionary is orthogonal to a subset of signals X, a sequential minimal eigenvalue based analysis dictionary learning algorithm is proposed in [12]. In [13], [16], [17], [36], an ${\ell }_1$ norm penalty function is imposed to the sparse coefficient and a projected subgradient-based algorithm is proposed for the analysis dictionary learning. The authors of [36] formulate the learning task as a bilevel-programming optimization problem, which in turn is handled using the gradient descent optimization. These works employ a uniformly normalized tight frame as a constraint on the dictionary to avoid the trivial solution. In [2], the Analysis K-SVD (AK-SVD) algorithm is proposed for analysis dictionary learning. By keeping Ω fixed, the optimal backward greedy algorithm (OBG) is employed to estimate a submatrix of Ω whose rows are then used to determine a submatrix and the eigenvector associated with the smallest eigenvalue of this submatrix is then used to update Ω. Greedy Analysis Pursuit is proposed in [18]. This paper presented preliminary and simplified versions of analysis IHT (AIHT), analysis HTP (AHTP), analysis CoSaMP (ACoSaMP) and Analysis SP (ASP) in [19], [20] as analysis versions of the synthesis counterpart methods. The article [21] proposed analysis thresholding algorithm for analysis sparse representation, the analysis reveals significant properties of the dictionary, which govern the pursuit performance. The first is the degree of linear dependencies between sets of rows in the dictionary, depicted by the co-sparsity level. The second property, termed the Restricted Orthogonal Projection Property, is the level of independence between such dependent sets and other rows in Ω. The authors of [39] take a very different route towards the dictionary learning problem, employing a constraint combining the unit row norm and the full rank constraint, with an additional consideration that the analysis operator has no trivially linear dependent rows. As these approaches have shown promising empirical results, we expect that this will open the door to explore the analysis sparse representation more broadly.

As mentioned above, studies on analysis model have led to several dictionary learning algorithms, such as the analysis K-SVD [2], Greedy Analysis Pursuit (GAP) [18], the analysis thresholding algorithm [21]. However, there are lesser investigations in the context of analysis dictionary learning for nonnegative signal representation. In practice some particular signals such as spectral data have the limitations of nonnegativity, including the factorization factors obtained by some specific data analysis [22], [23]. The purpose of this paper is just to address the problem on nonnegative analysis sparse representation.

In this paper, we presented a novel algorithm of analysis dictionary learning for nonnegative signal representation, which is parallel to the synthesis model in its rationale and structure. The algorithm utilizes the summation of blocked determinants of sparseness measure as the sparse constraints. The optimization of the error function can be cast into a series of QP problems, which can be easily solved. Finally, an efficient QP algorithm was developed to perform nonnegative analysis sparse representation. We will describe details of the proposed method in the following sections.

Notations used in this paper are as follows. A bold uppercase letter, such as H, denotes a matrix and a bold lowercase letter h denotes a vector. ${\mathbf{H}}^T$ is the transpose of the matrix H, ${\mathbf{H}}^{†}$ is the pseudo-inverse of matrix H and ${\mathbf{H}}^{-1}$ denotes the inverse of matrix H. $\det (\mathbf{H})$ denotes the determinant value of matrix H. h is the column vector in H. The notation ${(\cdot )}_{ij}$, has been used to specify the element locating in the i-th row and j-th column of the operand matrix. Also, we define the ${\ell }_0$ norm of a vector as ${\Vert \mathbf{h}\Vert }_0={\sum }_i{|h_i|}_0$, and the ${\ell }_1$ norm of a matrix as ${\Vert \mathbf{H}\Vert }_1={\sum }_{ij}{|H_{ij}|}_1$.

The remainder of this paper is organized as follows. Section 2, we firstly introduce the analysis model with the sparsity constraints. In Section 3, we describe the problem formulation of the analysis sparse model. The detailed algorithm is described in Section 4. Then we describe the computation complexity of our algorithm in Section 5. In Section 6 we present experimental results for the proposed algorithm and compare these results. We use synthesis data for numerical experiments. Finally, conclusions are drawn in Section 7.