Algorithm 820: A flexible implementation of matching pursuit for Gabor functions on the interval

ABSTRACT

In digital signal processing it is often advantageous to analyze a given signal using an adaptive method. The signal is approximated or represented as a superposition of "basic" waveforms chosen from a dictionary of such waveforms so as to best match the signal. The matching pursuit algorithm of Mallat and Zhang is such a method and is discussed in the context of discretized Gabor functions on an interval. We describe two software implementations based on these dictionaries. Both implementations rely on functions defined on an interval to avoid edge effects. One implementation allows for users to have great flexibility in the Gabor dictionary to be used. This is a useful improvement over other implementations, which only allow for a fixed dictionary. The other implementation takes advantage of the FFT algorithm and is faster. These implementations are written in C++, and can be used in practical applications.

REFERENCES

• 1: Chen, S. and Donoho, D. 1995. Atomic decomposition by basis pursuit. In SPIE International Conference on Wavelets (July). SPIE.
• 2: Scott Shaobing Chen , David L. Donoho , Michael A. Saunders, Atomic Decomposition by Basis Pursuit, SIAM Review, v.43 n.1, p.129-159, 2001 [doi>10.1137/S003614450037906X]
• 3: Cohen, A., Daubechies, I., and Vial, P. 1993. Wavelets on the interval and fast wavelet transforms. Applied and Computational Harmonic Analysis 1, 54--81.
• 4: Coifman, R. and Donoho, D. 1995. Translation invariant de-noising. Tech. Rep. 475, Statistics Department, Stanford University, California, 94305 USA.
• 5: Coifman, R. and Wickerhauser, V. 1992. Entropy-based algorithms for best basis selection. IEEE Trans. Info. Theory 38, 712--718.
• 6: Daubechies, I. 1990. The wavelet transform, time-frequency localization and signal analysis. IEEE Trans. Info. Theory 36, 5 (September), 961--1005.
• 7: Ingrid Daubechies, Ten lectures on wavelets, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1992
• 8: DeVore, R. and Temlyakov, V. 1996. Some remarks on greedy algorithms. Advances in Computational Mathematics 5, 173--187.
• 9: Jaggi, S. 1998. High resolution pursuit for feature extraction. J. Appl. Comput. Harmonic Analysis 5, 9, 428--439.
• 10: Kolasa, L., Ferrando, S., and Kovačević, N. 2000. C++Wavelets: A User's Guide. Included in distribution of Wave++, http://www.scs.ryerson.ca/∼lkolasa/CppWavelets.html.
• 11: Mallat, S. 1998. A Wavelet Tour of Signal Processing. Academic Press, Boston, MA.
• 12: Mallat, S. and Zhang, Z. 1993. Matching pursuit with time-frequency dictionaries. IEEE Trans. Signal Proc. 41, 12, 3397--3415.
• 13: Neff, R. and Zakhor, A. 1997. Very low bit-rate video coding based on matching pursuit. IEEE Trans. Circuit Syst. Video Tech. 7, 1 (February), 158--171.
• 14: Phillips, P. J. 1998. Matching pursuit filters applied to face identification. IEEE Trans. Image Proc. 7, 8 (August), 1150--1164.
• 15: Torrence, C. and Campo, G. P. 1998. A practical guide to wavelet analysis. Bulletin of the American Meteorological Society 79, 1 (January), 61--78.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.2 Approximation

Additional Classification:
  G. Mathematics of Computing
  G.4 MATHEMATICAL SOFTWARE

  I. Computing Methodologies
  I.4 IMAGE PROCESSING AND COMPUTER VISION
      I.4.5 Reconstruction
  I.5 PATTERN RECOGNITION
      I.5.4 Applications
          Subjects: Signal processing

General Terms:
Algorithms

Keywords:
Adaptive signal processing, Gabor analysis