Fast computation in adaptive tree approximation Academic Article uri icon


  • Adaptive methods of approximation arise in many settings including numerical methods for PDEs and image processing. They can usually be described by a tree which records the adaptive decisions. This paper is concerned with the fast computation of near optimal trees based on n adaptive decisions. The best tree based on n adaptive decisions could be found by examining all such possibilities. However, this is exponential in n and could be numerically prohibitive. The main result of this paper is to show that it is possible to find near optimal trees using computations linear in n.

published proceedings

  • Numerische Mathematik

author list (cited authors)

  • Binev, P., & DeVore, R.

citation count

  • 66

complete list of authors

  • Binev, Peter||DeVore, Ronald

publication date

  • April 2004