Near best tree approximation

R. G. Baraniuk, R. A. DeVore, G. Kyriazis, X. M. Yu

Research output: Contribution to journalArticlepeer-review

26 Scopus citations


Tree approximation is a form of nonlinear wavelet approximation that appears naturally in applications such as image compression and entropy encoding. The distinction between tree approximation and the more familiar n-term wavelet approximation is that the wavelets appearing in the approximant are required to align themselves in a certain connected tree structure. This makes their positions easy to encode. Previous work [4,6] has established upper bounds for the error of tree approximation for certain (Besov) classes of functions. This paper, in contrast, studies tree approximation of individual functions with the aim of characterizing those functions with a prescribed approximation error. We accomplish this in the case that the approximation error is measured in L2, or in the case p ≠ 2, in the Besov spaces Bp 0(Lp), which are close to (but not the same as) Lp. Our characterization of functions with a prescribed approximation order in these cases is given in terms of a certain maximal function applied to the wavelet coefficients.

Original languageEnglish (US)
Pages (from-to)357-373
Number of pages17
JournalAdvances in Computational Mathematics
Issue number4
StatePublished - 2002


  • Approximation classes
  • Compression
  • Encoding
  • n-term approximation

ASJC Scopus subject areas

  • Applied Mathematics
  • Computational Mathematics


Dive into the research topics of 'Near best tree approximation'. Together they form a unique fingerprint.

Cite this