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.

author list (cited authors)

  • Binev, P., & DeVore, R.

citation count

  • 59

publication date

  • April 2004