  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.
