Matching Pursuit - The Algorithm

The Algorithm

Searching over an extremely large dictionary for the best matches is computationally unacceptable for practical applications. In 1993 Mallat and Zhang proposed a greedy solution that is known from that time as Matching Pursuit. The algorithm iteratively generates for any signal and any dictionary a sorted list of indexes and scalars which are sub-optimal solution to the problem of sparse signal representation. The residual after calculating and is denoted by .

Algorithm Matching Pursuit Input: Signal:, dictionary . Output: List of coefficients: . Initialization: ; ; Repeat: find with maximum inner product ; ; ; ; Until stop condition (for example: )

The concept of matching pursuit in signal processing is related to statistical projection pursuit, in which "interesting" projections were found; ones that deviate more from a normal distribution are considered to be more interesting.