  We present an algorithm, dubbed Multi-Branch Matching Pursuit (MBMP), to
solve the sparse recovery problem over redundant dictionaries. MBMP combines
three different paradigms: being a greedy method, it performs iterative signal
support estimation; as a rank-aware method, it is able to exploit signal
subspace information when multiple snapshots are available; and, as its name
foretells, it leverages a multi-branch (i.e., tree-search) strategy that allows
us to trade-off hardware complexity (e.g. measurements) for computational
complexity. We derive a sufficient condition under which MBMP can recover a
sparse signal from noiseless measurements. This condition, named MB-coherence,
is met when the dictionary is sufficiently incoherent. It incorporates the
number of branches of MBMP and it requires fewer measurements than other
conditions (e.g. the Neuman ERC or the cumulative coherence). As such,
successful recovery with MBMP is guaranteed for dictionaries that do not
satisfy previously known conditions.
