HomePage > Publications > A Geometrical Study of ...
A Geometrical Study of Matching Pursuit Parametrization
L. Jacques and C. De Vleeschouwer, Signal Processing, IEEE Transactions on [see also Acoustics, Speech, and Signal Processing, IEEE Transactions on], 2008, Vol. 56(7), pp. 2835-2848
This paper studies the effect of discretizing the parametrization of a dictionary used for Matching Pursuit
decompositions of signals. Our approach relies on viewing the continuously parametrized dictionary
as an embedded manifold in the signal space on which the tools of differential (Riemannian) geometry
can be applied. The main contribution of this paper is twofold. First, we prove that if a discrete dictionary
reaches a minimal density criterion, then the corresponding discrete MP (dMP) is equivalent in terms of
convergence to a weakened hypothetical continuous MP. Interestingly, the corresponding weakness factor
depends on a density measure of the discrete dictionary. Second, we show that the insertion of a simple
geometric gradient ascent optimization on the atom dMP selection maintains the previous comparison but
with a weakness factor at least two times closer to unity than without optimization. Finally, we present
numerical experiments confirming our theoretical predictions for decomposition of signals and images
on regular discretizations of dictionary parametrizations.
Keywords: Matching Pursuit, Riemannian geometry, Optimization, Convergence, Dictionary, Parametrization.
Documents: arXiv 0801.3372 preprint, related Technical Report, Matlab codes available here (for testing only)