Fast computation in adaptive tree approximation

Summary. 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.Mathematics Subject Classification (2000): 65Y20, 65N50, 41A63, 41A15, 68W40, 68W25This work has been supported in part by the Office of Naval Research contracts 03-10051, (N00014-00-1-0470), the Army Research Office contract DAAD 19-02-1-0028, and the National Science Foundation grants DMS 9872890, DMS 0221642.