Ada Numerica (1998), pp. 51-150 © Cambridge University Press, 1998Nonlinear approximationRonald A. DeVore*Department of Mathematics,University of South Carolina,Columbia, SC 29208, USAE-mail: devoreOmath. sc. eduThis is a survey of nonlinear approximation, especially that part of the sub-ject which is important in numerical computation. Nonlinear approximationmeans that the approximants do not come from linear spaces but rather fromnonlinear manifolds. The central question to be studied is what, if any, are theadvantages of nonlinear approximation over the simpler, more established, lin-ear methods. This question is answered by studying the rate of approximationwhich is the decrease in error versus the number of parameters in the approx-imant. The number of parameters usually correlates well with computationaleffort. It is shown that in many settings the rate of nonlinear approximationcan be characterized by certain smoothness conditions which are significantlyweaker than required in the linear theory. Emphasis in the survey will beplaced on approximation by piecewise polynomials and wavelets as well astheir numerical implementation. Results on highly nonlinear methods suchas optimal basis selection and greedy algorithms (adaptive pursuit) are alsogiven. Applications to image processing, statistical estimation, regularity forPDEs, and adaptive algorithms are discussed.This research was supported by Office of Naval Research Contract N0014-91-J1343 andArmy Research Office Contract N00014-97-1-0806.52 R. A. DEVORECONTENTS1 Nonlinear approximation: an overview 522 Approximation in a Hilbert space 563 Approximation by piecewise constants 604 The elements of approximation theory 815 Nonlinear approximation in a Hilbert space:a second look 956 Piecewise polynomial approximation 967 Wavelets 1078 Highly nonlinear approximation 1219 Lower estimates for approximation: n-widths 13110 Applications of nonlinear approximation 135References 1461. Nonlinear approximation: an overviewThe fundamental problem of approximation theory is to resolve a possiblycomplicated function, called the target function, by simpler, easier to com-pute functions called the approximants. Increasing the resolution of thetarget function can generally only be achieved by increasing the complexityof the approximants. The understanding of this trade-off between resolutionand complexity is the main goal of constructive approximation. Thus thegoals of approximation theory and numerical computation are similar, eventhough approximation theory is less concerned with computational issues.The differing point in the two subjects lies in the information assumed tobe known about the target function. In approximation theory, one usuallyassumes that the values of certain simple linear functionals applied to thetarget function are known. This information is then used to construct anapproximant. In numerical computation, information usually comes in adifferent, less explicit form. For example, the target function may be thesolution to an integral equation or boundary value problem and the numer-ical analyst needs to translate this into more direct information about thetarget function. Nevertheless, the two subjects of approximation and com-putation are inexorably intertwined and it is impossible to understand fullythe possibilities in numerical computation without a good understanding ofthe elements of constructive approximation.It is noteworthy that the developments of approximation theory and nu-merical computation followed roughly the same line. The early methodsutilized approximation from finite-dimensional linear spaces. In the begin-ning, these were typically spaces of polynomials, both algebraic and trigono-metric. The fundamental problems concerning order of approximation weresolved in this setting (primarily by the Russian school of Bernstein, Cheby-NONLINEAR APPROXIMATION 53shev, and their mathematical descendants). Then, starting in the late 1950scame the development of piecewise polynomials and splines and their incor-poration into numerical computation. We have in mind the finite elementmethods (FEM) and their counterparts in other areas such as numericalquadrature, and statistical estimation.It was noted shortly thereafter that there was some advantage to be gainedby not limiting the approximations to come from linear spaces, and thereinemerged the beginnings of nonlinear approximation. Most notable in thisregard was the pioneering work of Birman and Solomyak (1967) on adapt-ive approximation. In this theory, the approximants are not restricted tocome from spaces of piecewise polynomials with a fixed partition; rather,the partition was allowed to depend on the target function. However, thenumber of pieces in the approximant is controlled. This provides a goodmatch with numerical computation since it often represents closely the costof computation (number of operations). In principle, the idea was simple:we should use a finer mesh where the target function is not very smooth(singular) and a coarser mesh where it is smooth. The paramount questionremained, however, as to just how we should measure this smoothness inorder to obtain definitive results.As is often the case, there came a scramble to understand the advantagesof this new form of computation (approximation) and, indeed, rather exoticspaces of functions were created (Brudnyi 1974, Bergh and Peetre 1974),to define these advantages. But to most, the theory that emerged seemedtoo much a tautology and the spaces were not easily understood in termsof classical smoothness (derivatives and differences). But then came theremarkable discovery of Petrushev (1988) (preceded by results of Brudnyi(1974) and Oswald (1980)) that the efficiency of nonlinear spline approxima-tion could be characterized (at least in one variable) by classical smoothness(Besov spaces). Thus the advantage of nonlinear approximation becamecrystal clear (as we shall explain later in this article).Another remarkable development came in the 1980s with the develop-ment of multilevel techniques. Thus, there were the roughly parallel devel-opments of multigrid theory for integral and differential equations, waveletanalysis in the vein of harmonic analysis and approximation theory, andmultiscale filterbanks in the context of image processing. From the view-point of approximation theory and harmonic analysis, the wavelet theorywas important on several counts. It gave simple and elegant unconditionalbases