Blended Matching Pursuit
This work addresses optimization challenges in signal processing and machine learning for researchers and practitioners, offering an incremental improvement over existing matching pursuit methods.
The paper tackles the problem of minimizing smooth convex functions over linear spaces spanned by atoms by introducing a blended matching pursuit algorithm that combines coordinate descent and gradient descent steps, achieving sublinear to linear convergence rates and demonstrating computational superiority with fast convergence and wall-clock speed while maintaining sparsity comparable to orthogonal matching pursuit.
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.