Sharp Convergence Rates for Matching Pursuit

Matching pursuit [17] is a widely used algorithm in signal processing that approximates a target signal by selecting a sparse linear combination of elements from a given dictionary. Over the years, matching pursuit has garnered significant attention due to its effectiveness in capturing essential features of a signal with a parsimonious representation, offering reduced storage requirements, efficient signal reconstruction, and enhanced interpretability of the underlying signal structure. Because of this, its applications span various domains, including image, video, and audio processing and compression [2, 19]. While previous works have explored the convergence properties of matching pursuit, several open questions and challenges remain. In particular, the relationship between the characteristics of the target signal, the chosen dictionary, and the convergence rate warrants further investigation. The main objective of this paper is to provide a comprehensive analysis of the convergence properties of matching pursuit. Understanding the convergence rate is crucial for assessing the algorithm's efficiency and determining the number of iterations required to achieve a desired level of approximation accuracy. Let H be a Hilbert space and D H be a symmetric collection of unit vectors, i.e., d = 1 for d D and d D implies d D, called a dictionary.