7.1.2.1 Dictionary Learning

Recent researches on dictionary learning have demonstrated that a well-learned dictionary will greatly boost the performance by yielding a better representation in human action recognition [21], scene categorization [22], and image coloration [23].

A sparse representation based classification (SRC) method for robust face recognition was proposed by Wright et al. Suppose we have c classes of a training set $X=[X_1,X_2,\dots ,X_c]$ where $X_i\in {\mathbb{R}}^{d\times n_i}$ is the training sample from the ith class with dimension d and $n_i$ samples. The SRC procedure is specified by two phases to classify a given test sample $x_{\text{test}}$. First, in the coding phase, we solve the following $l_1$-norm minimization problem:

$\overline{a}=\arg \underset{a}{\min }{\Vert x_{\text{test}}-Xa\Vert }_2^2+\lambda {\Vert a\Vert }_1,$

in which the $l_1$-norm is used as the convex envelope to replace the $l_0$-norm in order to avoid an NP-hard problem and while keeping the sparsity. Then the classification is done via

$\text{identity}(x_{\text{test}})=\arg \underset{i}{\min }{\epsilon }_i,$

where ${\epsilon }_i={\Vert x_{\text{test}}-X_i{\overline{a}}_i\Vert }_2$, and ${\overline{a}}_i$ is the coefficient vector associated with class i. SRC classifies a test image by picking the smallest reconstruction error ${\epsilon }_i$.

Instead of directly using the training set itself as a dictionary, several algorithms and regularizations have been introduced into the dictionary learning framework to learn a compact dictionary with more representation power. In FDDL, a set of class-specified sub-dictionaries whose atoms correspond to the class labels are updated iteratively based on the Fisher discrimination criterion to include discriminative information. Jiang et al. presented a Label Consistent K-SVD (LC-KSVD) algorithm to make a learned dictionary more discriminative for sparse coding [10]. These methods have shown that a structured dictionary could dramatically improve classification performance. However, the performance of these methods will drop a lot if the training data is largely corrupted.

Recently introduced low-rank dictionary learning [12] aims to uncover the global structure by grouping similar samples into one cluster, which has been successfully applied to many applications, e.g., object detection [13], multi-view learning [14], unsupervised subspace segmentation [15], and 3D visual recovery [16]. The goal is to generate a low-rank matrix from corrupted original input data. That is, if a given data matrix X is corrupted by a sparse matrix E while the samples share a similar pattern, then the sparse noisy matrix can be separated to practically recover X via rank minimization. According to the previous research, many works have integrated low-rank regularization into sparse representation for separating the sparse noises from inputs signals while simultaneously optimizing the dictionary atoms in order to faithfully reconstruct the de-noised data. Moreover, a low-rank dictionary addresses the noisy data well by adding an error term with different norms, e.g., $l_1$-norm, $l_{2,1}$-norm.

Applying augmented Lagrange multipliers (ALM), Lin [24] proposed Robust PCA, with which the corrupted data in a single subspace can be recovered by solving a matrix rank minimization problem. In [12], Liu et al. proposed converting the task of face image clustering into a subspace segmentation problem with the assumption that face images from different individuals lie in different, nearly independent subspaces.

7.1.2.2 Auto-encoder

Most recently, deep learning has attracted a lot of interest when looking for better feature extraction. In this direction, auto-encoder [18] is one of the most popular building blocks to form a lite-version deep learning framework. The auto-encoder has drawn increasing attention in the feature learning area and has been considered as a simulation of the way the human visual system processes imagery. The auto-encoder architecture explicitly involves two modules, an encoder and a decoder. The encoder outputs a group of hidden representation units, which is realized by a linear deterministic mapping with a weight matrix and a nonlinear transformation employing a logistic sigmoid. The decoder reconstructs the input data based on the received sparse hidden representation. The aforementioned dictionary learning model can be formalized as a decoder module.

As a typical single hidden layer neural network with identical input and target, the auto-encoder [29] aims to discover data's intrinsic structure by encouraging the output to be as similar to the target as possible. Essentially, the neurons in the hidden layer can be seen as a good representation since they are able to reconstruct the input data. To encourage structured feature learning, further constraints have been imposed on the parameters during training.

Moreover, there is a well-known trick of the trade to deal with noisy data, that is, manually injecting noise into the training samples thereby learning with artificially corrupted data. Denoising auto-encoders (DAEs) [30,18], learned with artificial corrupted data as input, have been successfully applied to a wide range of machine learning tasks by learning a new denoising representation. During the training process, DAEs reconstruct the input data from partial corruption with a pre-specified corrupting distribution to its original clean version. This process learns a robust representation which ensures tolerance to certain distortions in input data.

On this basis, stacked denoising auto-encoders (SDAs) [19] have been successfully used to learn new representations and attained record accuracy on standard benchmark for domain adaptation. However, there are two crucial limitations of SDAs: (i) high computational cost, and (ii) lack of scalability to high-dimensional features. To address these two problems, the authors of [20] proposed marginalized SDAs (mSDA). Different from SDAs, mSDA marginalizes noise and thus the parameters can be computed in closed-form rather than using stochastic gradient descent or other optimization algorithms. Consequently, mSDA significantly speeds up SDAs by two orders of magnitude.

Wang et al. [28] explored the effectiveness of a locality constraint on two different types of feature learning technique, i.e., dictionary learning and auto-encoder, respectively. A locality-constrained collaborative auto-encoder (LCAE) was proposed to extract features with local information for enhancing the classification ability. In order to introduce locality into the coding procedure, the input data is first reconstructed by LLC coding criteria and then used as the target of the auto-encoder. That is, target $\hat{x}$ is replaced by a locality reconstruction as follows:

$\begin{array}{c}\hfill \underset{C}{\min }{\sum }_{i=1}^N{\Vert x_i-D{c}_i\Vert }^2+\lambda {\Vert l_i\odot c_i\Vert }^2\hfill \\ \hfill \text{ s.t. }{\mathbf{1}}^T{c}_i=1,\forall i,\hfill \end{array}$

where dictionary D will be initialized by PCA on the input training matrix X. The proposed LCAE can be trained using the backpropagation algorithm, which updates W and b by backpropagating the reconstruction error gradient from the output layer to the locality coded target layer.

In this chapter, the introduced model jointly learns the auto-encoder and dictionary to benefit from both techniques. To make the model fast, a lite version of the auto-encoder, i.e., marginalized denoising auto-encoder [20] is adapted, which has shown appealing performance and efficiency. Furthermore, there are several benchmarks used to evaluate the proposed algorithm, and the experimental results show its better performance compared to the state-of-the-art methods.

7.1.3.1 Preliminaries and Motivations

In this section, we introduce a feature learning model by unifying the marginalized denoising auto-encoder and locality-constrained dictionary learning (MDDL) together to simultaneously benefit from their merits [1]. Specifically, dictionary learning manages handling corrupted data from the sample space, while marginalized auto-encoder attempts to deal with the noisy data from the feature space. Thus, the algorithm aims to work well with the corrupted data from both the sample and feature spaces by integrating dictionary learning and auto-encoder into a unified framework. The key points of this introduced framework are listed as follows:

Consider a matrix $X=[x_1,x_2,\dots ,x_n]$ having n samples. A low-rank representation tries to segment these samples by minimizing the following objective function:

$\arg \underset{Z}{\min }{\Vert Z\Vert }_{⁎}\text{s.t. }X=DZ,$

where ${\Vert \cdot \Vert }_{⁎}$ denotes the nuclear norm and Z is the coefficient matrix. In the subspace segmentation problem, a low-rank approximation is enforced by minimizing the error between X and its low rank representation ($D=X$). By applying low-rank regularization in dictionary updating, the DLRD [25] algorithm achieved impressive results, especially when corruption exists. Jiang et al. proposed a sparse and dense hybrid representation based on a supervised low-rank dictionary decomposition to learn a class-specific dictionary and erase non-class-specific information [26]. Furthermore, supervised information has been well utilized to seek a more discriminative dictionary [11,17]. In the introduced model, supervised information is also adopted to learn multiple sub-dictionaries so that samples from the same class are drawn from one low-dimensional subspace.

Above-mentioned sparse representation based methods consider each sample as an independent sparse linear combination, this assumption fails to exploit the spatial consistency between neighboring samples. Recent research efforts have yielded more promising results on the task of classification by using the idea of locality [27]. The method named Local Coordinate Coding (LCC), which specifically encourages the coding to rely on local structure, has been presented as a modification to sparse coding. In [27] the author also theoretically proved that locality is more essential than sparsity under certain assumptions. Inspired by the above learning techniques, Wang et al. proposed a Locality-Constrained Low-Rank Dictionary Learning (LC-LRD) to enhance the identification capability by using the geometric structure information [28].

7.1.3.2 LC-LRD Revisited

Given a set of training data $X=[X_1,X_2,\dots ,X_c]\in {\mathbb{R}}^{d\times n}$, where d is the feature dimensionality, n is the number of total training samples, c is the number of classes, and $X_i\in {\mathbb{R}}^{d\times n_i}$ is the sample from class i which has $n_i$ samples. The goal of dictionary learning is to learn an m atoms dictionary $D\in {\mathbb{R}}^{d\times m}$ which yields a sparse representation matrix $A\in {\mathbb{R}}^{m\times n}$ from X for future classification tasks. Then we can write $X=DA+E$, where E is the sparse noise matrix. Rather than learning the dictionary as a whole from all the training samples, we learn sub-dictionary $D_i$ for the ith class separately. Then A and D could be written as $A=[A_1,A_2,\dots ,A_c]$ and $D=[D_1,D_2,\dots ,D_c]$, where $A_i$ is the sub-matrix that denotes the coefficients for $X_i$ over D.

In [28], Wang et al. have proposed the following LC-LRD model for each sub-dictionary:

$\begin{array}{c}\hfill \underset{D_i,A_i,E_i}{\min }R(D_i,A_i)+\alpha {\Vert D_i\Vert }_{⁎}+\beta {\Vert E_i\Vert }_1\hfill \\ \hfill +\lambda \sum _{k=1}^{n_i}{\Vert l_{i,k}\odot a_{i,k}\Vert }^2,\text{ s.t. }{X}_i=D{A}_i+E_i,\hfill \end{array}$

where $R(D_i,A_i)$ is the Fisher discriminant regularization on each sub-dictionary, ${\Vert D_i\Vert }_{⁎}$ is the nuclear norm to enforce low-rank properties, and ${\Vert l_{i,k}\odot a_{i,k}\Vert }^2$ is a locality constraint to replace sparsity on the coding coefficient matrix; $a_{i,k}$ denotes the kth column in $A_i$, which means the coefficient for the kth sample in class i. This model was broken down into the following modules: discriminative sub-dictionaries, low-rank regularization term, and the locality constraint on the coding coefficients.

Sub-dictionary $D_i$ should be endowed with the discrimination power to well represent samples from the ith class. Mathematically, the coding coefficients of $X_i$ over D can be written as $A_i=[A_i^1;A_i^2;\dots ;A_i^c]$, where $A_i^j$ is the coefficient matrix of $X_i$ over $D_j$. The discerning power of $D_i$ is produced by following two aspects: first, it is expected that $X_i$ should be well represented by $D_i$ but not by $D_j$, $j\ne i$. Therefore, we will have to minimize ${\Vert X_i-D_i{A}_i^i-{\mathcal{E}}_i\Vert }_F^2$, where ${\mathcal{E}}_i$ is the residual. Meanwhile, $D_i$ should not be good at representing samples from other classes, that is, each $A_j^i$, where $j\ne i$, should have nearly zero coefficients so that ${\Vert D_i{A}_j^i\Vert }_F^2$ is as small as possible. Thus we denote the discriminative fidelity term for sub-dictionary $D_i$ as follows:

$R(D_i,A_i)={\Vert X_i-D_i{A}_i^i-{\mathcal{E}}_i\Vert }_F^2+\sum _{j=1,j\ne i}^c{\Vert D_i{A}_j^i\Vert }_F^2.$

In the task of image classification, the within-class samples are linearly correlated and lie in a low dimensional manifold. Therefore, we want to find the dictionary with the most concise atoms by minimizing the rank of $D_i$, which suggests replacing it by ${\Vert D_i\Vert }_{⁎}$ [31], where ${\Vert \cdot \Vert }_{⁎}$ denotes the nuclear norm of a matrix (i.e., the sum of its singular values).

In addition, a locality constraint is deployed on the coefficient matrix instead of the sparsity constraint. As suggested by LCC [32], locality is more essential than sparsity under certain assumptions, as locality must lead to sparsity but not necessary vice versa. Specifically, the locality constraint uses the following criterion:

$\underset{A}{\min }\sum _{i=1}^n{\Vert l_i\odot a_i\Vert }^2,\text{ s.t. }{\mathbf{1}}^T{a}_i=1,\forall i,$

where ⊙ denotes the element-wise multiplication, and $l_i\in {\mathbb{R}}^m$ is the locality adaptor which gives different freedom for each basis vector proportional to its similarity to the input sample $x_i$. Specifically,

$l_i=\text{exp}(\frac{\text{dist}(x_i,D)}{\delta }),$

where $\text{dist}(x_i,D)={[\text{dist}(x_i,d_1),\text{dist}(x_i,d_2),\dots ,\text{dist}(x_i,d_m)]}^T$, and $\text{dist}(x_i,d_j)$ is the Euclidean distance between sample $x_i$ and the jth dictionary atom $d_j$; δ controls the bandwidth of the distribution.

Generally speaking, LC-LRD is based on the following three observations: (i) locality is more essential than sparsity to ensure obtain the similar representations for similar samples; (ii) each sub-dictionary should have discerning ability by introducing the discriminative term; (iii) low-rank is introduced to each sub-dictionary to separate noise from samples and discover the latent structure.

7.1.3.3 Marginalized Denoising Auto-encoder (mDA)

Consider a vector input $x\in {\mathbb{R}}^d$, with d as the dimensionality of the visual descriptor. There are two important transformations, which can be considered as encoder and decoder processes involved in the auto-encoder, namely “input→hidden units” and “hidden units→output”, which are given by

$\begin{array}{c}\hfill h=\sigma (Wx+b_h),\hat{x}=\sigma (W^{T}h+b_o),\hfill \end{array}$

where $h\in {\mathbb{R}}^z$ is the hidden representation unit, and $\hat{x}\in {\mathbb{R}}^d$ is interpreted as a reconstruction of input x. The parameter set includes a weight matrix $W\in {\mathbb{R}}^{z\times d}$, and two offset vectors $b_h\in {\mathbb{R}}^z$ and $b_o\in {\mathbb{R}}^d$ for hidden units and output, respectively; σ is a nonlinear mapping such as the sigmoid function of the form $\sigma (x)={(1+e^{-x})}^{-1}$. In general, an auto-encoder is a single layer hidden neural network, with identical input and target, meaning the auto-encoder encourages the output to be as similar to the target as possible, namely,

$\underset{W,b_h,b_o}{\min }L(x)=\underset{W,b_h,b_o}{\min }\frac{1}{2n}\sum _{i=1}^n{\Vert x_i-{\hat{x}}_i\Vert }_2^2,$

where n is the number of images, $x_i$ is the target, and ${\hat{x}}_i$ is the reconstructed input. In this way, the neurons in the hidden layer can be seen as a good representation for the input, since they are able to reconstruct the data.

Since an auto-encoder deploys nonlinear functions, it takes more time to train the model, especially when the dimension of the data is very high. Recently, marginalized denoising auto-encoder (mDA) [20] was developed to address the data reconstruction in a linear fashion and achieved comparable performance with the original auto-encoder. The general idea of mDA is to learn a linear transformation matrix W to reconstruct the data with the transformation matrix by minimizing the squared reconstruction loss

$\frac{1}{2n}\sum _{i=1}^n{\Vert x_i-W{\tilde{x}}_i\Vert }^2,$

where ${\tilde{x}}_i$ is a corrupted version of $x_i$. The above objective solution is correlated to the randomly corrupted features of each input. To make the variance lower, a marginal denoising auto-encoder was proposed to minimize the overall squared loss from t different corrupted versions

$\frac{1}{2tn}\sum _{j=1}^t\sum _{i=1}^n{\Vert x_i-W{\tilde{x}}_{i,(j)}\Vert }^2,$

where ${\tilde{x}}_{i,(j)}$ denotes the jth corrupted version of the original input $x_i$. Define $X=[x_1,\dots ,x_n]$ and its t-times repeated version as $\bar{X}=[X,\dots ,X]$ with its t-times differently corrupted version $\tilde{X}=[{\tilde{X}}_{(1)},\dots ,{\tilde{X}}_{(t)}]$, where ${\tilde{X}}_{(i)}$ denotes the ith corrupted version of X. In this way, Eq. (7.12) can be reformulated as

$\frac{1}{2tn}{\Vert \bar{X}-W\tilde{X}\Vert }_{\mathrm{F}}^2,$

which has the well-known closed-form solution for ordinary least squares. When $t\to \infty$, it can be solved by the expectation, using the weak law of large numbers [20].

7.1.3.4 Proposed MDDL Model

Previous discussion on mDA gives a brief idea that, with a linear transformation matrix, mDA can be implemented in several lines of Matlab code and works very efficiently. The learned transformation matrix can well reconstruct the data and extract the noisy data.

Inspired by this, the proposed model aims at jointly learning a dictionary and a marginalized denoising transformation matrix in a unified framework. We formulate the objective function as

$\begin{array}{c}\hfill \underset{D_i,A_i,E_i,W}{\min }\mathcal{F}(D_i,A_i,E_i)+{\Vert \bar{X}-W\tilde{X}\Vert }_{\mathrm{F}}^2,\hfill \\ \hfill \text{ s.t.}W{X}_i=D{A}_i+E_i\hfill \end{array}$

where $\mathcal{F}(D_i,A_i,E_i)=R(D_i,A_i)+\alpha {\Vert D_i\Vert }_{⁎}+{\beta }_1{\Vert E_i\Vert }_1+\lambda {\sum }_{k=1}^{n_i}{\Vert l_{i,k}\odot a_{i,k}\Vert }^2$ is the locality-constrained dictionary learning part in Eq. (7.5) and $R(D_i,A_i)={\Vert W{X}_i-D_i{A}_i^i-{\mathcal{E}}_i\Vert }_F^2+{\sum }_{j=1,j\ne i}^c{\Vert D_i{A}_j^i\Vert }_F^2$ is the discriminative term in Eq. (7.6); α, ${\beta }_1$, and λ are trade-off parameters.

Discussion. The proposed marginalized denoising regularized dictionary learning (MDDL) aims to learn a more discriminative dictionary on transformed data. Since the marginalized denoising regularizer could generate a better transformation matrix to address corrupted data, the dictionary could be learned on denoised clean data. The framework unifies the marginal denoising auto-encoder and locality-constrained dictionary learning together. Generally, dictionary learning seeks a well-represented basis in order to achieve more discriminative coefficients for original data. Therefore, dictionary learning can handle noisy data to some extent, while the denoising auto-encoder has demonstrated its power in many applications. To this end, the joint learning scheme can benefit from both the marginal denoising auto-encoder and locality-constrained dictionary learning.

7.1.3.5 Optimization

The proposed objective function in Eq. (7.14) could be optimized by dividing into two sub-problems: first, updating one by one each coefficient $A_i(i=1,2,\dots ,c)$ and W, by fixing dictionary D and all other $A_j(j\ne i)$, and then putting together to get the coding coefficient matrix A; second, updating $D_i$ by fixing other variables. These two steps are iteratively repeated to get the discriminative low-rank sub-dictionaries D, the marginal denoising transformation W, and the locality-constrained coefficients A. One problem arises in the second sub-problem, though. Recall that in Eq. (7.6) the coefficients $A_i^i$ corresponding to $X_i$ over $D_i$ should be updated to minimize the term ${\Vert X_i-D_i{A}_i^i-{\mathcal{E}}_i\Vert }_F^2$. Therefore, when we update $D_i$ in the second sub-problem, the related variance $A_i^i$ is also updated.

Sub-problem I. Assume that the structured dictionary D is given, the coefficient matrices $A_i(i=1,2,\dots ,c)$ are updated one by one, then the original objective function in Eq. (7.14) reduces to the following locality-constrained coding problem for the coefficient of each class and W:

$\begin{array}{c}\hfill \underset{A_i,E_i,W}{\min }\lambda \sum _{k=1}^{n_i}{\Vert l_{i,k}\odot a_{i,k}\Vert }^2+{\beta }_1{\Vert E_i\Vert }_1+{\Vert \bar{X}-W\tilde{X}\Vert }_{\mathrm{F}}^2\hfill \\ \hfill \text{ s.t. }W{X}_i=D{A}_i+E_i,\hfill \end{array}$

which can be solved by the following Augmented Lagrange Multiplier method [33]. We transform Eq. (7.15) into its Lagrange function as follows:

$\begin{array}{c}\underset{A_i,E_i,W,T_1}{\min }\sum _{i=1}^c(\lambda \sum _{k=1}^{n_i}{\Vert l_{i,k}\odot a_{i,k}\Vert }^2+{\beta }_1{\Vert E_i\Vert }_1+\hfill \\ \langle T_1,W{X}_i-D{A}_i-E_i\rangle +\frac{\mu }{2}{\Vert W{X}_i-D{A}_i-E_i\Vert }_F^2)\hfill \\ +{\Vert \bar{X}-W\tilde{X}\Vert }_{\mathrm{F}}^2,\hfill \end{array}$

where $T_1$ is the Lagrange multiplier, and μ is a positive penalty parameter. Different from traditional locality-constrained linear coding (LLC) [27], MDDL adds an error term which could handle large noise in samples. In the following, we perform iterative optimization on $A_i$, $E_i$, and W.

Updating $A_i$:

$\begin{array}{c}{A}_i=\arg \underset{A_i}{\min }\frac{\mu }{2}{\Vert Z_i-D{A}_i\Vert }_F^2+\lambda \sum _{k=1}^{n_i}{\Vert l_{i,k}\odot a_{i,k}\Vert }^2,\hfill \end{array}$

$\Rightarrow A_i=\text{LLC}(Z_i,D,\lambda ,\delta ),$

where $Z_i=W{X}_i-E_i+\frac{T_1}{\mu }$, and $l_{i,k}=\text{exp}(\text{dist}(z_{i,k},D)/\delta )$. Function $\mathrm{LLC}(\cdot )$ is a locality-constrained linear coding function² [27].

Updating $E_i$:

$E_i=\arg \underset{E_i}{\min }\frac{{\beta }_1}{\mu }{\Vert E_i\Vert }_1+\frac{1}{2}{\Vert E_i-(W{X}_i-D{A}_i+\frac{T_1}{\mu })\Vert }_F^2,$

which can be solved by the shrinkage operator [34].

Updating W:

$\begin{array}{c}W=\arg \underset{W}{\min }\sum _{i=1}^c\left(\frac{\mu }{2}{\Vert W{X}_i-D{A}_i-E_i+\frac{T_1}{\mu }\Vert }_F^2\right)\hfill \\ \phantom{W=}+{\Vert \bar{X}-W\tilde{X}\Vert }_{\mathrm{F}}^2\hfill \\ \phantom{W}=\arg \underset{W}{\min }\frac{\mu }{2}{\Vert WX-D_A\Vert }_{\mathrm{F}}^2+{\Vert \bar{X}-W\tilde{X}\Vert }_{\mathrm{F}}^2,\hfill \end{array}$

where $X=[X_1,\dots ,X_c]$ and $D_A=[D{A}_1+E_1-\frac{T_{1,1}}{\mu },\dots ,D{A}_c+E_c-\frac{T_{1,c}}{\mu }]$. Equation (7.19) has a well-known closed-form solution

$\begin{array}{c}\hfill W=(\mu D_A{X}^{\mathrm{T}}+2\bar{X}{\tilde{X}}^{\mathrm{T}}){(\mu X{X}^{\mathrm{T}}+2\tilde{X}{\tilde{X}}^{\mathrm{T}})}^{-1}\hfill \end{array}$

where $\bar{X}$ is the t-times repeated version of X and $\tilde{X}$ consists of its t-times corrupted version. We define $P=\mu D_A{X}^{\mathrm{T}}+2\bar{X}{\tilde{X}}^{\mathrm{T}}$ and $Q=\mu X{X}^{\mathrm{T}}+2\tilde{X}{\tilde{X}}^{\mathrm{T}}$. And we would like the repetition number t to be ∞. Therefore, the denoising transformation W could be effectively learned from infinitely many copies of noisy data. Practically, we cannot generate $\tilde{X}$ with infinitely many corrupted versions; however, matrices P and Q converge to their expectations when t becomes very large. In this way, we can derive the expected values of P and Q, and calculate the corresponding mapping W as:

$\begin{array}{c}W=\mathbb{E}[P]\mathbb{E}{[Q]}^{-1}\hfill \\ \phantom{W}=\mathbb{E}[\mu D_A{X}^{\mathrm{T}}+2\bar{X}{\tilde{X}}^{\mathrm{T}}]\mathbb{E}{[\mu X{X}^{\mathrm{T}}+2\tilde{X}{\tilde{X}}^{\mathrm{T}}]}^{-1}\hfill \\ \phantom{W}=(\mu D_A{X}^{\mathrm{T}}+2\mathbb{E}[\bar{X}{\tilde{X}}^{\mathrm{T}}]){(\mu X{X}^{\mathrm{T}}+2\mathbb{E}[\tilde{X}{\tilde{X}}^{\mathrm{T}}])}^{-1}\hfill \end{array}$

where $D_A$ and μ are treated as constant values when optimizing W. The expectations $\mathbb{E}[\bar{X}{\tilde{X}}^{\mathrm{T}}]$ and $\mathbb{E}[\tilde{X}{\tilde{X}}^{\mathrm{T}}]$ are easy to be computed through mDA [20].

Sub-problem II. For the procedure of sub-dictionary updating, MDDL uses the same method as in [25]. Considering the second sub-problem, when $A_i$ is fixed, sub-dictionaries $D_i(i=1,2,...,c)$ are updated one by one. The objective function in Eq. (7.14) is converted into the following problem:

$\begin{array}{c}\hfill \underset{D_i,{\mathcal{E}}_i,A_i^i}{\min }\sum _{j=1,j\ne i}^c{\Vert D_i{A}_j^i\Vert }_F^2+\alpha {\Vert D_i\Vert }_{⁎}+{\beta }_2{\Vert {\mathcal{E}}_i\Vert }_1\hfill \\ \hfill +\lambda \sum _{k=1}^{n_i}{\Vert l_{i,k}^i\odot a_{i,k}^i\Vert }^2,\text{ s.t. }W{X}_i=D_i{A}_i^i+{\mathcal{E}}_i\hfill \end{array}$

where $a_{i,k}^i$ is the kth column in $A_i^i$, which means the coefficient for the kth sample in class i over $D_i$. Problem Eq. (7.22) can be solved using the Augmented Lagrange Multiplier method [33] by introducing a relaxing variable J:

$\begin{array}{c}\hfill \underset{D_i,{\mathcal{E}}_i,A_i^i}{\min }\lambda \sum _{k=1}^{n_i}{\Vert l_{i,k}^i\odot a_{i,k}^i\Vert }^2+\sum _{j=1,j\ne i}^c{\Vert D_i{A}_j^i\Vert }_F^2+\alpha {\Vert J\Vert }_{⁎}\hfill \\ \hfill +{\beta }_2{\Vert {\mathcal{E}}_i\Vert }_1+\langle T_2,W{X}_i-D_i{A}_i^i-{\mathcal{E}}_i\rangle +\langle T_3,D_i-J\rangle \hfill \\ \hfill +\frac{\mu }{2}({\Vert W{X}_i-D_i{A}_i^i-{\mathcal{E}}_i\Vert }_F^2+{\Vert D_i-J\Vert }_F^2),\hfill \end{array}$

where $T_2$ and $T_3$ are Lagrange multipliers, and μ is a positive penalty parameter. In the following, we describe the iterative optimization of $D_i$ and $A_i^i$.

Updating $A_i^i$:

Similar as for Eq. (7.17), we have the solution for $A_i^i$ as follows:

$A_i^i=\text{LLC}((W{X}_i-{\mathcal{E}}_i+\frac{T_2}{\mu }),D_i,\lambda ,\delta ),$

where function $\mathrm{LLC}(\cdot )$ is a locality-constrained linear coding function [27].

Updating J and $D_i$:

Here we convert Eq. (7.23) to a problem for J and $D_i$ as:

$\begin{array}{c}\hfill \underset{J,D_i}{\min }{\sum }_{j=1,j\ne i}^c{\Vert D_i{A}_j^i\Vert }_F^2+\alpha {\Vert J\Vert }_{⁎}\hfill \\ \hfill +\langle T_2,W{X}_i-D_i{A}_i^i-{\mathcal{E}}_i\rangle +\langle T_3,D_i-J\rangle \hfill \\ \hfill +\frac{\mu }{2}({\Vert D_i-J\Vert }_F^2+{\Vert W{X}_i-D_i{A}_i^i-{\mathcal{E}}_i\Vert }_F^2),\hfill \end{array}$

where $J=\arg \underset{J}{\min }\alpha {\Vert J\Vert }_{⁎}+\langle T_3,D_i-J\rangle +\frac{\mu }{2}({\Vert D_i-J\Vert }_F^2)$, and the solution for $D_i$ is:

$\begin{array}{c}\hfill D_i=(J+W{X}_i{A_i^i}^T-{\mathcal{E}}_i{A_i^i}^T+(T_2{A_i^i}^T-T_3)/\mu )\hfill \\ \hfill {(I+A_i^i{A_i^i}^T+V)}^{-1},\text{where}V=\frac{2\lambda }{\mu }\sum _{j=1,j\ne i}^c{A}_j^i{A_j^i}^T;\hfill \end{array}$

Updating ${\mathcal{E}}_i$:

$\begin{array}{c}\hfill {\mathcal{E}}_i=\arg \underset{{\mathcal{E}}_i}{\min }{\beta }_2{\Vert E_i\Vert }_1+\langle T_2,W{X}_i-D_i{A}_i^i-{\mathcal{E}}_i\rangle \hfill \\ \hfill +\frac{\mu }{2}{\Vert W{X}_i-D_i{A}_i^i-{\mathcal{E}}_i\Vert }_F^2,\hfill \end{array}$

which can be solved by the shrinkage operator [34]. The details of the optimization problem solution for the proposed model can be referred to as Algorithm 7.1.

7.1.3.6 Classification Based on MDDL

MDDL uses a linear classifier for classification. After the dictionary is learned, the locality-constrained coefficients A of training data X and $A_{\text{test}}$ of test data $X_{\text{test}}$ are calculated. The representation $a_i$ for test sample i is the ith column vector in $A_{\text{test}}$. The multivariate ridge regression model [35] was used to obtain a linear classifier $\hat{P}$:

$\begin{array}{c}\hfill \hat{P}=\arg \underset{P}{\min }{\Vert L-PA\Vert }_{\mathrm{F}}^2+\gamma {\Vert P\Vert }_{\mathrm{F}}^2\hfill \end{array}$

where L is the class label matrix. This yields $\hat{P}=L{A}^T{(A{A}^T+\gamma I)}^{-1}$. When testing points $A_{\text{test}}$ come in, we first compute $\hat{P}{A}_{\text{test}}$. Then the label for sample i is assigned by the position corresponding to the largest value in the label vector, that is, $label=\arg \underset{label}{\max }(\hat{P}{a}_i)$.

7.1.4.1 Experimental Settings

To verify the effectiveness and generality of the introduced MDDL, we show experiments conducted on various visual classification applications in this section. The method is tested on five datasets, including three face datasets: ORL [36], Extend YaleB [37], and CMU PIE [38], one object categorization dataset COIL-100 [39], and digits recognition dataset MNIST [40].

We show the experiments in comparison with LDA [41], linear regression classification (LRC) [42] and several latest dictionary learning based classification methods, i.e., FDDL [11], DLRD [25], ${\text{D}}^2{\text{L}}^2{\text{R}}^2$ [43], DPL [44], and LC-LRD [28]. Moreover, for verifying the advantage of joint learning, a simple combination framework was proposed as a baseline, named as AE+DL, which first uses a traditional SAE to learn a new representation, then feeds in LC-LRD framework [28].

Parameter selection. The number of atoms in a sub-dictionary, which is denoted as $m_i$, is one of the most important parameters in most of dictionary learning algorithms. We conduct the experiment on Extended YaleB with different number of dictionary atoms $m_i$ and analyze its effect on the performance of MDDL model and other competitors. Fig. 7.2 shows that all comparisons obtain better performance with larger dictionary size. In the experiments, the number of the dictionary columns of each class is fixed as the training size for ORL, Extend YaleB, AR and COIL-100 datasets, while it is fixed as 30 for CMU PIE and MNIST datasets. All the dictionaries are initialized with PCA on input data.

There are five parameters in Algorithm 7.1: α, λ, δ along with ${\beta }_1$, ${\beta }_2$ as two error term parameters, respectively, for updating dictionary and coefficients. These five are associated with the dictionary learning part in MDDL and are chosen by 5-fold cross validation. Experiments show that ${\beta }_1$ and ${\beta }_2$ play more important roles than the other parameters; therefore, the other parameters are set as $\alpha =1$, $\lambda =1$ and $\delta =1$. For Extended YaleB, ${\beta }_1=15$, ${\beta }_2=100$; for ORL, ${\beta }_1=5$, ${\beta }_2=50$; for CMU PIE, ${\beta }_1=5$, ${\beta }_2=1.5$; for COIL-100, ${\beta }_1=3$, ${\beta }_2=150$; for MNIST, ${\beta }_1=2.5$, ${\beta }_2=2.5$.

7.1.4.2 Face Recognition

ORL Face Database. The ORL dataset contains 400 images of 40 individuals, so that there are 10 images for each subject with varying pose and illumination. The subjects of the images are in frontal and upright posture while the background is dark and uniform. The images are resized to $32\times 32$, converted to gray scale, normalized and the pixels are concatenated to form a vector. Each image is manually corrupted by a randomly located and unrelated block image. Fig. 7.3B shows four examples of images with increasing block corruptions. For each subject, 5 samples are selected for training and the rest for testing, and the experiment is repeated on 10 random splits for evaluation. Furthermore, SIFT and Gabor filter features are extracted to evaluate MDDL generality.

We illustrate the recognition rates under different percentages of occlusion in Table 7.1. From the table, we can observe two phenomena: first, locality-constrained dictionary learning based methods achieve the best results for all the settings; second, the MDDL model performs best when the data is clean; however, along with the percentage of occlusion increase, MDDL drops behind with LC-LRD. This makes sense because in this experiment occlusion noise is added on to the images, while the denoising auto-encoder module in MDDL is introduced to tackle Gaussian noise. In conclusion, first, MDDL can achieve top results in a no occlusion situation because of the locality term; second, in a larger occlusion situation, the low-rank term outweighs DAEs.

Table 7.1

Average recognition rate (%) of different algorithms on ORL dataset for various occlusion percentage (%). Red denotes the best results, while blue means the second best results. (For interpretation of the colors in the tables, the reader is referred to the web version of this chapter)

Occlusion	LDA [41]	LRC [42]	FDDL [11]	DLRD [25]	${\text{D}}^2{\text{L}}^2{\text{R}}^2$ [43]
0	92.5±1.8	91.8±1.6	96.0±1.2	93.5±1.5	93.9±1.8
0 (SIFT)	95.8±1.3	92.9±2.1	95.2±1.3	93.7±1.3	93.9±1.5
0 (Gabor)	89.0±3.3	93.4±1.7	96.0±1.3	96.3±1.3	96.6±1.3
10	71.7±3.2	82.2±2.2	86.6±1.9	91.3±1.9	91.0±1.9
20	54.3±2.0	71.3±2.8	75.3±3.4	82.8±3.0	82.8±3.3
30	40.5±3.7	63.7±3.1	63.8±2.7	78.9±3.1	78.8±3.3
40	25.7±2.5	48.0±3.0	48.1±2.4	67.3±3.2	67.4±3.4
50	20.7±3.0	40.9±3.7	36.7±1.2	58.6±3.1

Occlusion	DPL [44]	LC-LRD [28]	AE+DL [1]	MDDL [1]
0	94.1±1.8		96.2±1.2
0 (SIFT)	95.3±1.4	93.5±2.6
0 (Gabor)	97.0±1.4	94.6±1.8
10	84.5±2.7		91.5±1.2
20	71.2±1.7		83.6±1.8
30	59.8±3.9			78.0±2.4
40	43.0±2.9		67.3±2.6
50	32.2±3.5		58.7±3.2	58.5±3.0

The effects from two parameters of the error term, ${\beta }_1$ and ${\beta }_2$, are demonstrated in Fig. 7.4. From the six sub-figures under increasing percentage of corrupted pixels, parameter ${\beta }_1$ in the coefficient updating procedure makes a larger impact. As more occlusion is applied, the best result appears when the parameter ${\beta }_1$ is smaller, which means the error term plays a more important role when noise exists.

The results show that MDDL introduces significant improvement on some datasets, and for some other datasets, its significance increases along with the noise level in the input data.

Extended YaleB Dataset. The Extended Yale Face Database B contains 2414 frontal-face images from 38 human subjects captured under various laboratory-controlled illumination conditions. The size of image is cropped to $32\times 32$. Two experiments are deployed on this dataset. First, random subsets with $p(=5,10,\dots ,40)$ images per individual taken with labels are chosen to form the training set, and the rest of the dataset is considered to be the testing set. For each given p, there are 10 random splits. Second, a certain percentage of randomly selected pixels from the images are replaced with pixel value of 255 (shown in Fig. 7.3C). Then we randomly take 30 images as training samples, with the rest reserved for testing, and the experiment is repeated 10 times. The experimental results are given in Tables 7.2 and 7.3, respectively.

Table 7.2

Average recognition rate (%) of different algorithms on Extended YaleB dataset with different number of training samples per class. Red denotes the best results, while blue means the second best results

Training	5	10	20	30	40
LDA [41]	74.1±1.5	86.7±0.9	90.6±1.1	86.8±0.9	95.3±0.8
LRC [42]	60.2±2.0	83.00±0.8	91.8±1.0	94.6±0.6	96.1±0.6
FDDL [11]	77.8±1.3	91.2±0.9	96.2±0.7	97.9±0.3	98.8±0.5
DLRD [25]	76.2±1.2	89.9±0.9	96.0±0.8	97.9±0.5	98.8±0.4
D2L2R2[43]	76.0±1.2	89.6±0.9	96.0±0.9	97.9±0.4	98.1±0.4
DPL [44]	75.2±1.9	89.3±0.6	95.7±0.9	97.8±0.4	98.7±0.4
LC-LRD [28]	78.6±1.2	92.1±0.9
AE+DL [1]			96.6±0.9	98.6±0.5	99.2±0.4
MDDL [1]

Table 7.3

Average recognition rate (%) of different algorithms on Extended YaleB dataset with various corruption percentage (%). Red denotes the best results, while blue means the second best results

Corruption	0	5	10	15	20
LDA [41]	86.8±0.9	29.0±0.8	18.5±1.2	13.6±0.5	11.3±0.5
LRC [42]	94.6±0.6	80.5±1.1	67.6±1.3	56.8±1.2	47.2±1.6
FDDL [11]	97.9±0.4	63.6±0.9	44.7±1.2	32.7±1.0	25.3±0.4
DLRD [25]	97.9±0.5	91.8±1.1	85.8±1.5	80.9±1.4	73.6±1.6
D2L2R2[43]	97.8±0.4	91.9±1.1	85.7±1.5	80.5±1.6	73.6±1.5
DPL [44]	97.8±0.4	78.3±1.2	64.6±1.1	53.8±0.9	44.9±1.4
LC-LRD [28]			87.0±0.9		74.1±1.0
AE+DL [1]	98.6±0.5	93.2±0.7		81.6±0.9
MDDL [1]

We can observe from Table 7.2 that in different training size settings three locality-constrained based methods (LC-LRD, AE+DL, MDDL) archive the best accuracy, and the proposed MDDL performs the best. MDDL's robustness to noise is demonstrated in Table 7.3. As the percentage of corruption increases, MDDL still produces the best recognition results. The performance of LDA, as well as LRC, FDDL and DPL, drops rapidly with larger corruption, while LC-LRD, MDDL, ${\text{D}}^2{\text{L}}^2{\text{R}}^2$ and DLRD can still get much better recognition accuracy. This demonstrates the effectiveness of low-rank regularization and the error term when noise exists. LC-LRD and simple AE+DL equally match in different situations, while MDDL constantly performs the best.

CMU PIE Dataset. The CMU PIE dataset contains a total of 41,368 face images from 68 people, each with 13 different poses, 4 different expressions, and 43 different illumination conditions. Two experiments are deployed on two subsets of CMU PIE. First of all, five near frontal poses (C05, C07, C09, C27, C29) are selected as a first subset of PIE, and all the images under different illuminations and expressions (11,554 samples in total) are used. Thus, there are about 170 images for each person, and each image is normalized to have size of $32\times 32$ pixels; 60 images per person are selected for training. Secondly, a relatively large-scale dataset is built by choosing more poses, which contains 24,245 samples in total. Overall, there are around 360 images for each person, and each image is normalized to have size of $32\times 32$ pixels. The training set is constructed by randomly selecting 200 images per person, while the rest is used for evaluation. Table 7.4 shows that MDDL achieves good results and outperforms the compared methods.

7.1.4.3 Object Recognition

COIL-100 Dataset. In this section, MDDL is evaluated on object categorization by using the COIL-100 dataset. The training set is constructed by randomly selecting 10 images per object, and the testing set contains the rest of the images. This random selection is repeated 10 times, and the average results of all the compared methods are reported. To evaluate the scalability of different methods, the experiment separately utilizes images of 20, 40, 60, 80 and 100 objects from the dataset. Table 7.5 shows the average recognition rates with standard deviations of all compared methods. The results show that MDDL could not only work on face recognition but also on object categorization.

Table 7.5

Average recognition rate (%) with standard deviations of different algorithms on COIL-100 dataset with different number of classes. Red denotes the best results, while blue means the second best results

Class No.	20	40	60	80	100
LDA [41]	81.9±1.2	76.7±0.3	66.2±1.0	59.2±0.7	52.5±0.5
LRC [42]	90.7±0.7	89.0±0.5	86.6±0.4	85.1±0.3	83.2±0.6
FDDL [11]	85.7±0.8	82.1±0.4	77.2±0.7	74.8±0.6	73.6±0.6
DLRD [25]	88.6±1.0	86.4±0.5	83.5±0.1	81.5±0.5	79.9±0.6
D2L2R2[43]	91.0±0.4	88.3±0.4	86.4±0.5	84.7±0.5	83.1±0.4
DPL [44]	87.6±1.3	85.1±0.2	81.2±0.2	78.8±0.9	76.3±0.9
LC-LRD [28]			87.1±0.7
AE+DL [1]	91.3±0.5	89.1±0.7		85.1±0.5	84.1±0.4
MDDL [1]

7.1.4.4 Digits Recognition

MNIST Dataset. This section tests MDDL on the subset of MNIST handwritten digit dataset downloaded from CAD website, which includes first 2000 training images and first 2000 test images, with the size of each digit image being $16\times 16$. This experimental setting follows [43], and the experiments get consistent results. The recognition rates and training/testing time by different algorithms on MNIST dataset are summarized in Table 7.6. MDDL achieves the highest accuracy relative to its competitors. Compared within LC-LRD, MDDL costs only slightly more computational time thanks to the easy updating of marginalized auto-encoder.

Another experiment setting is conducted on this dataset to evaluate the effect from denoising auto-encoders. All the training and testing images in MNIST are corrupted with additive white Gaussian noise having signal-to-noise ratio (snr) from 50 to 1 dB (shown in Fig. 7.3A). Fig. 7.5 illustrates the recognition rate curves on 8 noised version of datasets. On the X-axis, we show the noise ratio used in input reconstruction process in DAEs, where close to 1 means more noise added, and 0 means no DAEs evolved. From the figure, we can observe that, with the increasing noise added in the datasets (50 to 1 dB), the highest recognition rate appears when the noise parameter gets larger (from nearly 0.004 for 50 dB to nearly 0.1 for 1 dB). In other words, denoising auto-encoders play a more important role when the dataset contains more noise.

To verify if the improvement from MDDL is statistically significant, a significance test (t-test) is further conducted for the results shown in Fig. 7.6. A significance level of 0.05 was used, that is, when the p-value is less than 0.05, the performance difference of two methods is statistically significant. The p-values of MDDL and other competitors are listed in Fig. 7.6. Since we do $-\log (p)$ processing, the comparison shows that MDDL outperforms the others significantly if the values are greater than $-\log (0.05)$. The results show that MDDL introduces significant improvement on COIL-100 dataset, and for Extended YaleB dataset, the significance increases along with the noise level in the input data.

7.2.1.1 Problem Definition and Background

While ${\ell }_0$ and ${\ell }_1$ regularizations have been well-known and successfully applied in sparse signal approximations, utilizing the ${\ell }_{\infty }$ norm to regularize signal representations has been less explored. In this section, we are particularly interested in the following ${\ell }_{\infty }$-constrained least squares problem:

$\begin{array}{c}{\min }_x||\mathit{D}x-y|{|}_2^2\text{s.t.}||x|{|}_{\infty }\le \lambda ,\hfill \end{array}$

where $y\in R^{n\times 1}$ denotes the input signal, $\mathit{D}\in R^{n\times N}$ the (overcomplete) the basis (often called frame or dictionary) with $N<n$, and $x\in R^{N\times 1}$ the learned representation. Further, the maximum absolute magnitude of x is bounded by a positive constant λ, so that each entry of x has the smallest dynamic range [45]. As a result, model (7.29) tends to spread the information of y approximately evenly among the coefficients of x. Thus, x is called “democratic” [46] or “anti-sparse” [47], as all of its entries are of approximately the same importance.

In practice, x usually has most entries reaching the same absolute maximum magnitude [46], therefore resembling an antipodal signal in an N-dimensional Hamming space. Furthermore, the solution x to (7.29) withstands errors in a very powerful way: the representation error gets bounded by the average, rather than the sum, of the errors in the coefficients. These errors may be of arbitrary nature, including distortion (e.g., quantization) and losses (e.g., transmission failure). This property was quantitatively established in Section II.C of [45]:

In the case of $N\ll n$, the above will yield great robustness for the solution to (7.29) with respect to noise, in particular, quantization errors. Also note that its error bound will not grow with the input dimensionality n, a highly desirable stability property for high-dimensional data. Therefore, (7.29) appears to be favorable for the applications such as vector quantization, hashing and approximate nearest neighbor search.

In this section, we investigate (7.29) in the context of deep learning. Based on the Alternating Direction Methods of Multipliers (ADMM) algorithm, we formulate (7.29) as a feed-forward neural network [48], called Deep ${\mathit{\ell }}_{\infty }$ Encoder, by introducing a novel Bounded Linear Unit (BLU) neuron and modeling the Lagrange multipliers as network biases. The major technical merit to be presented is how a specific optimization model (7.29) could be translated to designing a task-specific deep model, which displays the desired quantization-robust property. We then study its application in hashing, by developing a Deep Siamese ${\mathit{\ell }}_{\infty }$ Network that couples the proposed encoders under a supervised pairwise loss, which could be optimized from end to end. Impressive performances are observed in our experiments.

7.2.1.2 Related Work

Similar to the case of ${\ell }_0/{\ell }_1$ sparse approximation problems, solving (7.29) and its variants (e.g., [46]) relies on iterative solutions. The authors of [49] proposed an active set strategy similar to that of [50]. In [51], the authors investigated a primal–dual path-following interior-point method. Albeit effective, the iterative approximation algorithms suffer from their inherently sequential structures, as well as the data-dependent complexity and latency, which often constitute a major bottleneck in the computational efficiency. In addition, the joint optimization of the (unsupervised) feature learning and the supervised steps has to rely on solving complex bi-level optimization problems [52]. Further, to effectively represent datasets of growing sizes, larger dictionaries D are usually needed. Since the inference complexity of those iterative algorithms increases more than linearly with respect to the dictionary size [53], their scalability turns out to be limited. Last but not least, while the hyperparameter λ sometimes has physical interpretations, e.g., for signal quantization and compression, it remains unclear how to set or adjust it for many application cases.

Deep learning has recently attracted great attention [54]. The advantages of deep learning lie in its composition using multiple nonlinear transformations to yield more abstract and descriptive embedding representations. The feed-forward networks could be naturally tuned jointly with task-driven loss functions [55]. With the aid of gradient descent, it also scales linearly in time and space with the number of training samples.

There has been a blooming interest in bridging “shallow” optimization and deep learning models. In [48], a feed-forward neural network, named LISTA, was proposed to efficiently approximate the sparse codes, whose hyperparameters were learned from general regression. In [56], the authors leveraged a similar idea on fast trainable regressors and constructed feed-forward network approximations of the learned sparse models. It was later extended in [57] to develop a principled process of learned deterministic fixed-complexity pursuits, for sparse and low rank models. Lately, [55] proposed Deep ${\ell }_0$ Encoders, to model ${\ell }_0$ sparse approximation as feed-forward neural networks. The authors extended the strategy to the graph-regularized ${\ell }_1$ approximation in [58], and the dual sparsity model in [59]. Despite the above progress, to the best of our knowledge, few efforts have been made beyond sparse approximation (e.g., ${\ell }_0/{\ell }_1$) models.