Tree Structure Search for Matching Pursuit

Matching pursuit has found many applications recently especially in very low bit rate video coding. In this paper we show how the complexity of matching pursuit can be reduced from $O(N)$ to $O(log(2N))$ using tree structured dictionaries. Moreover, we show how tree structured dictionaries provide an efficient coding strategy that is more resilient to error than random coding. Our simulation results showed an improvement of about 3dB in PSNR can be achieved using the code provided by the tree structured dictionary.