Infoscience

Report

Tree-Based Pursuit

Building good sparse approximations of functions is one of the major themes in approximation theory. When applied to signals, images or any kind of data, it allows to deal with basic building blocks that essentially synthesize all the information at hand. It is known since the early successes of wavelet analysis that sparse expansions very often result in efficient algorithms for characterizing signals in noise or even for analyzing and compressing signals. The very strong links between approximation theory and computational harmonic analysis on one hand and data processing on the other hand, resulted in fruitful crossfertilizations over the last decade. This paper proposes to create a tree structure from an arbitrary dictionary of functions. Due to a hierarchical classification of the original data, an important part of the redundancy is intrinsically hold by the structure that represents whole bunch of highly correlated atoms by an unique element. A pursuit algorithm taking advantage of this structure is proposed. It consists in finding the best path through the tree. It presents the important advantage of being much faster than a classical Matching Pursuit. The proposed method reduces the dimensionality of the problems without losing important information for the problem at hand; it only minimally degrades the quality of approximation. The performance of the proposed algorithm are demonstrated in the context of image representation.

    Keywords: LTS2 ; LTS4

    Note:

    ITS

    Reference

    • EPFL-REPORT-87051

    Record created on 2006-06-14, modified on 2016-08-08

Related material