# Blended Matching Pursuit

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 28 Apr 2019.

## Built on by (most cited first, 3 of 3)

- [Sparse Bayesian Learning via Stepwise Regression](https://mlsanity.com/paper/2106.06095/) (2021)
- [Scalable DC Optimization via Adaptive Frank-Wolfe Algorithms](https://mlsanity.com/paper/2507.17545/) (2025)
- [Approximate Frank-Wolfe Algorithms over Graph-structured Support Sets](https://mlsanity.com/paper/2107.00472/) (2021)

## Abstract (arXiv)

Matching pursuit algorithms are an important class of algorithms in signal processing and machine learning. We present a blended matching pursuit algorithm, combining coordinate descent-like steps with stronger gradient descent steps, for minimizing a smooth convex function over a linear space spanned by a set of atoms. We derive sublinear to linear convergence rates according to the smoothness and sharpness orders of the function and demonstrate computational superiority of our approach. In particular, we derive linear rates for a wide class of non-strongly convex functions, and we demonstrate in experiments that our algorithm enjoys very fast rates of convergence and wall-clock speed while maintaining a sparsity of iterates very comparable to that of the (much slower) orthogonal matching pursuit.