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 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. 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 , 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
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 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 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 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 (, section 2) for details regarding this properties.
Convolutional sparse coding model 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 .
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 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) 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
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. 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
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: