  The recovery of signals that are sparse not in a basis, but rather sparse
with respect to an over-complete dictionary is one of the most flexible
settings in the field of compressed sensing with numerous applications. As in
the standard compressed sensing setting, it is possible that the signal can be
reconstructed efficiently from few, linear measurements, for example by the
so-called $\ell_1$-synthesis method.
  However, it has been less well-understood which measurement matrices provably
work for this setting. Whereas in the standard setting, it has been shown that
even certain heavy-tailed measurement matrices can be used in the same sample
complexity regime as Gaussian matrices, comparable results are only available
for the restrictive class of sub-Gaussian measurement vectors as far as the
recovery of dictionary-sparse signals via $\ell_1$-synthesis is concerned.
  In this work, we fill this gap and establish optimal guarantees for the
recovery of vectors that are (approximately) sparse with respect to a
dictionary via the $\ell_1$-synthesis method from linear, potentially noisy
measurements for a large class of random measurement matrices. In particular,
we show that random measurements that fulfill only a small-ball assumption and
a weak moment assumption, such as random vectors with i.i.d. Student-$t$
entries with a logarithmic number of degrees of freedom, lead to comparable
guarantees as (sub-)Gaussian measurements. Our results apply for a large class
of both random and deterministic dictionaries.
  As a corollary of our results, we also obtain a slight improvement on the
weakest assumption on a measurement matrix with i.i.d. rows sufficient for
uniform recovery in standard compressed sensing, improving on results by
Mendelson and Lecu\'e and Dirksen, Lecu\'e and Rauhut.
