Abstract: We propose a probabilistic extension of the matching pursuit adaptive signal processing algorithm introduced by Mallat and others. In adaptive signal processing, signals are expanded in terms of a large linearly dependent ``dictionary'' of functions rather than in terms of an orthonormal basis. Matching pursuit is a simple greedy algorithm for generating an expansion of a given signal. In probabilistic matching pursuit multiple random expansions are obtained as estimates for a given signal. The new algorithm is illustrated in the context of signal denoising. Although most of the random expansions generated by probabilistic matching pursuit are poorer estimates for the signal than those obtained by matching pursuit, our final estimate, obtained as an expected value computed by means of an ergodic average, can improve the result obtained by MP in some denoising situations. One of the major underlying ideas is a novel notion of coherence between a signal and the dictionary. Several simulated examples are presented.

Keywords: Matching pursuit, Gabor function dictionary, denoising, rejection sampling, Bernoulli shift.