Timezone: »

Blended Matching Pursuit
Cyrille Combettes · Sebastian Pokutta

Tue Dec 10 05:30 PM -- 07:30 PM (PST) @ East Exhibition Hall B + C #105

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 large 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.

Author Information

Cyrille Combettes (Georgia Institute of Technology)
Sebastian Pokutta (Zuse Institute Berlin)

More from the Same Authors