This paper studies the effect of discretizing the parametrization of a dictionary used for matching pursuit (MP) 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.
A similar approach to our geometric analysis of MP atom selection rule has been proposed in @cite_10 . In that paper, a dictionary of ( @math -normalized) wavelets is seen as a manifold associate to a Riemannian metric. However, the authors restrict their work to wavelet parametrization inherited from Lie group (such as the affine group). They also work only on the @math (dictionary) distance between dictionary atoms and do not introduce intrinsic geodesic distance. They define a discretization of the parametrization @math such that, in our notations, @math , with @math the local width of the cell localized on @math . There is however no analysis of the effect of this discretization on the MP rate of convergence.
@cite_10
1971186456
Abstract A new method of wavelet packet analysis is presented where the wavelet packets are chosen from a manifold rather than a discrete grid. A generalisation of the wavelet transform is defined on this manifold by correlation of the wavelet packets with the signal or image, and a discrete subset of the wavelet packets is then chosen from local maxima in the modulus of this function as a form of signal or image feature extraction. We show that consideration of the geometry of the manifold aids the search for these local maxima. We also show that the resulting wavelet characterisation is the best local approximation to the signal or image and represents signal and image components with the greatest signal to noise ratio, and is thus useful to surveillance and detection.