3.2.1 ${\ell }_0$- and ${\ell }_1$-Based Sparse Approximations

Finding the sparsest, or minimum ${\ell }_0$-norm, representation of a signal given a dictionary of basis atoms is an important problem in many application domains. Consider a data sample $\mathbf{x}\in R^{m\times 1}$ that is encoded into its sparse code $\mathbf{a}\in R^{p\times 1}$ using a learned dictionary $\mathbf{D}=[{\mathbf{d}}_1,{\mathbf{d}}_2,\dots ,{\mathbf{d}}_p]$, where ${\mathbf{d}}_i\in R^{m\times 1},i=1,2,\dots ,p$ are the learned atoms. The sparse codes are obtained by solving the ${\mathit{\ell }}_0$-regularized problem (λ is a constant)

$\begin{array}{c}\mathbf{a}=\arg {\min }_{\mathbf{a}}\frac{1}{2}||\mathbf{x}-\mathbf{Da}|{|}_F^2+\lambda ||\mathbf{a}|{|}_0.\hfill \end{array}$

Alternatively, one could explicitly impose constraints on the number of nonzero coefficients of the solution, by solving the M-sparse problem

$\begin{array}{c}\mathbf{a}=\arg {\min }_{\mathbf{a}}||\mathbf{x}-\mathbf{Da}|{|}_F^{2}s.t.||\mathbf{a}|{|}_0\le M.\hfill \end{array}$

Unfortunately, these optimization problems are often intractable because there is a combinatorial increase in the number of local minima as the number of the candidate basis vectors increases. One potential remedy is to employ a convex surrogate measure, such as the ${\ell }_1$-norm, in place of the ${\ell }_0$-norm that leads to a more tractable optimization problem. For example, (3.1) could be relaxed as

$\begin{array}{c}\mathbf{a}=\arg {\min }_{\mathbf{a}}\frac{1}{2}||\mathbf{x}-\mathbf{Da}|{|}_F^2+\lambda ||\mathbf{a}|{|}_1.\hfill \end{array}$

It creates an unimodal optimization problem that can be solved via linear programming techniques. The downside is that we have now introduced a mismatch between the ultimate goal and the objective function [14]. Under certain conditions, the minimum ${\ell }_1$-norm solution equals to that of the minimum ${\ell }_0$-norm [6]. But in practice, the ${\ell }_1$-approximation is often used way beyond these conditions, and is thus quite heuristic. As a result, we often get a solution which is not exactly minimizing the original ${\ell }_0$-norm.

That said, ${\ell }_1$-approximation is found to work practically well for many sparse coding problems. Yet in certain applications, we intend to control the exact number of nonzero elements, such as basis selection [14], where ${\ell }_0$-approximation is indispensable. Beyond that, ${\ell }_0$-approximation is desirable for performance concerns in many ways. In compressive sensing literature, empirical evidence [15] suggested that using an iterative reweighted ${\ell }_1$-scheme to approximate the ${\ell }_0$-solution often improved the quality of signal recovery. In image enhancement, it was shown in [16] that ${\ell }_0$ data fidelity was more suitable for reconstructing images corrupted with impulse noise. For the purpose of image smoothing, the authors of [17] utilized ${\ell }_0$ gradient minimization to globally control how many nonzero gradients are used to approximate prominent structures in a structure-sparsity-management manner. Recent work [18] revealed that ${\ell }_0$ sparse subspace clustering can completely characterize the set of minimal union-of-subspace structure, without additional separation conditions required by its ${\ell }_1$ counterpart.

3.2.2 Network Implementation of ${\ell }_1$-Approximation

In [8], a feed-forward neural network, as illustrated in Fig. 3.1, was proposed to efficiently approximate the ${\ell }_1$-based sparse code a of the input signal x; the sparse code a is obtained by solving (3.3) for a given dictionary D in advance. The network has a finite number of stages, each of which updates the intermediate sparse code ${\mathbf{z}}^k$ ($k=1,2$) according to

$\begin{array}{c}{\mathbf{z}}^{k+1}=s_{\theta }(\mathbf{Wx}+{\mathbf{Sz}}^k),\hfill \end{array}$

where $s_{\theta }$ is an element-wise shrinkage function (u is a vector and ${\mathbf{u}}_i$ is its ith element, $i=1,2,\dots ,p$),

$\begin{array}{c}{[s_{\theta }(\mathbf{u})]}_i=\text{sign}({\mathbf{u}}_i){(|{\mathbf{u}}_i|-{\theta }_i)}_{+}.\hfill \end{array}$

The parameterized encoder, named learned ISTA (LISTA), is a natural network implementation of the iterative shrinkage and thresholding algorithm (ISTA). LISTA learned all its parameters W, S and θ from training data using a back-propagation algorithm [19]. In this way, a good approximation of the underlying sparse code can be obtained after a fixed small number of stages.

In [10], the authors leveraged a similar idea on fast trainable regressors and constructed feed-forward network approximations of the learned sparse models. Such a process-centric view was later extended in [11] to develop a principled process of learned deterministic fixed-complexity pursuits, in lieu of iterative proximal gradient descent algorithms, for structured sparse and robust low rank models. Very recently, [9] further summarized the methodology of the problem-level and model-based “deep unfolding”, and developed new architectures as inference algorithms for both Markov random fields and nonnegative matrix factorization. Our work shares the same prior ideas, yet studies the unexplored ${\ell }_0$-problems and obtains further insights.

3.3.1 Deep ${\ell }_0$-Regularized Encoder

To solve the optimization problem in (3.1), an iterative hard-thresholding (IHT) algorithm was derived in [13], namely

$\begin{array}{c}{\mathbf{a}}^{k+1}=h_{{\lambda }^{0.5}}({\mathbf{a}}^k+{{\mathbf{D}}^{\mathbf{T}}(\mathbf{x}-\mathbf{Da}}^k)),\hfill \end{array}$

where ${\mathbf{a}}^k$ denotes the intermediate result of the kth iteration, and $h_{\theta }$ is an element-wise hard thresholding operator given by

${[h_{{\lambda }^{0.5}}(\mathbf{u})]}_i=\{\begin{array}{cc}0\hfill & \text{if}|{\mathbf{u}}_i|<{\lambda }^{0.5},\hfill \\ {\mathbf{u}}_i\hfill & \text{if}|{\mathbf{u}}_i|\ge {\lambda }^{0.5}.\hfill \end{array}$

Equation (3.6) could be alternatively rewritten as

$\begin{array}{c}{\mathbf{a}}^{k+1}=h_{\theta }(\mathbf{Wx}+{\mathbf{Sa}}^k),\hfill \\ \mathbf{W}={\mathbf{D}}^T,\mathbf{S}=\mathbf{I}-{\mathbf{D}}^T\mathbf{D},\theta ={\lambda }^{0.5},\hfill \end{array}$

and expressed as the block diagram in Fig. 3.2, which outlines a recurrent network form of solving (3.6).

By time-unfolding and truncating Fig. 3.2 to a fixed number of K iterations ($K=2$ in this chapter by default),¹ we obtain a feed-forward network structure in Fig. 3.3, where W, S and θ are shared among both stages, named deep ${\mathit{\ell }}_0$-regularized encoder. Furthermore, W, S and θ are all to be learnt, instead of being directly constructed from any precomputed D. Although the equations in (3.8) do not directly apply any more to solving the deep ${\ell }_0$-regularized encoder, they can usually serve as a high-quality initialization of the latter.

Note that the activation thresholds θ are less straightforward to update. We rewrite (3.5) as ${[h_{\theta }(\mathbf{u})]}_i={\theta }_i{h}_1({\mathbf{u}}_i/{\theta }_i)$. It indicates that the original neuron with trainable thresholds can be decomposed into two linear scaling layers, plus a unit-hard-threshold neuron, which is later called Hard thrEsholding Linear Unit (HELU) by us. The weights of the two scaling layers are diagonal matrices defined by θ and its element-wise reciprocal, respectively.

Discussion about HELU. While being inspired by LISTA, the differentiating point of deep ${\ell }_0$-regularized encoder lies in the HELU neuron. Compared to classical neuron functions such as logistic, sigmoid, and ReLU [20], as well as the soft shrinkage and thresholding operation (3.5) in LISTA, HELU does not penalize large values, yet enforces strong (in theory infinite) penalty for small values. As such, HELU tends to produce highly sparse solutions.

The neuron form of LISTA (3.5) could be viewed as a double-sided and translated variant of ReLU, which is continuous and piecewise linear. In contrast, HELU is a discontinuous function that rarely occurs in existing deep network neurons. As pointed out by [21], HELU has countably many discontinuities and is thus (Borel) measurable, in which case the universal approximation capability of the network is not compromised. However, experiments remind us that the algorithmic learnability with such discontinuous neurons (using popular first-order methods) is in question, and the training is in general hard. For computation concerns, we replace HELU with the following continuous and piecewise linear function ${\text{HELU}}_{\sigma }$, during network training:

${[{\text{HELU}}_{\sigma }(\mathbf{u})]}_i=\{\begin{array}{cc}0\hfill & \text{if}|{\mathbf{u}}_i|\le 1-\sigma ,\hfill \\ \frac{({\mathbf{u}}_i-1+\sigma )}{\sigma }\hfill & \text{if}1-\sigma <{\mathbf{u}}_i<1,\hfill \\ \frac{({\mathbf{u}}_i+1-\sigma )}{\sigma }\hfill & \text{if }-1<{\mathbf{u}}_i<\sigma -1,\hfill \\ {\mathbf{u}}_i\hfill & \text{if}|{\mathbf{u}}_i|\ge 1.\hfill \end{array}$

Obviously, ${\text{HELU}}_{\sigma }$ becomes HELU when $\sigma \to 0$. To approximate HELU, we tend to choose very small σ, while avoiding putting the training to be ill-posed. As a practical strategy, we start with a moderate σ (0.2 by default), and divide it by 10 after each epoch. After several epochs, ${\text{HELU}}_{\sigma }$ turns very close to the ideal HELU.

In [22], the authors introduced an ideal hard thresholding function for solving sparse coding, whose formulation was close to HELU. Note that [22] approximates the ideal function with a sigmoid function, which has connections with our ${\text{HELU}}_{\sigma }$ approximation. In [23], a similar truncated linear ReLU was utilized in the networks.

3.3.2 Deep M-Sparse ${\ell }_0$ Encoder

Both the ${\ell }_0$-regularized problem in (3.1) and deep ${\ell }_0$-regularized encoder have no explicit control on the sparsity level of the solution. One would therefore turn to the M-sparse problem in (3.2), and derive the following iterative algorithm [13]:

$\begin{array}{c}{\mathbf{a}}^{k+1}=h_M({\mathbf{a}}^k+{{\mathbf{D}}^{\mathbf{T}}(\mathbf{x}-\mathbf{Da}}^k)).\hfill \end{array}$

Equation (3.10) resembles (3.6), except that $h_M$ is now a nonlinear operator retaining the M coefficients with the top M-largest absolute values. Following the same methodology as in the previous section, the iterative form could be time-unfolded and truncated to the deep M-sparse encoder, as in Fig. 3.4. To deal with the $h_M$ operation, we refer to the popular concepts of pooling and unpooling [24] in deep networks, and introduce the pairs of max_M pooling and unpooling, as in Fig. 3.4.

Discussion about max_M pooling/unpooling. Pooling is popular in convolutional networks to obtain translation-invariant features [7]. It is yet less common in other forms of deep networks [25]. The unpooling operation was introduced in [24] to insert the pooled values back to the appropriate locations of feature maps for reconstruction purposes.

In our proposed deep M-sparse encoder, the pooling and unpooling operation pair is used to construct a projection from $R^m$ to its subset $S:=\{s\in R^m|||s|{|}_0\le M\}$. The max_M pooling and unpooling functions are intuitively defined as

$\begin{array}{c}[{\mathbf{p}}_M,{\mathbf{idx}}_M]=\text{max}{}_M\text{.pooling}(\mathbf{u}),\hfill \\ {\mathbf{u}}_M=\text{max}{}_M\text{.unpooling}({\mathbf{p}}_M,{\mathbf{idx}}_M).\hfill \end{array}$

For each input u, the pooled map ${\mathbf{p}}_M$ records the top M-largest values (irrespective of sign), and the switch ${\mathbf{idx}}_M$ records their locations. The corresponding unpooling operation takes the elements in ${\mathbf{p}}_M$ and places them in ${\mathbf{u}}_M$ at the locations specified by ${\mathbf{idx}}_M$, the remaining elements being set to zero. The resulting ${\mathbf{u}}_M$ is of the same dimension as u, but has exactly no more than M nonzero elements. In back propagation, each position in ${\mathbf{idx}}_M$ is propagated with the entire error signal.

3.3.3 Theoretical Properties

It is showed in [13] that the iterative algorithms in both (3.6) and (3.10) are guaranteed not to increase the cost functions. Under mild conditions, their targeted fixed points are local minima of the original problems. As the next step after the time truncation, the deep encoder models are to be solved by the stochastic gradient descent (SGD) algorithm, which converges to stationary points under a few stricter assumptions than those satisfied in this chapter [26].² However, the entanglement of the iterative algorithms and the SGD algorithm makes the overall convergence analysis really difficult.

One must emphasize that in each step, the back propagation procedure requires only operations of order O(p) [8]. The training algorithm takes O(Cnp) time (C is the constant absorbing epochs, stage numbers, etc.). The testing process is purely feed-forward and is therefore dramatically faster than traditional inference methods by solving (3.1) or (3.2). SGD is also easy to be parallelized.

3.5.1 Implementation

Two proposed deep ${\ell }_0$ encoders are implemented with the CUDA ConvNet package [7]. We use a constant learning rate of 0.01 with no momentum, and a batch size of 128. In practice, given that the model is well initialized, the training takes approximately 1 hour on the MNIST dataset, on a workstation with 12 Intel Xeon 2.67 GHz CPUs and 1 GTX680 GPU. It is also observed that the training efficiency of our model scales approximately linearly with the size of data.

While many neural networks train well with random initializations without pre-training, given that the training data is sufficient, it has been discovered that poorly initialized networks can hamper the effectiveness of first-order methods (e.g., SGD) [30]. For the proposed models, it is, however, much easier to initialize the model in the right regime, benefiting from the analytical relationships between sparse coding and network hyperparameters in (3.8).

3.5.2 Simulation on ${\ell }_0$ Sparse Approximation

We first compare the performance of different methods on ${\ell }_0$ sparse code approximation. The first 60,000 samples of the MNIST dataset are used for training and the last 10,000 for testing. Each patch is resized to $16\times 16$ and then preprocessed to remove its mean and normalize its variance. The patches with small standard deviations are discarded. A sparsity coefficient $\lambda =0.5$ is used in (3.1), and the sparsity level $M=32$ is fixed in (3.2). The sparse code dimension (dictionary size) p is to be varied.

Our prediction task resembles the setup in [8]: first learning a dictionary from training data, followed by solving sparse approximation (3.3) with respect to the dictionary, and finally training the network as a regressor from input samples to the solved sparse codes. The only major difference here lies in that unlike the ${\ell }_1$-based problems, the nonconvex ${\ell }_0$-based minimization could only reach a (nonunique) local minimum. To improve stability, we first solve the ${\ell }_1$-problems to obtain a good initialization for ${\ell }_0$-problems, and then run the iterative algorithms (3.6) or (3.10) until convergence. The obtained sparse codes are called “optimal codes” hereinafter and used in both training and testing evaluation (as “ground-truth”). One must keep in mind that we are not seeking to produce approximate sparse code for all possible input vectors, but only for input vectors drawn from the same distribution as our training samples.

We compare the proposed deep ${\ell }_0$ encoders with the iterative algorithms under different number of iterations. In addition, we include a baseline encoder into comparison, which is a fully-connected feed-forward network, consisting of three hidden layers of dimension p with ReLu neurons. The baseline encoder thus has the same parameter capacity as deep ${\ell }_0$ encoders.³ We apply dropout to the baseline encoders, with the probabilities of retaining the units being 0.9, 0.9, and 0.5. The proposed encoders do not apply dropout.

The deep ${\ell }_0$ encoders and the baseline encoder are first trained, and all are then evaluated on the testing set. We calculate the total prediction errors, i.e., the normalized squared errors between the optimal codes and the predicted codes, as in Tables 3.1 and 3.2. For the M-sparse case, we also compare their recovery of nonzero supports in Table 3.3, by counting the mismatched nonzero element locations between optimal and predicted codes (averaged on all samples). Immediate conclusions from the numerical results are as follows:

3.5.3 Applications on Classification

Since the task-driven models are trained from end to end, no precomputation of a is needed. For classification, we evaluate our methods on the MNIST dataset, and the AVIRIS Indiana Pines hyperspectral image dataset (see [31] for details). We compare our two proposed deep encoders with two competitive sparse coding-based methods: (1) task-driven sparse coding (TDSC) in [28], with the original setting followed and all parameters carefully tuned; (2) a pre-trained LISTA followed by supervised tuning with softmax loss. Note that for the deep M-sparse encoder, M is not known in advance and has to be tuned. To our surprise, the fine-tuning of M is likely to improve the performances significantly, which is analyzed next. The overall error rates are compared in Tables 3.4 and 3.5.

In general, the proposed deep ${\ell }_0$ encoders provide superior results to the deep ${\ell }_1$-based method (tuned LISTA). TDSC also generates competitive results, but at the cost of the high complexity for inference, i.e., solving conventional sparse coding. It is of particular interest to us that when supplied with specific M values, the deep M-sparse encoder can generate remarkably improved results.⁴ Especially in Table 3.5, when $M=10$, the error rate is around 1.5% lower than that of $M=30$. Note that in the AVIRIS Indiana Pines dataset, the training data volume is much smaller than that of MNIST. In this way, we conjecture that it might not be sufficiently effective to make the training process depend fully on data; instead, crafting a stronger sparsity prior by smaller M could help learn more discriminative features.⁵ Such a behavior provides us with an important hint to impose suitable structural priors to deep networks.

3.5.4 Applications on Clustering

For clustering, we evaluate our methods on the COIL 20 and the CMU PIE datasets [32]. Two state-of-the-art methods to compare are the jointly optimized sparse coding and clustering method proposed in [29], as well as the graph-regularized deep clustering method in [33].⁶ The overall error rates are compared in Tables 3.6 and 3.7.

Note that the method in [33] incorporated Laplacian regularization as an additional prior while the others did not. It is thus no wonder that this method often performs better than others. Even without any graph information utilized, the proposed deep encoders are able to obtain very close performances, and outperform [33] in certain cases. On the COIL 20 dataset, the lowest error rate is reached by the deep M-sparse ($M=10$) Encoder, when $p=512$, followed by the deep ${\ell }_0$-regularized encoder.

On the CMU PIE dataset, the deep ${\ell }_0$-regularized encoder leads to competitive accuracy with [33], and outperforms all deep M-sparse encoders with noticeable margins, which is different from other cases. Previous work discovered that sparse approximations over CMU PIE had significant errors [34], which is also verified by us. Therefore, hardcoding exact sparsity could even hamper the model performance.

Remark. From the experiments, we gain additional insights in designing deep architectures:

We hope the above insights could be of reference to many other deep learning models.