  Greedy first-order methods, such as coordinate descent with Gauss-Southwell
rule or matching pursuit, have become popular in optimization due to their
natural tendency to propose sparse solutions and their refined convergence
guarantees. In this work, we propose a principled approach to generating
(regularized) matching pursuit algorithms adapted to the geometry of the
problem at hand, as well as their convergence guarantees. Building on these
results, we derive approximate convergence guarantees and describe a transition
phenomenon in the convergence of (regularized) matching pursuit from
underparametrized to overparametrized models.
