Jump to content

Convolutional sparse coding

From Wikipedia, the free encyclopedia

The convolutional sparse coding paradigm is an extension of the global sparse coding model, in which a redundant dictionary is modeled as a concatenation of circulant matrices. While the global sparsity constraint describes signal as a linear combination of a few atoms in the redundant dictionary , usually expressed as for a sparse vector , the alternative dictionary structure adopted by the convolutional sparse coding model allows the sparsity prior to be applied locally instead of globally: independent patches of are generated by "local" dictionaries operating over stripes of .

The local sparsity constraint allows stronger uniqueness and stability conditions than the global sparsity prior, and has shown to be a versatile tool for inverse problems in fields such as image understanding and computer vision. Also, a recently proposed multi-layer extension of the model has shown conceptual benefits for more complex signal decompositions, as well as a tight connection the convolutional neural networks model, allowing a deeper understanding of how the latter operates.

Overview

[edit]

Given a signal of interest and a redundant dictionary , the sparse coding problem consist of retrieving a sparse vector , denominated the sparse representation of , such that . Intuitively, this implies is expressed as a linear combination of a small number of elements in . The global sparsity constraint prior has been shown to be useful in many ill-posed inverse problems such as image inpainting, super-resolution, and coding.[1][2][3] It has been of particular interest for image understanding and computer vision tasks involving natural images, allowing redundant dictionaries to be efficiently inferred [4][5][6]

As an extension to the global sparsity constraint, recent pieces in the literature have revisited the model to reach a more profound understanding of its uniqueness and stability conditions.[6] Interestingly, by imposing a local sparsity prior in , meaning that its independent patches can be interpreted as sparse vectors themselves, the structure in can be understood as a “local" dictionary operating over each independent patch. This model extension is denominated convolutional sparse coding (CSC) and drastically reduces the burden of estimating signal representations while being characterized by stronger uniqueness and stability conditions. Furthermore, it allows for to be efficiently estimated via projected gradient descent algorithms such as orthonormal matching pursuit (OMP) and basis pursuit (BP), while performing in a local fashion[5]

Besides its versatility in inverse problems, recent efforts have focused on the multi-layer version of the model and provided evidence of its reliability for recovering multiple underlying representations.[7] Moreover, a tight connection between such a model and the well-established convolutional neural network model (CNN) was revealed, providing a new tool for a more rigurous understanding of its theoretical conditions.

The convolutional sparse coding model provides a very efficient set of tools to solve a wide range of inverse problems, including image denoising, image inpainting, and image superresolution. By imposing local sparsity constraints, it allows to efficiently tackle the global coding problem by iteratively estimating disjoint patches and assembling them into a global signal. Furthermore, by adopting a multi-layer sparse model, which results from imposing the sparsity constraint to the signal inherent representations themselves, the resulting "layered" pursuit algorithm keeps the strong uniqueness and stability conditions from the single-layer model. This extension also provides some interesting notions about the relation between its sparsity prior and the forward pass of the convolutional neural network, which allows to understand how the theoretical benefits of the CSC model can provide a strong mathematical meaning of the CNN structure.

Sparse coding paradigm

[edit]

Basic concepts and models are presented to explain into detail the convolutional sparse representation framework. On the grounds that the sparsity constraint has been proposed under different models, a short description of them is presented to show its evolution up to the model of interest. Also included are the concepts of mutual coherence and restricted isometry property to establish uniqueness stability guarantees.

Global sparse coding model

[edit]

Allow signal to be expressed as a linear combination of a small number of atoms from a given dictionary . Alternatively, the signal can be expressed as , where corresponds to the sparse representation of , which selects the atoms to combine and their weights. Subsequently, given , the task of recovering from either the noise-free signal itself or an observation is denominated sparse coding. Considering the noise-free scenario, the coding problem is formulated as follows: The effect of the norm is to favor solutions with as much zero elements as possible. Furthermore, given an observation affected by bounded energy noise: , the pursuit problem is reformulated as:

Stability and uniqueness guarantees for the global sparse model

[edit]

Let the spark of be defined as the minimum number of linearly independent columns:

Then, from the triangular inequality, the sparsest vector satisfies: . Although the spark provides an upper bound, it is unfeasible to compute in practical scenarios. Instead, let the mutual coherence be a measure of similarity between atoms in . Assuming -norm unit atoms, the mutual coherence of is defined as: , where are atoms. Based on this metric, it can be proven that the true sparse representation can be recovered if and only if .

Similarly, under the presence of noise, an upper bound for the distance between the true sparse representation and its estimation can be established via the restricted isometry property (RIP). A k-RIP matrix with constant corresponds to: , where is the smallest number that satisfies the inequality for every . Then, assuming , it is guaranteed that .

Solving such a general pursuit problem is a hard task if no structure is imposed on dictionary . This implies learning large, highly overcomplete representations, which is extremely expensive. Assuming such a burden has been met and a representative dictionary has been obtained for a given signal , typically based on prior information, can be estimated via several pursuit algorithms.

Pursuit algorithms for the global sparse model

[edit]

Two basic methods for solving the global sparse coding problem are orthogonal matching pursuit (OMP) and basis pursuit (BP). OMP is a greedy algorithm that iteratively selects the atom best correlated with the residual between and a current estimation, followed by a projection onto a subset of pre-selected atoms. On the other hand, basis pursuit is a more sophisticated approach that replaces the original coding problem by a linear programming problem. Based on this algorithms, the global sparse coding provides considerably loose bounds for the uniqueness and stability of . To overcome this, additional priors are imposed over to guarantee tighter bounds and uniqueness conditions. The reader is referred to (,[5] section 2) for details regarding this properties.

Convolutional sparse coding model

[edit]

A local prior is adopted such that each overlapping section of is sparse. Let be constructed from shifted versions of a local dictionary . Then, is formed by products between and local patches of .

The global dictionary is expressed in terms of a stride convolutional matrix. So, signals can be generated in terms of stripes of the sparse representation multiplies by a shift-invariant local dictionary.

From the latter, can be re-expressed by disjoint sparse vectors : . Similarly, let be a set of consecutive vectors . Then, each disjoint segment in is expressed as: , where operator extracts overlapping patches of size starting at index . Thus, contains only nonzero columns. Hence, by introducing operator which exclusively preserves them: where is known as the stripe dictionary, which is independent of , and is denominated the i-th stripe. So, corresponds to a patch aggregation or convolutional interpretation: Where corresponds to the i-th atom from the local dictionary and is constructed by elements of patches : . Given the new dictionary structure, let the pseudo-norm be defined as: . Then, for the noise-free and noise-corrupted scenarios, the problem can be respectively reformulated as:

Stability and uniqueness guarantees for the convolutional sparse model

[edit]

For the local approach, mutual coherence satisfies: So, if a solution obeys , then it is the sparsest solution to the problem. Thus, under the local formulation, the same number of non-zeros is permitted for each stripe instead of the full vector!

Similar to the global model, the CSC is solved via OMP and BP methods, the latter contemplating the use of the iterative shrinkage thresholding algorithm (ISTA)[8] for splitting the pursuit into smaller problems. Based on the pseudonorm, if a solution exists satisfying , then both methods are guaranteed to recover it. Moreover, the local model guarantees recovery independently of the signal dimension, as opposed to the prior. Stability conditions for OMP and BP are also guaranteed if its exact recovery condition (ERC) is met for a support with a constant . The ERC is defined as: , where denotes the Pseudo-inverse. Algorithm 1 shows the Global Pursuit method based on ISTA.

Algorithm 1: 1D CSC via local iterative soft-thresholding.

Input:

: Local Dictionary,

: observation,

: Regularization parameter,

: step size for ISTA,

tol: tolerance factor,

maxiters: maximum number of iterations.

(Initialize disjoint patches.)
(Initialize residual patches.)

Repeat

(Coding along disjoint patches)
(Patch Aggregation)
(Update residuals)

Until tol or maxiters.

Multi-layered convolutional sparse coding model

[edit]

By imposing the sparsity prior in the inherent structure of , strong conditions for a unique representation and feasible methods for estimating it are granted. Similarly, such a constraint can be applied to its representation itself, generating a cascade of sparse representations: Each code is defined by a few atoms of a given set of convolutional dictionaries.

Based on these criteria, yet another extension denominated multi-layer convolutional sparse coding (ML-CSC) is proposed. A set of analytical dictionaries can be efficiently designed, where sparse representations at each layer are guaranteed by imposing the sparsity prior over the dictionaries themselves.[7] In other words, by considering dictionaries to be stride convolutional matrices i.e. atoms of the local dictionaries shift elements instead of a single one, where corresponds to the number of channels in the previous layer, it is guaranteed that the norm of the representations along layers is bounded.

For example, given the dictionaries , the signal is modeled as , where is its sparse code, and is the sparse code of . Then, the estimation of each representation is formulated as an optimization problem for both noise-free and noise-corrupted scenarios, respectively. Assuming :

In what follows, theoretical guarantees for the uniqueness and stability of this extended model are described.

Theorem 1: (Uniqueness of sparse representations) Consider signal satisfies the (ML-CSC) model for a set of convolutional dictionaries with mutual coherence . If the true sparse representations satisfy , then a solution to the problem will be its unique solution if the thresholds are chosen to satisfy: .

Theorem 2: (Global stability of the noise-corrupted scenario) Consider signal satisfies the (ML-CSC) model for a set of convolutional dictionaries is contaminated with noise , where . resulting in . If and , then the estimated representations satisfy the following: .

Projection-based algorithms

[edit]

As a simple approach for solving the ML-CSC problem, either via the or norms, is by computing inner products between and the dictionary atoms to identify the most representatives ones. Such a projection is described as:

which have closed-form solutions via the hard-thresholding and soft-thresholding algorithms , respectively. If a nonnegative constraint is also contemplated, the problem can be expressed via the norm as: which closed-form solution corresponds to the soft nonnegative thresholding operator , where . Guarantees for the Layered soft-thresholding approach are included in the Appendix (Section 6.2).

Theorem 3: (Stable recovery of the multi-layered soft-thresholding algorithm) Consider signal that satisfies the (ML-CSC) model for a set of convolutional dictionaries with mutual coherence is contaminated with noise , where . resulting in . Denote by and the lowest and highest entries in . Let be the estimated sparse representations obtained for . If and is chosen according to: Then, has the same support as , and , for

Connections to convolutional neural networks

[edit]

Recall the forward pass of the convolutional neural network model, used in both training and inference steps. Let be its input and the filters at layer , which are followed by the rectified linear unit (RLU) , for bias . Based on this elementary block, taking as example, the CNN output can be expressed as: Finally, comparing the CNN algorithm and the Layered thresholding approach for the nonnegative constraint, it is straightforward to show that both are equivalent:

Convolutional Layers from the Forward Pass Algorithm
Contrast between the rectified linear unit function and the nonnegative soft thresholding pointwise nonlinearities

As explained in what follows, this naive approach of solving the coding problem is a particular case of a more stable projected gradient descent algorithm for the ML-CSC model. Equipped with the stability conditions of both approaches, a more clear understanding about the class of signals a CNN can recover, under what noise conditions can an estimation be accurately attained, and how can its structure be modified to improve its theoretical conditions. The reader is referred to (,[7] section 5) for details regarding their connection.

Pursuit algorithms for the multi-layer CSC model

[edit]

A crucial limitation of the forward pass is it being unable to recover the unique solution of the DCP problem, which existence has been demonstrated. So, instead of using a thresholding approach at each layer, a full pursuit method is adopted, denominated layered basis pursuit (LBP). Considering the projection onto the ball, the following problem is proposed: where each layer is solved as an independent CSC problem, and is proportional to the noise level at each layer. Among the methods for solving the layered coding problem, ISTA is an efficient decoupling alternative. In what follows, a short summary of the guarantees for the LBP are established.

Theorem 4: (Recovery guarantee) Consider a signal characterized by a set of sparse vectors , convolutional dictionaries and their corresponding mutual coherences . If , then the LBP algorithm is guaranteed to recover the sparse representations.

Theorem 5: (Stability in the presence of noise) Consider the contaminated signal , where and is characterized by a set of sparse vectors and convolutional dictionaries . Let be solutions obtained via the LBP algorithm with parameters . If and , then: (i) The support of the solution is contained in that of , (ii) , and (iii) Any entry greater in absolute value than is guaranteed to be recovered.

Applications of the convolutional sparse coding model: image inpainting

[edit]

As a practical example, an efficient image inpainting method for color images via the CSC model is shown.[6] Consider the three-channel dictionary , where denotes the -th atom at channel , represents signal by a single cross-channel sparse representation , with stripes denoted as . Given an observation , where randomly chosen channels at unknown pixel locations are fixed to zero, in a similar way to impulse noise, the problem is formulated as: By means of ADMM,[9] the cost function is decoupled into simpler sub-problems, allowing an efficient estimation. Algorithm 2 describes the procedure, where is the DFT representation of , the convolutional matrix for the term . Likewise, and correspond to the DFT representations of and , respectively, corresponds to the Soft-thresholding function with argument , and the norm is defined as the norm along the channel dimension followed by the norm along the spatial dimension . The reader is referred to (,[6] Section II) for details on the ADMM implementation and the dictionary learning procedure.

Algorithm 2: Color image inpainting via the convolutional sparse coding model.

Input:

: DFT of convolutional matrices ,

: Color observation,

: Regularization parameter,

: step sizes for ADMM,

tol: tolerance factor,

maxiters: maximum number of iterations.

Repeat

Until tol or maxiters.

References

[edit]
  1. ^ Jianchao Yang; Wright, John; Huang, Thomas S; Yi Ma (November 2010). "Image Super-Resolution Via Sparse Representation". IEEE Transactions on Image Processing. 19 (11): 2861–2873. Bibcode:2010ITIP...19.2861Y. doi:10.1109/TIP.2010.2050625. PMID 20483687. S2CID 8187730.
  2. ^ Wetzstein, Gordon; Heidrich, Wolfgang; Heide, Felix (2015). "Fast and Flexible Convolutional Sparse Coding": 5135–5143. {{cite journal}}: Cite journal requires |journal= (help)
  3. ^ Wohlberg, Brendt (2017). "SPORCO: A Python package for standard and convolutional sparse representations". Proceedings of the 16th Python in Science Conference. pp. 1–8. doi:10.25080/shinma-7f4c6e7-001.
  4. ^ Mairal, Julien; Bach, Francis; Ponce, Jean; Sapiro, Guillermo (2009). "Online dictionary learning for sparse coding". Proceedings of the 26th Annual International Conference on Machine Learning. ACM. pp. 689–696. doi:10.1145/1553374.1553463. hdl:11299/180118. ISBN 9781605585161. S2CID 7027533.
  5. ^ a b c Papyan, Vardan; Sulam, Jeremias; Elad, Michael (1 November 2017). "Working Locally Thinking Globally: Theoretical Guarantees for Convolutional Sparse Coding". IEEE Transactions on Signal Processing. 65 (21): 5687–5701. arXiv:1707.06066. Bibcode:2017ITSP...65.5687P. doi:10.1109/TSP.2017.2733447. S2CID 11214580.
  6. ^ a b c d Wohlberg, Brendt (6–8 March 2016). "Convolutional sparse representation of color images". 2016 IEEE Southwest Symposium on Image Analysis and Interpretation (SSIAI). pp. 57–60. doi:10.1109/SSIAI.2016.7459174. ISBN 978-1-4673-9919-7. S2CID 9923572.
  7. ^ a b c Papyan, Vardan; Romano, Yaniv; Elad, Michael (2017). "Convolutional Neural Networks Analyzed via Convolutional Sparse Coding". J. Mach. Learn. Res. 18 (1): 2887–2938. arXiv:1607.08194. Bibcode:2016arXiv160708194P. ISSN 1532-4435.
  8. ^ Beck, Amir; Teboulle, Marc (January 2009). "A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems". SIAM Journal on Imaging Sciences. 2 (1): 183–202. doi:10.1137/080716542. S2CID 3072879.
  9. ^ Boyd, Stephen (2010). "Distributed Optimization and Statistical Learning via the Alternating Direction Method of Multipliers". Foundations and Trends in Machine Learning. 3 (1): 1–122. CiteSeerX 10.1.1.360.1664. doi:10.1561/2200000016. ISSN 1935-8237. S2CID 51789432.
[edit]