  Known sparsity thresholds for basis pursuit to deliver the maximally sparse
solution of the compressed sensing recovery problem typically depend on the
dictionary's coherence. While the coherence is easy to compute, it can lead to
rather pessimistic thresholds as it captures only limited information about the
dictionary. In this paper, we show that viewing the dictionary as the
concatenation of two general sub-dictionaries leads to provably better sparsity
thresholds--that are explicit in the coherence parameters of the dictionary and
of the individual sub-dictionaries. Equivalently, our results can be
interpreted as sparsity thresholds for dictionaries that are unions of two
general (i.e., not necessarily orthonormal) sub-dictionaries.
