  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.
