PaperlayerView exact revision on arXiv

Source-linked AI summary

Multi-Layer Convolutional Sparse Modeling: Pursuit and Dictionary Learning

Jeremias Sulam, Vardan Papyan, Yaniv Romano, Michael Elad

arXiv:1708.08705v2cs.CVcs.LGstat.ML

TL;DR

ML-CSC links CNN forward passes with nested sparse representations, but existing pursuits do not exactly satisfy the model and the guarantees loosen with depth. This paper studies projection-based pursuit, its stability, and dictionary learning, and reports applications with expressive models using few parameters. The authors also discuss an assumption needed for their deterministic worst-case theorems.

  • Problem

    Existing layered pursuits do not provide signals that comply exactly with ML-CSC assumptions, and their theoretical guarantees loosen with network depth.

    Source: §I · p. 1

  • Method

    The paper studies projection onto ML-CSC, derives stability results for practical algorithms, and proposes adapting dictionaries across layers to represent natural images.

    Source: §VI · p. 14

  • Results

    The authors demonstrate ML-CSC on practical applications and report significant expressiveness with a very small number of model parameters.

    Source: §VI · p. 14

  • Takeaways & Limitations

    The learned multilayer dictionaries provide a way to represent natural images within the ML-CSC framework.

    Source: §VI · p. 14

    The NVS assumption is needed for the deterministic worst-case theorems discussed in the paper.

    Source: E. Discussion on Theorem 6 and Theorem 7 · p. 18

Abstract

from arXiv · show

The recently proposed Multi-Layer Convolutional Sparse Coding (ML-CSC) model, consisting of a cascade of convolutional sparse layers, provides a new interpretation of Convolutional Neural Networks (CNNs). Under this framework, the computation of the forward pass in a CNN is equivalent to a pursuit algorithm aiming to estimate the nested sparse representation vectors -- or feature maps -- from a given input signal. Despite having served as a pivotal connection between CNNs and sparse modeling, a deeper understanding of the ML-CSC is still lacking: there are no pursuit algorithms that can serve this model exactly, nor are there conditions to guarantee a non-empty model. While one can easily obtain signals that approximately satisfy the ML-CSC constraints, it remains unclear how to simply sample from the model and, more importantly, how one can train the convolutional filters from real data. In this work, we propose a sound pursuit algorithm for the ML-CSC model by adopting a projection approach. We provide new and improved bounds on the stability of the solution of such pursuit and we analyze different practical alternatives to implement this in practice. We show that the training of the filters is essential to allow for non-trivial signals in the model, and we derive an online algorithm to learn the dictionaries from real data, effectively resulting in cascaded sparse convolutional layers. Last, but not least, we demonstrate the applicability of the ML-CSC model for several applications in an unsupervised setting, providing competitive results. Our work represents a bridge between matrix factorization, sparse dictionary learning and sparse auto-encoders, and we analyze these connections in detail.

I. INTRODUCTION

Sparse coding represents signals with a few atoms, and ML-CSC extends convolutional sparse coding into nested layers linked to CNNs. The section motivates a closer study of exact pursuit, model structure, and learning from real data.

I. INTRODUCTION

  • Sparse representation modeling describes natural signals as linear combinations of a few building blocks, or atoms, and dictionary learning adapts those atoms from real data,.The paper situates these methods across signal processing and machine learning applications,,,,,.Source: §I · p. 1
  • Earlier ML-CSC work connected CNN forward passes to approximate sparse pursuit, but its pursuits do not satisfy the model exactly and their guarantees loosen with depth.The paper frames its study around projection, stability, learning dictionaries, and unsupervised applications.Source: §I · pp. 1–2

A. Convolutional Sparse Coding

  • Convolutional Sparse Coding represents a signal as D1γ1, using a sparse representation and a convolutional dictionary of local filters.Each signal patch is associated with a local model based on a stripe of the global representation.Source: A. Convolutional Sparse Coding · p. 2

B. Multi Layer CSC

  • ML-CSC imposes nested sparse convolutional representations, so products of layer dictionaries form a structured global convolutional dictionary.Successive layers combine local atoms into more complex structures, illustrated as atoms, molecules, and a digit.Source: B. Multi Layer CSC · pp. 2–3, Figure 2 · p. 3

C. Pursuit in the noisy setting

In the noisy setting, pursuit estimates nested representations for measurements that differ from an ideal ML-CSC signal. Layer-wise relaxed pursuit can provide approximate estimates, but its discrepancies accumulate with depth.

C. Pursuit in the noisy setting

  • For measurements y = x + v with bounded noise, pursuit seeks representations that explain y within the allowed error while x belongs to the ML-CSC model.The section introduces this as the Deep Coding Problem.Source: C. Pursuit in the noisy setting · p. 4

(DCP E

  • The stability bound grows with network depth because layer-wise relaxation causes discrepancies to accumulate across layers.The section reports stability guarantees for this approximate pursuit setting, including the CNN forward pass.Source: (DCP E · p. 4
  • Layer-wise relaxed pursuit may leave nonzero residuals between successive representations, so its estimates need not define a signal in the ML-CSC model.In this case, the reconstructed signal and intermediate representations do not satisfy the model equalities.Source: (DCP E · p. 4

III. A PROJECTION ALTERNATIVE

The paper projects measurements onto the ML-CSC model by estimating the deepest representation and deriving the remaining layers. It establishes stability guarantees for this projection and gives a global sparse-coding pursuit to implement it.

III. A PROJECTION ALTERNATIVE

  • The ML-CSC projection seeks the closest signal to y whose representations satisfy the model constraints.This is more restrictive than the deep coding formulation, which allows model deviations across layers.Source: §III · p. 4

A. Stability of the projection PMλ

  • Projection stability bounds do not accumulate with network depth.The bounds use effective-dictionary mutual coherence; an alternative bound is tightest at the innermost layer and grows toward shallower layers.Source: A. Stability of the projection PMλ · pp. 4–5

B. Pursuit Algorithms

  • A global sparse-coding solver estimates the deepest representation, then derives the others so the estimate remains in the ML-CSC model.The approach avoids layer-wise sparse coding of intermediate features and provides provably stable solutions.Source: B. Pursuit Algorithms · p. 5

C. Stability Guarantees for Pursuit Algorithms

The section develops stability tools and recovery guarantees for the Multi-Layer Pursuit. Its bounds contrast greedy and convex approaches, with the guarantees tightest at the innermost layer.

Stability Guarantees for Pursuit Algorithms

  • The Non Vanishing Support property prevents overlapping atoms from canceling entries in the resulting representation.It holds with probability 1 when nonzero coefficients are drawn from a Normal distribution.Source: C. Stability Guarantees for Pursuit… · p. 5
  • N.V.S. implies maximal cardinality: among representations with equal support, applying the dictionary cannot produce more nonzeros than the N.V.S. representation.The conclusion follows because the output support cannot exceed the number of nonzero rows among the selected atoms.Source: C. Stability Guarantees for Pursuit… · p. 5
  • For ℓ0,∞-sparse signals, the CSC model is globally stable and admits an upper bound on local energy change in the ℓ2,∞ norm.The local result is one-sided; an analogous lower bound is conjectured, not established.Source: C. Stability Guarantees for Pursuit… · p. 6
  • The convex and greedy Multi-Layer Pursuit guarantees are tightest at the innermost layer and increase slightly toward shallower representations.The convex relaxation gives local error bounds, while the OMP implementation gives a global alternative; when consecutive layer dimensions are similar, the coefficient is roughly 2.Source: C. Stability Guarantees for Pursuit… · p. 6

D. Projecting General Signals

For arbitrary measurements, the paper proposes a greedy projection that grows the deepest representation while enforcing every layer’s sparsity constraint. It also shows that dictionary choice matters: random dictionaries can make the ML-CSC model empty.

D. Projecting General Signals

  • The general-signal projection progressively grows the deepest representation and accepts an estimate only while all intermediate sparsity constraints hold.If a constraint is violated, it returns the previously computed feasible signal; the presented procedure is completely greedy.Source: D. Projecting General Signals · pp. 6–7

E. Summary - Pursuit for the ML-CSC

  • The pursuit summary states that, for measurements close to an ML-CSC signal with bounded noise, OMP or BP yields approximate representations whose supports are subsets of the true supports.The resulting estimates satisfy the model constraints; for arbitrary measurements, the proposed OMP-inspired method increases support while maintaining those constraints.Source: E. Summary - Pursuit for the ML-CSC · p. 7

IV. LEARNING THE MODEL

  • Random dictionaries can make the ML-CSC model empty because the induced intermediate representation is dense.Thus, meaningful nested sparse representations depend on dictionary design.Source: §IV · p. 7

A. Sparse Dictionaries

The learning formulation uses sparsity in the deepest representation and intermediate dictionaries as proxies for sparsity in the nested features. An online alternating-minimization algorithm then estimates the deepest representation and updates the convolutional dictionaries.

A. Sparse Dictionaries

  • Sparse dictionaries support sampling by drawing deepest representations that meet their sparsity constraint, but the condition does not establish whether a model is non-empty.If both a representation and the preceding representation are sparse, the dictionaries must contain only a few nonzeros.Source: A. Sparse Dictionaries · pp. 7–8

B. Learning Formulation

  • Intermediate-feature sparsity is encouraged indirectly by penalizing deepest-code sparsity and the nonzeros in subsequent dictionaries.The formulation forces dictionaries from layer 2 to L to be sparse, while the reconstructed signal is not required to be sparse.Source: B. Learning Formulation · p. 8
  • The formulation estimates only the deepest sparse representation and enforces sparsity on dictionaries from layer 2 onward.Intermediate representations are not computed explicitly; the first dictionary is not constrained to be sparse.Source: B. Learning Formulation · p. 8
  • The online algorithm estimates each deepest representation, then updates dictionaries using projected gradient steps with hard thresholding.The dictionary update is an instance of Iterative Hard Thresholding.Source: B. Learning Formulation · pp. 8–9
  • The dictionary-sparsity parameters are less intuitive to choose, and setting them remains an open research question.The experiments report that manual settings can still yield effective constructions.Source: B. Learning Formulation · p. 9
  • The stated per-sample complexity is approximately (τ + TL) times that of a similar CNN architecture.The analysis omits potential savings from sparse convolutional kernels, which the authors leave for future work.Source: B. Learning Formulation · pp. 9–10

C. Connection to related works

The paper relates its learning formulation to hierarchical sparse factorization, dictionary learning, CNNs, and convolutional sparse autoencoders. On MNIST, the learned dictionaries combine local filters into sparse, more complex atoms, and the method is presented as competitive with dictionary-learning and autoencoder approaches.

C. Connection to related works

  • The formulation resembles hierarchical sparse-factor methods,, but uses convolutional factors updated through stochastic optimization.The paper also connects its approach to sparse-kernel dictionary learning and double-sparsity methods,,.Source: C. Connection to related works · p. 10
  • With a layered non-negative thresholding pursuit, the formulation implements a CNN with a final ReLU and sparse-filter penalties, as well as a convolutional sparse autoencoder.The paper frames its online block-coordinate descent method as competing favorably with dictionary-learning and convolutional-network autoencoder approaches in unsupervised settings.Source: C. Connection to related works · p. 10

V. EXPERIMENTS

  • D2 is 99% sparse and D3 is 99.8% sparse, combining local edges into increasingly complex atoms, including global atoms resembling digit parts.The first-layer filters are simple edges or blobs, while the final atoms are linear combinations of local edges.Source: §V · p. 11, Figure 5 · p. 11
  • Effective-dictionary mutual coherence often decreases with depth, alongside a reduction in redundancy to about 1.3 at the third layer.The authors caution that mutual coherence is a worst-case measure and does not directly indicate practical performance.Source: §V · p. 11
  • The learned model gives notably sparse multi-layer decompositions of an unseen MNIST image, and increasing representation cardinality can improve approximation quality.The decompositions represent the digit 3 at different scales.Source: §V · p. 11

A. Sparse Recovery

The section evaluates ML-CSC pursuit, sparse approximation, and unsupervised classification, then concludes that the model offers expressive representations with few parameters. Across the reported comparisons, projection improves recovery, while ML-CSC is competitive with sparse autoencoders and trainlets.

A. Sparse Recovery

  • Projection recovers representations more accurately than layered pursuit in the synthetic experiment, which was configured to somewhat favor the layered approach.The comparison uses relative ℓ2 error and normalized support intersection across sample cardinalities and layer depths.Source: A. Sparse Recovery · pp. 11–12
  • On noisy MNIST digits, projection gives accurate representation estimates with negligible support mistakes, while layered pursuit recovers only a small fraction of the correct support.Layered pursuit may find same-sparsity first-layer representations with lower data-fidelity error that do not satisfy the model, leading to further errors at deeper layers.Source: A. Sparse Recovery · p. 12

B. Sparse Approximation

  • ML-CSC achieves slightly lower representation error than k-sparse autoencoders across a wide range of nonzero counts, using 1–2 orders of magnitude fewer parameters.The comparison uses a fixed target sparsity of k = 10 for ML-CSC, without retraining separate models for each cardinality.Source: B. Sparse Approximation · p. 13, Figure 7 · p. 13
  • The ML-CSC model provides slightly better M-term representation error than k-sparse autoencoders, while OSDL is only slightly superior to ML-CSC.OSDL uses a parameter fraction matched to one ML-CSC model; its comparison also uses IHT sparse coding.Source: B. Sparse Approximation · p. 13

C. Unsupervised Classification

  • Combining second- and third-layer ML-CSC features yields 1.15% MNIST classification error, comparable to a Stacked Winner Take All autoencoder with the same number of neurons.A stacked convolutional WTA autoencoder achieves 0.48% error, but its 51,200-dimensional features are more than an order of magnitude larger than those of the other models.Source: C. Unsupervised Classification · pp. 13–14

VI. CONCLUSION

  • The authors report that the model provides significant expressiveness with very few parameters across several practical applications.They also identify incorporating pooling and addressing supervised or semi-supervised learning as open questions.Source: §VI · p. 14

APPENDIX

The appendix characterizes effective dictionaries formed by cascading convolutional layers and gives stability results for projection onto the ML-CSC model. The stability bounds rely on assumptions about the signal, noise, and dictionaries.

A. Properties of the ML-CSC model

  • Products of the layer dictionaries remain convolutional dictionaries, so the ML-CSC cascade is a structured global convolutional model.The effective filter dimension grows with the dimensions of the layer filters.Source: A. Properties of the ML-CSC model · p. 15

B. Stability result for the PMλ problem

  • The PMλ solution has stability bounds for noisy observations under the theorem's assumptions, including a simplified bound on representation error across layers.The simplified bound is ∥γ_i − ˆγ_i∥_2^2 ≤ E_L^2 2^(L−i).Source: B. Stability result for the PMλ problem · pp. 15–16

C. Local stability of the S-RIP

This subsection states a local one-sided near-isometry result for convolutional dictionaries satisfying Stripe-RIP. The bound relates the output patch norm to the stripe norm of the sparse representation.

C. Local stability of the S-RIP

  • For a convolutional dictionary satisfying Stripe-RIP, the local patch norm is bounded by the stripe norm scaled by 1 + δ_k.The result is stated as a one-sided bound, not an equality.Source: C. Local stability of the S-RIP · p. 16

D. Recovery guarantees for pursuit algorithms

This section gives recovery guarantees for the Multi-Layer Pursuit Algorithm in convex and greedy cases. The convex-relaxation result assumes locally bounded noise and representations satisfying the N.V.S. property.

D. Recovery guarantees for pursuit algorithms

  • The convex-relaxation recovery guarantee assumes locally bounded noise and the N.V.S. property for all representations.The N.V.S. condition rules out cancellation among atom supports when a dictionary acts on a sparse vector.Source: 1) Convex relaxation case · pp. 16–17

2) Greedy case:

The greedy Multi-Layer Pursuit recovery result bounds reconstruction error under energy-bounded noise and stated representation assumptions. Its proof uses OMP support recovery and propagates error bounds across layers.

2) Greedy case:

  • Theorem 7 gives a stable-recovery bound for the Multi-Layer Pursuit algorithm when the input has energy-bounded noise and the layer representations satisfy the stated assumptions.The bound relates recovery error to the noise level, sparsity, and dictionary coherence.Source: 2) Greedy case · pp. 17–18
  • Running OMP for the number of nonzeros in the deepest representation recovers its support, and the N.V.S. property constrains the support propagated to the preceding layer.The proof then bounds propagated error using the Stripe RIP and a coherence-based bound on its constant.Source: 2) Greedy case · pp. 17–18
  • The proof extends the recovery argument to any layer, yielding analogous layer-wise claims.Source: 2) Greedy case · p. 18

E. Discussion on Theorem 6 and Theorem 7

The discussion explains why the theorem assumptions can be met, sketches Algorithm 2 as a greedy approximation to projection, and gives a sparsity condition for the dictionaries.

E. Discussion on Theorem 6 and Theorem 7

  • Wavelet-based multi-layer overcomplete dictionaries can have mutual coherence on the order of 10^-3 and 10^-4, leaving room for representations that meet the theorem assumptions.The discussion also explains that the N.V.S. condition is needed for deterministic worst-case guarantees; with Gaussian coefficients, overlapping supports do not cancel with probability 1.Source: E. Discussion on Theorem 6 and Theorem 7 · p. 18

F. Projecting General Signals

  • Algorithm 2 greedily increases the deepest-layer sparsity constraint until a constraint is violated, then returns the preceding estimate rather than backtracking among support choices.Under stated assumptions, the method is a greedy approximation to an optimal algorithm.Source: F. Projecting General Signals · p. 18

G. Sparse Dictionaries

  • The sparse-dictionary lemma gives a sufficient condition: the deepest dictionary’s sparsity must be at most λ_L−1/(c_Lλ_L) for the preceding layer’s sparsity constraint to hold.The argument iterates this bound across the remaining layers.Source: G. Sparse Dictionaries · pp. 18–19
Loading 1708.08705v2…