  Signal recovery from a given set of linear measurements using a sparsity
prior has been a major subject of research in recent years. In this model, the
signal is assumed to have a sparse representation under a given dictionary.
Most of the work dealing with this subject has focused on the reconstruction of
the signal's representation as the means for recovering the signal itself. This
approach forced the dictionary to be of low coherence and with no linear
dependencies between its columns. Recently, a series of contributions that
focus on signal recovery using the analysis model find that linear dependencies
in the analysis dictionary are in fact permitted and beneficial. In this paper
we show theoretically that the same holds also for signal recovery in the
synthesis case for the l0- synthesis minimization problem. In addition, we
demonstrate empirically the relevance of our conclusions for recovering the
signal using an l1-relaxation.
