Convolutional sparse coding
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 formula_1 as a linear combination of a few atoms in the redundant dictionary formula_2, usually expressed as formula_3 for a sparse vector formula_4, 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 formula_5 are generated by "local" dictionaries operating over stripes of formula_6. 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. Given a signal of interest formula_1 and a redundant dictionary formula_2, the sparse coding problem consist of retrieving a sparse vector formula_4, denominated the sparse representation of formula_5, such  that formula_11. Intuitively, this implies formula_5 is expressed as a linear combination of a small number of elements in formula_13. 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. It has been of particular interest for image understanding and computer vision tasks involving natural images, allowing redundant dictionaries to be efficiently inferred 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. Interestingly, by imposing  a local sparsity prior in formula_6, meaning that its independent patches can be interpreted as sparse vectors themselves, the structure in formula_13 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 formula_6 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 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. 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. 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. Allow signal formula_17 to be expressed as a linear combination of a small number of atoms from a given dictionary formula_18. Alternatively, the signal can be expressed as formula_3, where formula_20 corresponds to the sparse representation of formula_5, which selects the atoms  to combine and their weights. Subsequently, given formula_13, the task of recovering formula_6 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: formula_24 The effect of the formula_25 norm is to favor solutions with as much zero elements as possible. Furthermore, given an observation affected by bounded energy noise: formula_26, the pursuit problem is reformulated as: formula_27 Stability and uniqueness guarantees for the global sparse model. Let the "spark" of formula_28 be defined as the minimum number of linearly independent columns: formula_29 Then , from the triangular inequality, the sparsest vector formula_6 satisfies: formula_31. 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 formula_13. Assuming formula_33-norm unit atoms, the mutual coherence of formula_13 is defined as: formula_35, where formula_36 are atoms. Based on this metric, it can be proven that the true sparse representation formula_37 can be recovered if and only if formula_38. Similarly, under the presence of noise, an upper bound for the distance between the true sparse representation formula_39 and its estimation  formula_40 can be established via the restricted isometry property (RIP). A k-RIP matrix formula_13 with constant formula_42 corresponds to: formula_43, where formula_44 is the smallest number that satisfies the inequality for every formula_45. Then, assuming formula_46, it is guaranteed that formula_47. Solving such a general pursuit problem is a hard task if no structure is imposed on dictionary formula_13. 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 formula_5, typically based on prior information, formula_37 can be estimated via  several pursuit algorithms. Pursuit algorithms for the global sparse model. 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 formula_5 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 formula_40. To overcome this, additional priors are imposed over formula_13 to guarantee tighter bounds and uniqueness conditions. The reader is referred to (, section 2) for details regarding this properties. Convolutional sparse coding model. A local prior is adopted such that each overlapping section of formula_6 is sparse. Let formula_55 be constructed from shifted versions of a local dictionary formula_56. Then, formula_5 is formed by products between formula_58 and local patches of formula_59. From the latter, formula_6 can be re-expressed by formula_61 disjoint sparse vectors formula_62: formula_63. Similarly, let formula_64 be a set of formula_65 consecutive vectors formula_66. Then , each disjoint segment in formula_5 is expressed as: formula_68, where operator formula_69 extracts overlapping patches of size formula_70 starting at index formula_71. Thus, formula_72 contains only formula_73 nonzero columns. Hence, by introducing operator formula_74 which exclusively preserves them: formula_75 where formula_76 is known as the stripe dictionary, which is independent of formula_71, and formula_78 is denominated the i-th stripe. So, formula_5 corresponds to a patch aggregation or convolutional interpretation: formula_80 Where formula_36 corresponds to the i-th atom from the local dictionary formula_82 and formula_83 is constructed by elements of patches formula_84: formula_85. Given the new dictionary structure, let  the formula_86 pseudo-norm be defined as: formula_87. Then, for the noise-free and noise-corrupted scenarios, the problem can be respectively reformulated as: formula_88 Stability and uniqueness guarantees for the convolutional sparse model. For the local approach, formula_13 mutual coherence satisfies: formula_90 So, if a solution obeys formula_91, then it is the sparsest solution to the formula_86 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) for splitting the pursuit into smaller problems. Based on the formula_86 pseudonorm, if a solution formula_6 exists satisfying formula_95, then both methods are guaranteed to recover it. Moreover, the local model guarantees recovery independently of the signal dimension, as opposed to the formula_25 prior. Stability conditions for OMP and BP are also guaranteed if its exact recovery condition (ERC) is met for a support formula_97 with a constant formula_98. The ERC is defined as: formula_99, where formula_100 denotes the Pseudo-inverse. Algorithm 1 shows the Global Pursuit method based on ISTA. Algorithm 1: 1D  CSC via local iterative soft-thresholding. "Input:" formula_82: Local Dictionary, formula_102: observation, formula_103: Regularization parameter, formula_104: step size for codice_1, codice_2: tolerance factor, codice_3: maximum number of iterations. Repeat Until formula_113 codice_2 or formula_114 codice_3. Multi-layered convolutional sparse coding model. By imposing the sparsity prior in the inherent structure of formula_5, 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  this criteria, yet another extension denominated mlti-layer convolutional sparse coding (ML-CSC) is proposed. A set of analytical dictionaries formula_116 can be efficiently designed, where sparse representations at each layer formula_117 are guaranteed by imposing the sparsity prior over the dictionaries themselves. In other words, by considering dictionaries to be stride convolutional matrices i.e. atoms of the local dictionaries shift formula_118 elements instead of a single one, where formula_118 corresponds to the number of channels in the previous layer, it is guaranteed that the formula_120 norm of the representations along layers is bounded. For example, given the dictionaries formula_121 , the signal is modeled as formula_122, where formula_123 is its sparse code, and formula_124 is the sparse code of formula_123. Then, the estimation of each representation is formulated as an optimization problem for both noise-free and noise-corrupted scenarios, respectively. Assuming formula_126: formula_127 In what follows, theoretical guarantees for the uniqueness and stability of this extended model are described. Theorem 1: (Uniqueness of sparse representations) Consider signal formula_5 satisfies the (ML-CSC) model for a set of convolutional dictionaries formula_129 with mutual coherence formula_130. If the true sparse representations satisfy formula_131, then a solution to the problem formula_132 will  be its unique solution if the thresholds are chosen to satisfy: formula_133. Theorem 2: (Global stability of the noise-corrupted scenario) Consider signal formula_5 satisfies the (ML-CSC) model for a set of convolutional dictionaries formula_129 is contaminated with noise formula_136, where formula_137. resulting in formula_138. If formula_139 and formula_140, then the estimated representations formula_141 satisfy the following: formula_142. Projection-based algorithms. As a simple approach for solving the ML-CSC problem, either via the formula_25 or formula_144 norms, is by computing inner products between formula_5 and the dictionary atoms to identify the most representatives ones. Such a projection is  described as: formula_146 which have closed-form solutions via the hard-thresholding formula_147 and soft-thresholding algorithms formula_148, respectively. If a nonnegative constraint is also contemplated, the problem can be expressed via the formula_144 norm as: formula_150 which closed-form solution corresponds to the soft nonnegative thresholding operator formula_151, where formula_152. 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 formula_5 that satisfies the (ML-CSC) model for a set of convolutional dictionaries formula_154 with mutual coherence formula_155 is contaminated with noise  formula_136, where formula_157. resulting in formula_138. Denote by formula_159 and formula_160 the lowest and highest entries in formula_161. Let formula_162 be the estimated sparse representations obtained for formula_163. If formula_164 and formula_165 is chosen according to: formula_166 Then, formula_167 has the same support as formula_168, and formula_169, for formula_170 Connections to convolutional neural networks. Recall the forward pass of the convolutional neural network model, used in both training and inference steps. Let formula_171 be its input and formula_172 the filters at layer formula_173, which are followed by the rectified linear unit (RLU) formula_174, for bias formula_175. Based on this elementary  block, taking formula_176 as example, the CNN output can be expressed as: formula_177 Finally, comparing the CNN algorithm and the Layered thresholding approach for the nonnegative , it is straightforward to show that both are equivalent: formula_178 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 (, section 5) for details regarding their connection. Pursuit algorithms for the multi-layer CSC model. 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 formula_144 ball, the following problem is proposed: formula_180 where each layer is solved as an independent CSC problem, and formula_181  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 formula_5 characterized by a set of sparse vectors formula_141, convolutional dictionaries formula_129 and their corresponding mutual coherences formula_185. If formula_186, then the LBP algorithm is guaranteed to recover the sparse representations. Theorem 5: (Stability in the presence of noise) Consider the contaminated signal formula_187, where formula_188 and formula_5 is characterized by a set of sparse  vectors formula_141 and convolutional dictionaries formula_129. Let formula_192 be solutions obtained via the LBP algorithm with parameters formula_193. If formula_194 and formula_195, then: (i) The support of the solution formula_196 is contained in that of formula_168, (ii) formula_198, and (iii) Any entry greater in absolute value than formula_199 is guaranteed to be recovered. Applications of the convolutional sparse coding model: image inpainting. As a practical example, an efficient image inpainting method for color images via the CSC model is shown. Consider the three-channel dictionary formula_200, where formula_201 denotes the formula_118-th atom at channel formula_104, represents signal formula_5 by  a single cross-channel sparse representation formula_6, with stripes denoted as formula_206. Given an observation formula_207, where randomly chosen channels at unknown pixel locations are fixed to zero, in a similar way to impulse noise, the problem is formulated as: formula_208 By means of ADMM, the cost function is decoupled into simpler sub-problems, allowing an efficient formula_6 estimation. Algorithm 2 describes the procedure, where formula_210 is the DFT representation of formula_211, the convolutional matrix for the term formula_212. Likewise, formula_213 and formula_214 correspond to the DFT representations of formula_215 and formula_216, respectively, formula_217 corresponds to the Soft-thresholding function  with argument formula_218, and the formula_219 norm is defined as the formula_33 norm along the channel dimension formula_104 followed by the formula_144 norm along the spatial dimension formula_118. The reader is referred to (, 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:" formula_224: DFT of convolutional matrices formula_225, formula_226: Color observation, formula_103: Regularization parameter, formula_228: step sizes for codice_6, codice_2: tolerance factor, codice_3: maximum number of iterations. Repeat Until formula_234codice_2 or formula_235 codice_3.