# Revisiting Matching Pursuit: Beyond Approximate Submodularity

arXiv: https://arxiv.org/abs/2305.07782 · HTML: https://mlsanity.com/paper/2305.07782/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 8 of its 41 references that are in the map.
- First posted on arXiv 12 May 2023.

## Builds on (most cited first, 8 of 8)

- [Distributed Submodular Maximization](https://mlsanity.com/paper/1411.0541/) (2014)
- [Submodularity in Action: From Machine Learning to Signal Processing Applications](https://mlsanity.com/paper/2006.09905/) (2020)
- [Multi-Objective Maximization of Monotone Submodular Functions with Cardinality Constraint](https://mlsanity.com/paper/1711.06428/) (2017)
- [Near-Optimal Sparse Sensing for Gaussian Detection with Correlated Observations](https://mlsanity.com/paper/1710.09676/) (2017)
- [Adaptive matching pursuit for off-grid compressed sensing](https://mlsanity.com/paper/1308.4273/) (2013)
- [Efficient Algorithms for Non-convex Isotonic Regression through Submodular Optimization](https://mlsanity.com/paper/1707.09157/) (2017)
- [Sparse Antenna and Pulse Placement for Colocated MIMO Radar](https://mlsanity.com/paper/1805.10641/) (2018)
- [Basis Pursuit Denoise with Nonsmooth Constraints](https://mlsanity.com/paper/1811.11633/) (2018)

## Abstract (arXiv)

We study the problem of selecting a subset of vectors from a large set, to obtain the best signal representation over a family of functions. Although greedy methods have been widely used for tackling this problem and many of those have been analyzed under the lens of (weak) submodularity, none of these algorithms are explicitly devised using such a functional property. Here, we revisit the vector-selection problem and introduce a function which is shown to be submodular in expectation. This function does not only guarantee near-optimality through a greedy algorithm in expectation, but also alleviates the existing deficiencies in commonly used matching pursuit (MP) algorithms. We further show the relation between the single-point-estimate version of the proposed greedy algorithm and MP variants. Our theoretical results are supported by numerical experiments for the angle of arrival estimation problem, a typical signal representation task; the experiments demonstrate the benefits of the proposed method with respect to the traditional MP algorithms.