2013/12/19 by Marco Rossi, Rossi, Marco, Alexander M. Haimovich +3
Computer Science · Engineering · Mathematics · #Direction-of-Arrival Estimation Techniques #FOS: Computer and information sciences #FOS: Mathematics #Information Theory (cs.IT) #Optimization and Control (math.OC) #Radar Systems and Signal Processing #Sparse and Compressive Sensing Techniques #cs.IT #math.IT #math.OC
paper · pdf · doi:10.48550/arxiv.1312.5765
Submitted to IEEE Transaction on Signal Processing
openalex publication_date 2013/12/19 · arxiv created 2014/07/02 · arxiv updated 2014/07/03 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.