Working Locally Thinking Globally: Theoretical Guarantees for Convolutional Sparse Coding

Abstract

The celebrated sparse representation model has led to remarkable results in various signal processing tasks in the last decade. However, despite its initial purpose of serving as a global prior for entire signals, it has been commonly used for modeling low dimensional patches due to the computational constraints it entails when deployed with learned dictionaries. A way around this problem has been recently proposed, adopting a convolutional sparse representation model. This approach assumes that the global dictionary is a concatenation of banded Circulant matrices. While several works have presented algorithmic solutions to the global pursuit problem under this new model, very few truly-effective guarantees are known for the success of such methods. In this work, we address the theoretical aspects of the convolutional sparse model providing the first meaningful answers to questions of uniqueness of solutions and success of pursuit algorithms, both greedy and convex relaxations, in ideal and noisy regimes. To this end, we generalize mathematical quantities, such as the ${\ell }_0$ norm, mutual coherence, Spark and RIP to their counterparts in the convolutional setting, intrinsically capturing local measures of the global model. On the algorithmic side, we demonstrate how to solve the global pursuit problem by using simple local processing, thus offering a first of its kind bridge between global modeling of signals and their patch-based local treatment.

This is the journal version of arXiv:1607.02005 and arXiv:1607.02009, accepted to IEEE Transactions on Signal Processing

References in corpus (4)

• Image Deblurring and Super-resolution by Adaptive Sparse Domain Selection and Adaptive Regularization
• Optimization Methods for Convolutional Sparse Coding
• Convolutional Matching Pursuit and Dictionary Training
• Convolutional Dictionary Learning through Tensor Factorization

Cited by in corpus (24)

• The Modern Mathematics of Deep Learning
• Multi-Layer Convolutional Sparse Modeling: Pursuit and Dictionary Learning
• First and Second Order Methods for Online Convolutional Dictionary Learning
• Convolutional Neural Networks Analyzed via Convolutional Sparse Coding
• Dictionary Learning with Convolutional Structure for Seismic Data Denoising and Interpolation
• Learning Filter Bank Sparsifying Transforms
• Efficient ADMM-based Algorithms for Convolutional Sparse Coding
• Working Locally Thinking Globally - Part II: Stability and Algorithms for Convolutional Sparse Coding
• A convolutional plane wave model for sound field reconstruction
• Convolutional Sparse Coding Fast Approximation with Application to Seismic Reflectivity Estimation
• A Bayesian Perspective of Convolutional Neural Networks through a Deconvolutional Generative Model
• Convolutional Sparse Coding with Overlapping Group Norms
• Adversarial Robustness of Supervised Sparse Coding
• A Local Block Coordinate Descent Algorithm for the Convolutional Sparse Coding Model
• Convolutional Neural Networks Analyzed via Inverse Problem Theory and Sparse Representations
• Convolutional-Sparse-Coded Dynamic Mode Decomposition and Its Application to River State Estimation
• CRNet: Image Super-Resolution Using A Convolutional Sparse Coding Inspired Network
• Deeply-Sparse Signal rePresentations ($\text{D}{\text{S}}^2\text{P}$)
• Learning Deep Analysis Dictionaries -- Part II: Convolutional Dictionaries
• Towards Understanding Residual and Dilated Dense Neural Networks via Convolutional Sparse Coding
• Towards an understanding of CNNs: analysing the recovery of activation pathways via Deep Convolutional Sparse Coding
• Variations on the CSC model
• Convolutional Dictionary Learning in Hierarchical Networks
• Improved Image Generation via Sparse Modeling