Dictionary learning with low mutual coherence constraint

Abstract

This paper presents efficient algorithms for learning low-coherence dictionaries. First, a new algorithm based on proximal methods is proposed to solve the dictionary learning (DL) problem regularized with the mutual coherence of dictionary. This is unlike the previous approaches that solve a regularized problem where an approximate incoherence promoting term, instead of the mutual coherence, is used to encourage low-coherency. Then, a new solver is proposed for constrained low-coherence DL problem, i.e., a DL problem with an explicit constraint on the mutual coherence of the dictionary. As opposed to current methods, which follow a suboptimal two-step approach, the new algorithm directly solves the associated DL problem. Using previous studies, convergence of the new schemes to critical points of the associated cost functions is also provided. Furthermore, it is shown that the proposed algorithms have lower iteration complexity than existing algorithms. Our simulation results on learning low-coherence dictionaries for natural image patches as well as image classification based on discriminative over-complete dictionary learning demonstrate the superiority of the proposed algorithms compared with the state-of-the-art method.

Introduction

Sparsity has been a key concept in a wide range of signal processing and machine learning problems over the last decade [1]. In particular, sparse signal approximation has been extensively utilized in a variety of applications, including image enhancement [2], [1]. To be more precise, let $\mathbf{y}\in {\mathbb{R}}^n$ denote the target signal, and ${\left\{{\mathbf{d}}_i\right\}}_{i=1}^N$ be a number of N atoms collected as the columns of a so-called dictionary $\mathbf{D}=[{\mathbf{d}}_1,\cdots ,{\mathbf{d}}_N]$. For more flexibility, the dictionary is usually chosen to be overcomplete, i.e., $N>n$. Then, the approximation of $\mathbf{y}$ over $\mathbf{D}$ is written as $\mathbf{y}\approx {\sum }_{i=1}^N{x}_i{\mathbf{d}}_i=\mathbf{Dx}$, where $\mathbf{x}\in {\mathbb{R}}^N$ is called the sparse representation vector, with most of its entries being zero. The sparse approximation problem is to find the sparsest $\mathbf{x}$. To this end, the following problem has to be solved:

$${\displaystyle \underset{\mathbf{x}}{\min }}\Vert \mathbf{x}{\Vert }_0\mathrm{s}.\mathrm{t}.\Vert \mathbf{y}-\mathbf{Dx}{\Vert }_2⩽∊,$$

where $\Vert .{\Vert }_0$, the so-called ${\ell }_0$(pseudo) norm, returns the number of non-zero entries, and $∊⩾0$ is an error tolerance. Various sparse recovery algorithms have been proposed, which are summarized in [3].

Dictionary has an important role in sparse approximation problems. There exist some predefined choices for the dictionary, including discrete cosine transform (DCT) for natural images and Gabor dictionaries for speech signals [4]. Nevertheless, it has been shown that learned dictionaries optimized over a set of training signals outperform predefined ones in many applications [1], [4], [5], [6], [7]. This process is known as dictionary learning (DL) [4]. In DL, given a training data matrix $\mathbf{Y}=[{\mathbf{y}}_1,\cdots ,{\mathbf{y}}_M]$, a dictionary $\mathbf{D}$ is learned from $\mathbf{Y}$, in such a way that it provides sparse enough representations for ${\mathbf{y}}_i$’s. This task can be formulated as the following problem

$${\displaystyle \underset{\mathbf{D}\in \mathcal{D},\mathbf{X}\in \mathcal{X}}{\min }}\frac{1}{2}\Vert \mathbf{Y}-\mathbf{DX}{\Vert }_F^2,$$

where $\Vert .{\Vert }_F$ is the Frobenius norm, and $\mathcal{D}$ and $\mathcal{X}$ are admissible sets of $\mathbf{D}$ and $\mathbf{X}$, respectively. $\mathcal{D}$ is usually defined as $\mathcal{D}\triangleq \left\{\mathbf{D}\in {\mathbb{R}}^{n\times N}|\forall i,\Vert {\mathbf{d}}_i{\Vert }_2=1\right\}$, which will be also considered in this paper. Furthermore, the set $\mathcal{X}$ constrains $\mathbf{X}$ to have sparse columns.

Numerous DL algorithms have been proposed [8], which follow an alternating minimization approach to solve the DL problem in (2). That is, starting with an initial estimate for the dictionary, most DL solvers alternate between the following two stages:

• Sparse approximation (SA): The training signals are sparsely approximated over the current estimate of $\mathbf{D}$.

• Dictionary update (DU): The dictionary is updated by minimizing the approximation error of the SA stage.

To ensure computational tractability and successful performance of sparse approximation algorithms, the dictionary must satisfy certain properties. In fact, substantial efforts in investigating the theoretical aspect of the sparse approximation problem have revealed that the uniqueness and stability of sparse approximation are directly related to the dictionary [9], [10]. Mutual coherence (MC) [11] and restricted isometry property (RIP) [9] are two fundamental tools for evaluating the goodness of a dictionary. The MC for a dictionary $\mathbf{D}$ with normalized columns is defined as

$$\mu (\mathbf{D})\triangleq {\displaystyle \underset{i\ne j}{\max }}|〈{\mathbf{d}}_i,{\mathbf{d}}_j〉|·$$

MC simply measures the similarity between distinct atoms of a dictionary. For $n\times N$ dictionaries, the MC is lower bounded via

$$\mu ⩾\sqrt{\frac{N-n}{n(N-1)}},$$

which is known as the Welch bound [12]. In addition, $\mathbf{D}$ is said to satisfy RIP of order s with constant ${\delta }_s$ if for any s-sparse signal $\mathbf{x}$ we have [13]

$$(1-{\delta }_s)\Vert \mathbf{x}{\Vert }_2^2⩽\Vert \mathbf{Dx}{\Vert }_2^2⩽(1+{\delta }_s)\Vert \mathbf{x}{\Vert }_2^2·$$

The existing RIP-based performance guarantees for sparse approximation algorithms show that smaller values for ${\delta }_s$ are favorable. Intuitively, according to (5), when ${\delta }_s\to 0$ the dictionary behaves as an orthonormal basis and, so, the stability and uniqueness of the approximation are better satisfied. Evaluating the RIP for a dictionary, however, is an NP-hard problem [14]. Nevertheless, it can be roughly verified using MC. In fact, it has been shown that RIP and MC for a dictionary are linked via ${\delta }_s⩽\mu (s-1)$[13]. Furthermore, it can be shown that ${\delta }_2=\mu$[1]. Consequently, MC as a practical measure of performance has received much attention [15], [16], [17].

Besides the sole sparse approximation problem, recent work indicates that MC and RIP play effective roles in theoretical investigations of the DL problem as a whole. For instance, it is argued in [18], [19] that a ground truth dictionary would be a local minimum to the DL cost function with an ${\ell }_1$ norm as the sparsity measure, provided that it is sufficiently incoherent along with some other assumptions on the problem parameters. In this case, the dictionary is said to be locally identifiable [18]. Moreover, Wu and Yu [19] showed recently that, under some conditions, the local identifiability is possible with sparsity level s to the order $\mathcal{O}({\mu }^{-2})$ for a complete dictionary ($n=N$) with the MC value of $\mu$. Also, in [20], RIP has been used as a determining assumption in providing local linear convergence for the alternating minimization approach used to solve the DL problem.

The importance of MC, explained by the above discussions, has inspired some work to propose algorithms for learning low-MC dictionaries. These work can be classified into two main groups: regularized and constrained approaches. The first group [21], [22], [23] targets the following problem to update the dictionary

$${\displaystyle \underset{\mathbf{D}\in \mathcal{D}}{\min }}\frac{1}{2}\Vert \mathbf{Y}-\mathbf{DX}{\Vert }_F^2+\lambda \mathcal{R}(\mathbf{D}),$$

where $\lambda \ge 0$ is a regularization parameter, and

$$\mathcal{R}(\mathbf{D})\triangleq \Vert {\mathbf{D}}^T\mathbf{D}-\mathbf{I}{\Vert }_F^2·$$

The use of $\mathcal{R}$ as an incoherence promoting term is motivated by the following relation

$$\mathcal{R}(\mathbf{D})={\displaystyle \sum _{i\ne j}}|〈{\mathbf{d}}_i,{\mathbf{d}}_j〉{|}^2+{\displaystyle \sum _i}{(〈{\mathbf{d}}_i,{\mathbf{d}}_i〉-1)}^2,$$

where the first term is responsible for minimizing the average squared inner-products between distinct atoms, and the last term encourages the atoms to have unit norms.

The second group of methods aims at solving the following constrained problem

$${\displaystyle \underset{\mathbf{D}\in \mathcal{D}}{\min }}\frac{1}{2}\Vert \mathbf{Y}-\mathbf{DX}{\Vert }_F^2\mathrm{s}.\mathrm{t}.\mu (\mathbf{D})⩽{\mu }_0,$$

in which, ${\mu }_0>0$ is a fixed target MC level. Incoherent K-SVD (INK-SVD) [24] and iterative projection-rotation DL (IPR-DL) [25] are sample algorithms of this group. INK-SVD solves (9) by first finding the minimizer (denoted by $\overline{\mathbf{D}}$) ignoring the MC constraint and, then, solving the following matrix nearness problem to reach the desired mutual coherence:

$${\displaystyle \underset{\mathbf{D}}{\min }}\frac{1}{2}\Vert \mathbf{D}-\overline{\mathbf{D}}{\Vert }_F^2\mathrm{s}.\mathrm{t}.\mu (\mathbf{D})⩽{\mu }_0·$$

To solve (10), the authors of [24] proposed a decorrelation step in which sub-dictionaries of highly correlated atoms are iteratively identified and pairs of atoms are decorrelated until the desired MC, namely ${\mu }_0$, is reached. A disadvantage of this approach, as pointed out in [25], is that, the approximation error, i.e., $\Vert \mathbf{Y}-\mathbf{DX}{\Vert }_F$, is not explicitly taken into account during the decorrelation process. To overcome this problem, Barchiesi et al. [25] proposed a novel decorrelation scheme, consisting of two steps. In the first step, called atoms decorrelation, an iterative projection algorithm is performed that ensures that the mutual coherence constraint is satisfied. This step is then followed by a dictionary rotation in which the dictionary is rotated to minimize the approximation error, without affecting its mutual coherence. This algorithm shows state-of-the-art performance, as confirmed by the simulations of [25].

In this paper, we propose new algorithms for learning low-coherence dictionaries. Our motivation is that the previous work cannot efficiently compromise between the representation ability of the learned dictionary and its MC. More precisely, as will be seen later in Section 2, the term $\mathcal{R}$ used in (6) is a very rough approximation to MC. In fact, as its definition in (8) implies, using this term only the average squared inner-products between distinct atoms are penalized. Therefore, it is not particularly effective to minimize the maximum absolute inner-products between any two atoms, i.e., the MC. Furthermore, when $\lambda \to \infty$, problem (6) reduces to

$${\displaystyle \underset{\mathbf{D}\in \mathcal{D}}{\min }}\mathcal{R}(\mathbf{D}),$$

whose solutions are unit-norm tight-frames (UNTFs) [26], [27] which are not guaranteed to have small enough MCs compared to what one would expect in this extreme scenario. In other words, a UNTF may have a large MC. So, one would need to further optimize it to achieve a small enough MC [28].

To address this issue, we introduce a new algorithm based on proximal methods [29] to solve the regularized (unconstrained) low-coherence DL problem that directly uses the MC definition in (3) instead of the approximate term $\mathcal{R}$. Our simulations reveal that the new algorithm is able to learn dictionaries with MCs far smaller than what the algorithms targeting problem (6) achieve. Additionally, it makes much better compromise between adapting the dictionary to the training set and minimizing the MC.

On the other hand, IPR-DL, as the state-of-the-art algorithm, does not solve (9) directly. Moreover, singular value decomposition (SVD) and eigenvalue decomposition (EVD) are used in its structure, which are expensive operations from computational load and memory usage points of view, especially in high-dimensional data settings. Our next algorithm solves the constrained low-coherence DL problem (9) directly, without resorting to a suboptimal approach as in INK-SVD and IPR-DL. In addition, the proposed algorithm does not use SVD or EVD. As will be seen in Section 5, compared with IPR-DL, our proposed unconstrained algorithm is able to efficiently minimize the approximation error while satisfying the target level of MC.

Our proposed regularized low-coherence DL algorithm has already been introduced in a conference paper [30]. However, the algorithm proposed in the current work is different from the one presented in [30]. More precisely, in [30] an atom-by-atom approach is taken that updates the atoms sequentially. However, in this work, we consider updating all the atoms at once. Moreover, here, we consider the constrained low-coherence DL problem, too, and in addition to presenting a new solver for the constrained case, we provide convergence guarantees for the dictionary update steps of both regularized and constrained problems based on previous studies.

The rest of the paper is presented in the following order. In Section 2, our new regularized low-coherence DL algorithm is introduced. The proposed constrained low-coherence DL algorithm is introduced in Section 3. Some discussions concerning the implementations of our new algorithms and a computational complexity analysis are given in Section 4. Simulation results will be reported in Section 5.

Throughout the paper, small and capital bold face characters are used for vector- and matrix-valued quantities, respectively. The $(i,j)$-th entry of a matrix $\mathbf{X}$ is denoted by $x_{\mathit{ij}}$, while ${\mathbf{x}}_i$ designates its i-th column. The superscript T stands for matrix transposition. The identity matrix is denoted by $\mathbf{I}$. For a vector $\mathbf{x}$, its ${\ell }_p$ norm ($p⩾1$) is defined via $\Vert \mathbf{x}{\Vert }_p\triangleq {({\sum }_i|x_i{|}^p)}^{1/p}$. For a matrix $\mathbf{X}$, we denote its ${\ell }_{\infty }$ norm¹ by $\Vert \mathbf{X}{\Vert }_{\infty }$ and define it as $\Vert \mathbf{X}{\Vert }_{\infty }\triangleq {\max }_{i,j}|x_{\mathit{ij}}|$. An ${\ell }_p$ norm-ball of radius r in ${\mathbb{R}}^n$ and centered around the origin is defined as ${\mathcal{B}}_p^r\triangleq \left\{\mathbf{x}\in {\mathbb{R}}^n|\Vert \mathbf{x}{\Vert }_p⩽r\right\}$. The same notation is used for ${\ell }_p$ matrix norm-ball. For two vectors $\mathbf{u}$ and $\mathbf{v}$ in ${\mathbb{R}}^n$, their inner-product is represented as $〈\mathbf{u},\mathbf{v}〉\triangleq {\sum }_i{u}_i{v}_i$. The indicator function of a set $\mathcal{S}$ is denoted by ${\mathcal{I}}_{\mathcal{S}}(\mathbf{x})$ which takes a value of 0 when $\mathbf{x}\in \mathcal{S}$, and $\infty$ otherwise. The vectorization operator is denoted by $\mathrm{vec}(.)$, which converts its matrix argument to an equivalent column vector by stacking its columns on top of each other. The inverse vectorization operator is also denoted by ${\mathrm{vec}}^{-1}(.)$. Moreover,

Definition 1 [29]

The Euclidean projection of a point $\mathbf{x}\in {\mathbb{R}}^n$ to a non-empty set $\mathcal{S}\subseteq {\mathbb{R}}^n$ is defined as

$$P_{\mathcal{S}}(\mathbf{x})\triangleq \underset{\mathbf{u}\in \mathcal{S}}{\mathrm{argmin}}\frac{1}{2}\Vert \mathbf{x}-\mathbf{u}{\Vert }_2^2·$$

Definition 2

[29] The proximal mapping of a convex function $g:\mathrm{dom}g⟶\mathbb{R}$ is defined as

$${\mathrm{prox}}_g(\mathbf{x})\triangleq \underset{\mathbf{u}\in \mathrm{dom}g}{\mathrm{argmin}}\left\{\frac{1}{2}\Vert \mathbf{x}-\mathbf{u}{\Vert }_2^2+g(\mathbf{u})\right\}·$$

For $g(\mathbf{x})={\mathcal{I}}_{\mathcal{S}}(\mathbf{x})$, the proximal mapping is simply the projection onto $\mathcal{S}$[29]. That is,

$${\mathrm{prox}}_{{\mathcal{I}}_{\mathcal{S}}}(\mathbf{x})=P_{\mathcal{S}}(\mathbf{x})·$$