Year: 2020

Abstract:
We introduce a sparse scattering deep convolutional neural network, which provides a simple model to analyze properties of deep representation learning for classification. Learning a single dictionary matrix with a classifier yields a higher classification accuracy than AlexNet over the ImageNet 2012 dataset. The network first applies a scattering transform that linearizes variabilities due to geometric transformations such as translations and small deformations. A sparse ` dictionary coding reduces intra-class variability while preserving class separation through projections over unions of linear spaces. It is implemented in a deep convolutional network with a homotopy algorithm having an exponential convergence. A convergence proof is given in a general framework that includes ALISTA. Classification results are analyzed on ImageNet.

heading: 1 INTRODUCTION
text: Deep convolutional networks have spectacular applications to classification and regression (LeCun et al., 2015), but they are black boxes that are hard to analyze mathematically because of their architecture complexity. Scattering transforms are simplified convolutional neural networks with wavelet filters which are not learned (Bruna & Mallat, 2013). They provide state-of-the-art classification results among predefined or unsupervised representations, and are nearly as efficient as learned deep networks on relatively simple image datasets, such as digits in MNIST, textures (Bruna & Mallat, 2013) or small CIFAR images (Oyallon & Mallat, 2014; Mallat, 2016). However, over complex datasets such as ImageNet, the classification accuracy of a learned deep convolutional network is much higher than a scattering transform or any other predefined representation (Oyallon et al., 2019). A fundamental issue is to understand the source of this improvement. This paper addresses this question by showing that one can reduce the learning to a single dictionary matrix, which is used to compute a positive sparse `1 code.
The resulting algorithm is implemented with a simplified convolutional neural network architecture illustrated in Figure 1. The classifier input is a positive `1 sparse code of scattering coefficients calculated in a dictionary D. The matrix D is learned together with the classifier by minimizing a classification loss over a training set. We show that learning D improves the performance of a scattering
representation considerably and is sufficient to reach a higher accuracy than AlexNet (Krizhevsky et al., 2012) over ImageNet 2012. This cascade of well understood mathematical operators provides a simplified mathematical model to analyze optimization and classification performances of deep neural networks.
Dictionary learning for classification was introduced in Mairal et al. (2009) and implemented with deep convolutional neural network architectures by several authors (Sulam et al., 2018; Mahdizadehaghdam et al., 2019; Sun et al., 2018). To reach good classification accuracies, these networks cascade several dictionary learning blocks. As a result, there is no indication that these operators compute optimal sparse `1 codes. These architectures are thus difficult to analyze mathematically and involve heavy calculations. They have only been applied to small image classification problems such as MNIST or CIFAR, as opposed to ImageNet. Our architecture reaches a high classification performance on ImageNet with only one dictionaryD, because it is applied to scattering coefficients as opposed to raw images. Intra-class variabilities due to geometric image transformations such as translations or small deformations are linearized by a scattering transform (Bruna & Mallat, 2013), which avoids unnecessary learning.
Learning a dictionary in a deep neural network requires to implement a sparse `1 code. We show that homotopy iterative thresholding algorithms lead to more efficient sparse coding implementations with fewer layers. We prove their exponential convergence in a general framework that includes the ALISTA (Liu et al., 2019) algorithm. The main contributions of the paper are summarized below:
• A sparse scattering network architecture, illustrated in Figure 1, where the classification is performed over a sparse code computed with a single learned dictionary of scattering coefficients. It outperforms AlexNet over ImageNet 2012.
• A new dictionary learning algorithm with homotopy sparse coding, optimized by gradient descent in a deep convolutional network. If the dictionary is sufficiently incoherent, the homotopy sparse coding error is proved to convergence exponentially.
We explain the implementation and mathematical properties of each element of the sparse scattering network. Section 2 briefly reviews multiscale scattering transforms. Section 3 introduces homotopy dictionary learning for classification, with a proof of exponential convergence under appropriate assumptions. Section 4 analyzes image classification results of sparse scattering networks on ImageNet 2012.

heading: 2 SCATTERING TRANSFORM
text: A scattering transform is a cascade of wavelet transforms and ReLU or modulus non-linearities. It can be interpreted as a deep convolutional network with predefined wavelet filters (Mallat, 2016). For images, wavelet filters are calculated from a mother complex wavelet ψ whose average is zero. It is rotated by r−θ, dilated by 2j and its phase is shifted by α:
ψj,θ(u) = 2 −2jψ(2−jr−θu) and ψj,θ,α = Real(e−iα ψj,θ)
We choose a Morlet wavelet as in Bruna & Mallat (2013) to produce a sparse set of non-negligible wavelet coefficients. A ReLU is written ρ(a) = max(a, 0).
Scattering coefficients of orderm = 1 are computed by averaging rectified wavelet coefficients with a subsampling stride of 2J :
Sx(u, k, α) = ρ(x ? ψj,θ,α) ? φJ(2 Ju) with k = (j, θ)
where φJ is a Gaussian dilated by 2J (Bruna & Mallat, 2013). The averaging by φJ eliminates the variations of ρ(x ? ψj,θ,α) at scales smaller than 2J . This information is recovered by computing their variations at all scales 2j ′ < 2J , with a second wavelet transform. Scattering coefficients of order two are:
Sx(u, k, k′, α, α′) = ρ(ρ(x ? ψj,θ,α) ? ψj′,θ′,α′) ? φJ(2 Ju) with k, k′ = (j, θ), (j′, θ′)
To reduce the dimension of scattering vectors, we define phase invariant second order scattering coefficients with a complex modulus instead of a phase sensitive ReLU:
Sx(u, k, k′) = ||x ? ψj,θ| ? ψj′,θ′ | ? φJ(2Ju) for j′ > j
The scattering representation includes order 1 coefficients and order 2 phase invariant coefficients. In this paper, we choose J = 4 and hence 4 scales 1 ≤ j ≤ J , 8 angles θ and 4 phases α on [0, 2π]. Scattering coefficients are computed with the software package Kymatio (Andreux et al., 2018). They preserve the image information, and x can be recovered from Sx (Oyallon et al., 2019). For computational efficiency, the dimension of scattering vectors can be reduced by a factor 6 with a linear operator L that preserves the ability to recover a close approximation of x from LSx. The dimension reduction operator L of Figure 1 may be an orthogonal projection over the principal directions of a PCA calculated on the training set, or it can be optimized by gradient descent together with the other network parameters.
The scattering transform is Lipschitz continuous to translations and deformations (Mallat, 2012). Intra-class variabilities due to translations smaller than 2J and small deformations are linearized. Good classification accuracies are obtained with a linear classifier over scattering coefficients in image datasets where translations and deformations dominate intra-class variabilities. This is the case for digits in MNIST or texture images (Bruna & Mallat, 2013). However, it does not take into account variabilities of pattern structures and clutter which dominate complex image datasets. To remove this clutter while preserving class separation requires some form of supervised learning. The sparse scattering network of Figure 1 computes a sparse code of scattering representation β = LSx in a learned dictionary D of scattering features, which minimizes the classification loss. For this purpose, the next section introduces a homotopy dictionary learning algorithm, implemented in a small convolutional network.

heading: 3 HOMOTOPY DICTIONARY LEARNING FOR CLASSIFICATION
text: Task-driven dictionary learning for classification with sparse coding was proposed in Mairal et al. (2011). We introduce a small convolutional network architecture to implement a sparse `1 code and learn the dictionary with a homotopy continuation on thresholds. The next section reviews dictionary learning for classification. Homotopy sparse coding algorithms are studied in Section 3.2.

heading: 3.1 SPARSE CODING AND DICTIONARY LEARNING
text: Unless specified, all norms are Euclidean norms. A sparse code approximates a vector β with a linear combination of a minimum number of columns Dm of a dictionary matrix D, which are normalized ‖Dm‖ = 1. It is a vector α0 of minimum support with a bounded approximation error ‖Dα0 − β‖ ≤ σ. Such sparse codes have been used to optimize signal compression (Mallat & Zhang, 1993) and to remove noise, to solve inverse problems in compressed sensing (Candes et al., 2006), and for classification (Mairal et al., 2011). In this case, the dictionary learning optimizes the matrix D in order to minimize the classification loss. The resulting columns Dm can be interpreted as classification features selected by the sparse code α0. To enforce this interpretation, we impose that sparse code coefficients are positive, α0 ≥ 0.
Positive sparse coding Minimizing the support of a code α amounts to minimizing its `0 "norm", which is not convex. This non-convex optimization is convexified by replacing the `0 norm by an `1 norm. Since α ≥ 0, we have ‖α‖1 = ∑ m α(m). The minimization of ‖α‖1 with ‖Dα− β‖ ≤ σ is solved by minimizing a convex Lagrangian with a multiplier λ∗ which depends on σ:
α1 = argmin α≥0
1 2 ‖Dα− β‖2 + λ∗ ‖α‖1 (1)
One can prove (Donoho & Elad, 2006) that α1(m) has the same support as the minimum support sparse code α0(m) along m if the support size s and the dictionary coherence satisfy:
s µ(D) < 1/2 where µ(D) = max m 6=m′ |DtmDm′ | (2)
The sparse approximation Dα1 is a non-linear filtering which preserves the components of β which are "coherent" in the dictionary D, represented by few large amplitude coefficients. It eliminates the "noise" corresponding to incoherent components of β whose correlations with all dictionary vectors Dm are typically below λ∗, which can be interpreted as a threshold.
Supervised dictionary learning with a deep neural network Dictionary learning for classification amounts to optimizing the matrix D and the threshold λ∗ to minimize the classification loss on a training set {(xi, yi)}i. This is a much more difficult non-convex optimization problem than the convex sparse coding problem (1). The sparse code α1 of each scattering representation β = LSx depends upon D and λ∗. It is used as an input to a classifier parametrized by Θ. The classification loss ∑ i Loss(D,λ∗,Θ, xi, yi) thus depends upon the dictionary D and λ∗ (through α
1), and on the classification parameters Θ. The dictionary D is learned by minimizing the classification loss. This task-driven dictionary learning strategy was introduced in Mairal et al. (2011).
An implementation of the task-driven dictionary learning strategy with deep neural networks has been proposed in (Papyan et al., 2017; Sulam et al., 2018; Mahdizadehaghdam et al., 2019; Sun et al., 2018). The deep network is designed to approximate the sparse code by unrolling a fixed number N of iterations of an iterative soft thresholding algorithm. The network takes β as input and is parametrized by the dictionary D and the Lagrange multiplier λ∗, as shown in Figure 2. The classification loss is then minimized with stochastic gradient descent on the classifier parameters and on D and λ∗. The number of layers in the network is equal to the number N of iterations used to approximate the sparse code. During training, the forward pass approximates the sparse code with respect to the current dictionary, and the backward pass updates the dictionary through a stochastic gradient descent step.
For computational efficiency the main issue is to approximate α1 with as few layers as possible and hence find an iterative algorithm which converges quickly. Next section shows that this can be done with homotopy algorithms, that can have an exponential convergence.

heading: 3.2 HOMOTOPY ITERATED SOFT THRESHOLDING ALGORITHMS
text: Sparse `1 codes are efficiently computed with iterative proximal gradient algorithms (Combettes & Pesquet, 2011). For a positive sparse code, these algorithms iteratively apply a linear operator and a rectifier which acts as a positive thresholding. They can thus be implemented in a deep neural network. We show that homotopy algorithms can converge exponentially and thus lead to precise calculations with fewer layers.
Iterated Positive Soft Thresholding with ReLU Proximal gradient algorithms compute sparse `1 codes with a gradient step on the regression term ‖x − Dz‖2 followed by proximal projection which enforces the sparse penalization (Combettes & Pesquet, 2011). For a positive sparse code, the proximal projection is defined by:
proxλ(β) = argmin α≥0
1 2 ‖α− β‖2 + λ ‖α‖1 (3)
Since ‖α‖1 = ∑ m α(m) for α(m) ≥ 0, we verify that proxλ(β) = ρ(β − λ) where ρ(a) = max(a, 0) is a rectifier, with a bias λ. The rectifier acts as a positive soft thresholding, where λ is the threshold. Without the positivity condition α ≥ 0, the proximal operator in (3) is a soft thresholding which preserves the sign.
An Iterated Soft Thresholding Algorithm (ISTA) (Daubechies et al., 2004) computes an `1 sparse code α1 by alternating a gradient step on ‖Dx− z‖2 and a proximal projection. For positive codes, it is initialized with α0 = 0, and:
αn+1 = ρ(αn + D t(β −Dαn)− λ∗) with <
1
‖DtD‖2,2 (4)
where ‖ . ‖2,2 is the spectral norm. The first iteration computes a non-sparse code α1 = ρ( Dtβ − λ∗) which is progressively sparsified by iterated thresholdings. The convergence is slow: ‖αn−α1‖ = O(n−1). Fast Iterated Soft Thresholding Agorithm (FISTA) (Beck & Teboulle, 2009) accelerates the error decay to O(n−2), but it remains slow.
Each iteration of ISTA and FISTA is computed with linear operators and a thresholding and can be implemented with one layer (Papyan et al., 2017). The slow convergence of these algorithms requires to use a large number N of layers to compute an accurate sparse `1 code. We show that the number of layers can be reduced considerably with homotopy algorithms.
Homotopy continuation Homotopy continuation algorithms introduced in Osborne et al. (2000), minimize the `1 Lagrangian (1) by progressively decreasing the Lagrange multiplier. This optimization path is opposite to ISTA and FISTA since it begins with a very sparse initial solution whose sparsity is progressively reduced, similarly to matching pursuit algorithms (Davis et al., 1997; Donoho & Tsaig, 2008). Homotopy algorithms are particularly efficient if the final Lagrange multiplier λ∗ is large and thus produces a very sparse optimal solution. We shall see that it is the case for classification.
Homotopy proximal gradient descents (Xiao & Zhang, 2013) are implemented with an exponentially decreasing sequence of Lagrange multipliers λn for n ≤ N . Jiao, Jin and Lu (Jiao et al., 2017) have introduced an Iterative Soft Thresholding Continuation (ISTC) algorithm with a fixed number of iterations per threshold. To compute a positive sparse code, we replace the soft thresholding by a ReLU proximal projector, with one iteration per threshold, over n ≤ N iterations:
αn = ρ(αn−1 +D t(β −Dαn−1)− λn) with λn = λmax (λmax λ∗ )−n/N (5)
By adapting the proof of (Jiao et al., 2017) to positive codes, the next theorem proves in a more general framework that ifN is sufficiently large and λmax ≥ ‖Dtβ‖∞ then αn converges exponentially to the optimal positive sparse code.
LISTA algorithm (Gregor & LeCun, 2010) and its more recent version ALISTA (Liu et al., 2019) accelerate the convergence of proximal algorithms by introducing an auxiliary matrix W , which is adapted to the statistics of the input and to the properties of the dictionary. Such an auxiliary matrix may also improve classification accuracy. We study its influence by replacing Dt by an arbitrary matrix W t in (5). Each column Wm of W is normalized by |W tmDm| = 1. A generalized ISTC is defined for any dictionary D and any auxiliary W by:
αn = ρ(αn−1 +W t(β −Dαn−1)− λn) with λn = λmax (λmax λ∗ )−n/N (6)
If W = D then we recover the original ISTC algorithm (5) (Jiao et al., 2017). Figure 2 illustrates a neural network implementation of this generalized ISTC algorithm over N layers, with side connections. Let us introduce the mutual coherence of W and D
µ̃ = max m6=m′
|W tm′Dm|
The following theorem gives a sufficient condition on this mutual coherence and on the thresholds so that αn converges exponentially to the optimal sparse code. ALISTA (Liu et al., 2019) is a particular case of generalized ISTC where W is optimized in order to minimize the mutual coherence µ̃. In Section 4.1 we shall optimizeW jointly withD without any analytic mutual coherence minimization like in ALISTA.
Theorem 3.1 Let α0 be the `0 sparse code of β with error ‖β−Dα0‖ ≤ σ. If its support s satisfies
s µ̃ < 1/2 (7)
then thresholding iterations (6) with
λn = λmax γ −n ≥ λ∗ = ‖W t(β −Dα0)‖∞ 1− 2γµ̃s
(8)
define an αn, whose support is included in the support of α0 if 1 < γ < (2µ̃s)−1 and λmax ≥ ‖W tβ‖∞. The error then decreases exponentially:
‖αn − α0‖∞ ≤ 2λmax γ−n (9)
The proof is in Appendix A of the supplementary material. It adapts the convergence proof of Jiao et al. (2017) to arbitrary auxiliary matrices W and positive sparse codes. If we set W to minimize the mutual coherence µ̃ then this theorem extends the ALISTA exponential convergence result to the noisy case. It proves exponential convergence by specifying thresholds for a non-zero approximation error σ.
However, one should not get too impressed by this exponential convergence rate because the condition sµ̃ < 1/2 only applies to very sparse codes in highly incoherent dictionaries. Given a dictionary D, it is usually not possible to findW which satisfies this hypothesis. However, this sufficient condition is based on a brutal upper bound calculation in the proof. It is not necessary to get an exponential convergence. Next section studies learned dictionaries for classification on ImageNet and shows that when W = D, the ISTC algorithm converges exponentially although sµ(D) > 1/2. When W is learned independently from D, with no mutual coherence condition, we shall see that the algorithm may not converge.

heading: 4 IMAGE CLASSIFICATION
text: The goal of this work is to construct a deep neural network model which is sufficiently simple to be analyzed mathematically, while reaching the accuracy of more complex deep convolutional networks on large classification problems. This is why we concentrate on ImageNet as opposed to MNIST or CIFAR. Next section shows that a single `1 sparse code in a learned dictionary improves considerably the classification performance of a scattering representation, and outperforms AlexNet on ImageNet 1. We analyze the influence of different architecture components. Section 4.2 compares the convergence of homotopy iterated thresholdings with ISTA and FISTA.

heading: 4.1 IMAGE CLASSIFICATION ON IMAGENET
text: ImageNet 2012 (Russakovsky et al., 2015) is a challenging color image dataset of 1.2 million training images and 50,000 validation images, divided into 1000 classes. Prior to convolutional networks, SIFT representations combined with Fisher vector encoding reached a Top 5 classification accuracy of 74.3% with multiple model averaging (Sánchez & Perronnin, 2011). In their PyTorch implementation, the Top 5 accuracy of AlexNet and ResNet-152 is 79.1% and 94.1% respectively2.
The scattering transform Sx at a scale 2J = 16 of an ImageNet color image is a spatial array of 14× 14 of 1539 channels. If we apply to Sx the same MLP classifier as in AlexNet, with 2 hidden layers of size 4096, ReLU and dropout rate of 0.3, the Top 5 accuracy is 65.3%. We shall use the same AlexNet type MLP classifier in all other experiments, or a linear classifier when specified. If we first apply to Sx a 3-layer SLE network of 1x1 convolutions with ReLU and then the same MLP then the accuracy is improved by 14% and it reaches AlexNet performance (Oyallon et al., 2017). However, there is no mathematical understanding of the operations performed by these three layers, and the origin of the improvements, which partly motivates this work.
The sparse scattering architecture is described in Figure 3. A 3 × 3 convolutional operator L is applied on a standardized scattering transform to reduce the number of scattering channels from 1539 to 256. It includes 3.5 106 learned parameters. The ISTC network illustrated in Figure 2 has N = 12 layers with ReLU and no batch normalization. A smaller network with N = 8 has nearly the same classification accuracy but the ISTC sparse coding does not converge as well, as explained in Section 4.2. Increasing N to 14 or 16 has little impact on accuracy and on the code precision.
1Code to reproduce experiments is available at https://github.com/j-zarka/SparseScatNet 2Accuracies from https://pytorch.org/docs/master/torchvision/models.html
The sparse code is first calculated with a 1 × 1 convolutional dictionary D having 2048 vectors. Dictionary columns Dm have a spatial support of size 1 and thus do not overlap when translated. It preserves a small dictionary coherence so that the iterative thresholding algorithm converges exponentially. This ISTC network takes as input an array LSx of size 14 × 14 × 256 which has been normalized and outputs a code α1 of size 14 × 14 × 2048 or a reconstruction Dα1 of size 14× 14× 256. The total number of learned parameters in D is about 5 105. The output α1 or Dα1 of the ISTC network is transformed by a batch normalization, and a 5× 5 average pooling and then provided as input to the MLP classifier. The representation is computed with 4 106 parameters in L andD, which is above the 2.5 106 parameters of AlexNet. Our goal here is not to reduce the number of parameters but to structure the network into well defined mathematical operators.
If we set W = D in the ISTC network, the supervised learning jointly optimizes L, the dictionary D with the Lagrange multiplier λ∗ and the MLP classifier parameters. It is done with a stochastic gradient descent during 160 epochs using an initial learning rate of 0.01 with a decay of 0.1 at epochs 60 and 120. With a sparse code in input of the MLP, it has a Top 5 accuracy of 81.0%, which outperforms AlexNet.
If we also jointly optimize W to minimize the classification loss, then the accuracy improves to 83.7%. However, next section shows that in this case, the ISTC network does not compute a sparse `1 code and is therefore not mathematically understood. In the following we thus impose that W = D.
The dimension reduction operator L has a marginal effect in terms of performance. If we eliminate it or if we replace it by an unsupervised PCA dimension reduction, the performance drops by less than 2%, whereas the accuracy drops by almost 16% if we eliminate the sparse coding. The number of learned parameters to compute α1 then drops from 4 106 to 5 105. The considerable improvement brought by the sparse code is further amplified if the MLP classifier is replaced by a much smaller linear classifier. A linear classifier on a scattering vector has a (Top 1, Top 5) accuracy of (26.1%, 44.7%). With a ISTC sparse code with W = D in a learned dictionary the accuracy jumps to (51.6%, 73.7%) and hence improves by nearly 30%.
The optimization learns a relatively large factor λ∗ which yields a large approximation error ‖LSx − Dα1‖/‖LSx‖ ≈ 0.5, and a very sparse code α1 with about 4% non-zero coefficients. The sparse approximation Dα1 thus eliminates nearly half of the energy of LS(x) which can be interpreted as non-informative "clutter" removal. The sparse approximation Dα1 of LSx has a small
dimension 14 × 14 × 256 similar to AlexNet last convolutional layer output. If the MLP classifier is applied to Dα1 as opposed to α1 then the accuracy drops by less than 2% and it remains slightly above AlexNet. Replacing LSx by Dα1 thus improves the accuracy by 14%. The sparse coding projection eliminates "noise", which seems to mostly correspond to intra-class variabilities while carrying little discriminative information between classes. Since Dα1 is a sparse combination of dictionary columns Dm, each Dm can be interpreted as "discriminative features" in the space of scattering coefficients. They are optimized to preserve discriminative directions between classes.

heading: 4.2 CONVERGENCE OF HOMOTOPY ALGORITHMS
text: To guarantee that the network can be analyzed mathematically, we verify numerically that the homotopy ISTC algorithm computes an accurate approximation of the optimal `1 sparse code in (1), with a small number of iterations.
When W = D, Theorem 3.1 guarantees an exponential convergence by imposing a strong incoherence condition s µ(D) < 1/2. In our classification setting, sµ(D) ≈ 60 so the theorem hypothesis is clearly not satisfied. However, this incoherence condition is not necessary. It is derived from a relatively crude upper bound in the proof of Appendix A.1. Figure 4 left shows numerically that the ISTC algorithm for W = D minimizes the Lagrangian L(α) = 12‖Dα − β‖
2 + λ∗ ‖α‖1 over α ≥ 0, with an exponential convergence which is faster than ISTA and FISTA. This is tested with a dictionary learned by minimizing the classification loss over ImageNet.
If we jointly optimize W and D to minimize the classification loss then the ImageNet classification accuracy improves from 81.0% to 83.7%. However, Figure 4 right shows that the generalized ISTC network outputs a sparse code which does not minimize the `1 Lagrangian at all. Indeed, the learned matrixW does not have a minimum joint coherence with the dictionaryD, as in ALISTA (Liu et al., 2019). The joint coherence then becomes very large with sµ̃ ≈ 300, which prevents the convergence. Computing W by minimizing the joint coherence would require too many computations.
To further compare the convergence speed of ISTC forW = D versus ISTA and FISTA, we compute the relative mean square error MSE(x, y) = ‖x − y‖2/‖x‖2 between the optimal sparse code α1 and the sparse code output of 12 iterations of each of these three algorithms. The MSE is 0.23 for FISTA and 0.45 for ISTA but only 0.02 for ISTC. In this case, after 12 iterations, ISTC reduces the error by a factor 10 compared to ISTA and FISTA.

heading: 5 CONCLUSION
text: This work shows that learning a single dictionary is sufficient to improve the performance of a predefined scattering representation beyond the accuracy of AlexNet on ImageNet. The resulting deep convolutional network is a scattering transform followed by a positive `1 sparse code, which are well defined mathematical operators. Dictionary vectors capture discriminative directions in
the scattering space. The dictionary approximations act as a non-linear projector which removes non-informative intra-class variations.
The dictionary learning is implemented with an ISTC network with ReLUs. We prove exponential convergence in a general framework that includes ALISTA. A sparse scattering network reduces the convolutional network learning to a single dictionary learning problem. It opens the possibility to study the network properties by analyzing the resulting dictionary. It also offers a simpler mathematical framework to analyze optimization issues.

heading: ACKNOWLEDGMENTS
text: This work was supported by the ERC InvariantClass 320959, grants from Région Ile-de-France and the PRAIRIE 3IA Institute of the French ANR-19-P3IA-0001 program. We thank the Scientific Computing Core at the Flatiron Institute for the use of their computing resources. We would like to thank Eugene Belilovsky for helpful discussions and comments.

heading: A APPENDIX
text: A.1 PROOF OF THEOREM 3.1
Let α0 be the optimal `0 sparse code. We denote by S(α) the support of any α. We also write ρλ(a) = ρ(a − λ). We are going to prove by induction on n that for any n ≥ 0 we have S(αn) ⊂ S(α0) and ‖αn − α0‖∞ ≤ 2λn if λn ≥ λ∗. For n = 0, α0 = 0 so S(α0) = ∅ is indeed included in the support of α0 and ‖α0−α0‖∞ = ‖α0‖∞. To verify the induction hypothesis for λ0 = λmax ≥ λ∗, we shall prove that ‖α0‖∞ ≤ 2λmax.
Let us write the error w = β −Dα0. For all m
α0(m)W tmDm = W t mβ −W tmw − ∑ m6=m′ α0(m′)W tmDm′ .
Since the support of α0 is smaller than s, W tmDm = 1 and µ̃ = maxm 6=m′ |W tmDm′ |
|α0(m)| ≤ |W tmβ|+ |W tmw|+ s µ̃ ‖α0‖∞ so taking the max on m gives:
‖α0‖∞(1− µ̃s) ≤ ‖W tβ‖∞ + ‖W tw‖∞ But given the inequalities
‖W tβ‖∞ ≤ λmax ‖W tw‖∞ ≤ λmax(1− 2γµ̃s) (1− γµ̃s) (1− µ̃s) ≤ 1 since γ ≥ 1 and (1− µ̃s) > 0
we get ‖α0‖∞ ≤ 2λmax = 2λ0
Let us now suppose that the property is valid for n and let us prove it for n + 1. We denote by DA the restriction of D to vectors indexed by A. We begin by showing that S(αn+1) ⊂ S(α0). For any m ∈ S(αn+1), since β = Dα0 + w and W tmDm = 1 we have αn+1(m) = ρλn+1(αn(m) +W t m(β −Dαn))
= ρλn+1(α 0(m) +W tm(DS(α0)∪S(αn)−{m}(α 0 − αn)S(α0)∪S(αn)−{m} + w))
For any m not in S(α0), let us prove that αn+1(m) = 0. The induction hypothesis assumes that S(αn) ⊂ S(α0) and ‖α0 − αn‖∞ ≤ 2λn with λn ≥ λ∗ so:
I = |α0(m) +W tm(DS(α0)∪S(αn)−{m}(α 0 − αn)S(α0)∪S(αn)−{m} + w)|
≤ |W tm(DS(α0)(α0 − αn)S(α0))|+ |W tmw| since S(αn) ⊂ S(α0) and α0(m) = 0 by assumption. ≤ µ̃s‖α0 − αn‖∞ + ‖W tw‖∞
Since we assume that λn+1 ≥ λ∗, we have ‖W tw‖∞ ≤ (1− 2γµ̃s)λn+1
and thus
I ≤ µ̃s‖α0 − αn‖∞ + ‖W tw‖∞ ≤ µ̃s2λn + λn+1(1− 2γµ̃s) ≤ λn+1 since λn = γλn+1.
Because of the thresholding ρλn+1 , it proves that αn+1(m) = 0 and hence that S(αn+1) ⊂ S(α0).
Let us now evaluate ‖α0 − αn+1‖∞. For any (α1, α2, λ), a soft thresholding satisfies |ρλ(α1 + α2)− α1| ≤ λ+ |α2|
so:
|αn+1(m)− α0(m)| ≤ λn+1 + |W tm(DS(α0)∪S(αn)−{m}(α 0 − αn)S(α0)∪S(αn)−{m})|+ |W t mw|
≤ λn+1 + µ̃s‖α0 − αn‖∞ + ‖W tw‖∞ ≤ λn+1 + µ̃s2λn + λn+1(1− 2γµ̃s) = 2λn+1
Taking a max over m proves the induction hypothesis.

Review summaries:
The paper proposes an interpretable architecture for image classification based on a scattering transform and sparse dictionary learning approach. The scattering transform acts as a pre-trained interpretable feature extractor that does not require data. A sparse dictionary on top of this representation (the scattering coefficients) is learnt to minimize the classification error. The authors cast the dictionary learning as a classical CNN learning approach and implement an efficient solution via homotopy learning (given that some assumptions are fulfilled). The scattering transform approach is not new (as the authors mention in the paper, it was published in Oyallon et al., 2019). The main novelty comes from applying a previously published dictionary learning approach (as the authors mention in the paper, it was published in Jiao et al., 2017) on top to boost the performance. As a second contribution, the authors extend the exponential convergence proof of ISTC (Jiao et al., 2017) and ALISTA (Liu et al., 2019). In the experiments, they show that the proposed architecture, despite its simplicity, outperform AlexNet in the ImageNet classification problem.

The paper proposes a network architecture composed of three interpretable components followed by a simple MLP classifier. It first applies a scattering transform followed by a learned linear projection (to reduce dimensionality). A sparse representation of these coefficients is then obtained using dictionary learning. The projection, dictionary and MLP classifier are jointly trained to minimize the classification loss. Results show that the model outperforms AlexNet on the Imagenet benchmark.