Hostname: page-component-586b7cd67f-g8jcs Total loading time: 0 Render date: 2024-11-27T11:27:25.395Z Has data issue: false hasContentIssue false
  • English
  • Français

Nonlinear approximation

Published online by Cambridge University Press:  07 November 2008

Ronald A. DeVore
Ronald A. DeVore
Affiliation:
Department of Mathematics, University of South Carolina, Columbia, SC 29208, USA E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

This is a survey of nonlinear approximation, especially that part of the subject which is important in numerical computation. Nonlinear approximation means that the approximants do not come from linear spaces but rather from nonlinear manifolds. The central question to be studied is what, if any, are the advantages of nonlinear approximation over the simpler, more established, linear methods. This question is answered by studying the rate of approximation which is the decrease in error versus the number of parameters in the approximant. The number of parameters usually correlates well with computational effort. It is shown that in many settings the rate of nonlinear approximation can be characterized by certain smoothness conditions which are significantly weaker than required in the linear theory. Emphasis in the survey will be placed on approximation by piecewise polynomials and wavelets as well as their numerical implementation. Results on highly nonlinear methods such as optimal basis selection and greedy algorithms (adaptive pursuit) are also given. Applications to image processing, statistical estimation, regularity for PDEs, and adaptive algorithms are discussed.

Type
Research Article
Information
Acta Numerica , Volume 7 , January 1998 , pp. 51 - 150
Copyright
Copyright © Cambridge University Press 1998

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

Adams, R. A. (1975), Sobolev Spaces, Academic Press, New York.Google Scholar
Babuška, I. and Suri, M. (1994), ‘The p and h versions of the finite element method: basic principles and properties’, SIAM Review 36, 578–632.CrossRefGoogle Scholar
Baker, G. A. Jr (1975), Essentials of Padé Approximants, Academic Press, New York.Google Scholar
Bennett, C. and Sharpley, R. (1988), Interpolation of Operators, Academic Press, New York.Google Scholar
Bergh, J. and Löfström, J. (1976), Interpolation Spaces: An Introduction, Springer, Berlin.CrossRefGoogle Scholar
Bergh, J. and Peetre, J. (1974), ‘On the spaces Vp (0 < p ≤ ∞)’, Boll. Unione Mat. Ital. 10, 632–648.Google Scholar
Birman, M. and Solomyak, M. (1967), ‘Piecewise polynomial approximation of functions of the class Wagrp’, Mat. Sbornik 2, 295–317.CrossRefGoogle Scholar
de Boor, C. (1973), ‘Good approximation by splines with variable knots’, in Spline Functions and Approximation (Meir, A. and Sharma, A., eds), Birkhäuser, Basel, pp. 57–72.CrossRefGoogle Scholar
de Boor, C., DeVore, R. and Ron, A. (1993), ‘Approximation from shift invariant spaces’, Trans. Amer. Math. Soc. 341, 787–806.Google Scholar
Brown, L. and Lucier, B. (1994), ‘Best approximations in L 1 are best in Lp, p < 1, too’, Proc. Amer. Math. Soc. 120, 97–100.Google Scholar
Brudnyi, Yu. (1974), ‘Spline approximation of functions of bounded variation’, Soviet Math. Dokl. 15, 518–521.Google Scholar
Calderón, A. P. (1964a), ‘Intermediate spaces and interpolation: the complex method’, Studia Math. 24, 113–190.CrossRefGoogle Scholar
Calderón, A. P. (1964b), ‘Spaces between L 1 and L ∞ and the theorem of Marcinkieiwicz: the complex method’, Studia Math. 26, 273–279.Google Scholar
Chambolle, A., DeVore, R., Lee, N.-Y. and Lucier, B. (1998), ‘Nonlinear wavelet image processing: Variational problems, compression, and noise removal through wavelet shrinkage’, IEEE Trans. Image Processing 7, 319–335.CrossRefGoogle Scholar
Cohen, A., Daubechies, I. and Feauveau, J.-C. (1992), ‘Biorthogonal bases of compactly supported wavelets’, Comm. Pure Appl. Math. 43, 485–560.CrossRefGoogle Scholar
Cohen, A., Daubechies, I. and Vial, P. (1993), ‘Wavelets on the interval and fast wavelet transforms’, Appl. Comput. Harm. Anal. 1, 54–81.CrossRefGoogle Scholar
Cohen, A., Daubechies, I., Guleryuz, O. and Orchard, M. (1997), ‘On the importance of combining wavelet-based non-linear approximation in coding strategies’. Preprint.Google Scholar
Cohen, A., DeVore, R. and Hochmuth, R. (1997), ‘Restricted approximation’. Preprint.Google Scholar
Cohen, A., DeVore, R., Petrushev, P. and Xu, H. (1998), ‘Nonlinear approximation and the space BV(ℝ2)’. Preprint.Google Scholar
Coifman, R. R. and Donoho, D. (1995) Translation invariant de-noising, in Wavelets in Statistics (Antoniadis, A. and Oppenheim, G., eds), Springer, New York, pp. 125–150.CrossRefGoogle Scholar
Coifman, R. R. and Wickerhauser, M. V. (1992), ‘Entropy based algorithms for best basis selection’, IEEE Trans. Inform. Theory 32, 712–718.Google Scholar
Dahlke, S. and DeVore, R. (1997), ‘Besov regularity for elliptic boundary value problems’, Commun. Partial Diff. Eqns. 22, 1–16.Google Scholar
Dahlke, S., Dahmen, W. and DeVore, R. (1997), Nonlinear approximation and adaptive techniques for solving elliptic operator equations, in Multiscale Wavelet Methods for PDEs (Dahmen, W., Kurdila, A. and Oswald, P., eds), Academic Press, pp. 237–284.Google Scholar
Dahmen, W. (1997), Wavelet and multiscale methods for operator equations, in Acta Numerica, Vol. 6, Cambridge University Press, pp. 55–228.Google Scholar
Daubechies, I. (1988), ‘Orthonormal bases of compactly supported wavelets’, Comm. Pure Appl. Math. 41, 909–996.CrossRefGoogle Scholar
Daubechies, I. (1992), Ten Lectures on Wavelets, Vol. 61 of CBMS-NSF Regional Conference Series in Applied Mathematics, SIAM, Philadelphia.CrossRefGoogle Scholar
Davis, G., Mallat, S. and Avellaneda, M. (1997), ‘Adaptive greedy approximations’, Constr. Approx. 13, 57–98.CrossRefGoogle Scholar
DeVore, R. A. (1987), ‘A note on adaptive approximation’, Approx. Theory Appl. 3, 74–78.Google Scholar
DeVore, R. A. and Lorentz, G. G. (1993), Constructive Approximation, Vol. 303 of Grundlehren, Springer, Heidelberg.CrossRefGoogle Scholar
DeVore, R. A. and Lucier, B. (1990), ‘High order regularity for conservation laws’, Indiana Math. J. 39, 413–430.CrossRefGoogle Scholar
DeVore, R. A. and Lucier, B. (1992), Wavelets, in Acta Numerica, Vol. 1, Cambridge University Press, pp. 1–56.Google Scholar
DeVore, R. A. and Lucier, B. (1996), ‘On the size and smoothness of solutions to nonlinear hyperbolic conservation laws’, SIAM J. Math. Anal. 27, 684–707.CrossRefGoogle Scholar
DeVore, R. and Popov, V. (1987), ‘Free multivariate splines’, Constr. Approx. 3, 239–248.CrossRefGoogle Scholar
DeVore, R. and Popov, V. (1988a), ‘Interpolation of Besov spaces’, Trans. Amer. Math. Soc. 305, 397–414.CrossRefGoogle Scholar
DeVore, R. A. and Popov, V. A. (1988b), Interpolation spaces and nonlinear approximation, in Function Spaces and Applications (Cwikel, M. et al. , eds), Vol. 1302 of Lecture Notes in Mathematics, Springer, Berlin, pp. 191–205.CrossRefGoogle Scholar
DeVore, R. A. and Scherer, K. (1979), ‘Interpolation of operators on Sobolev spaces’, Ann. Math. 109, 583–599.CrossRefGoogle Scholar
DeVore, R. A. and Scherer, K. (1980), Variable knot, variable degree approximation to xbgr, in Quantitative Approximation (DeVore, R. A. and Scherer, K., eds), Academic Press, New York, pp. 121–131.CrossRefGoogle Scholar
DeVore, R. A. and Sharpley, R. C. (1984), Maximal Functions Measuring Smoothness, Memoirs Vol. 293, American Mathematical Society, Providence, RI.Google Scholar
DeVore, R. A. and Sharpley, R. C. (1993), ‘Besov spaces on domains in ℝd’ Trans. Amer. Math. Soc. 335, 843–864.Google Scholar
DeVore, R. A. and Temlyakov, V. (1996), ‘Some remarks on greedy algorithms’, Adv. Comput. Math. 5, 173–187.CrossRefGoogle Scholar
DeVore, R. and Yu, X. M. (1986), ‘Multivariate rational approximation’, Trans. Amer. Math. Soc. 293, 161–169.CrossRefGoogle Scholar
DeVore, R. and Yu, X. M. (1990), ‘Degree of adaptive approximation’, Math. Comput. 55, 625–635.Google Scholar
DeVore, R., Howard, R. and Micchelli, C. A. (1989), ‘Optimal nonlinear approximation’, Manuskripta Math. 63, 469–478.CrossRefGoogle Scholar
DeVore, R., Jawerth, B. and Lucier, B. (1992), ‘Image compression through transform coding’, IEEE Proc. Inform. Theory 38, 719–746.CrossRefGoogle Scholar
DeVore, R., Jawerth, B. and Popov, V. (1992), ‘Compression of wavelet decompositions’, Amer. J. Math. 114, 737–785.CrossRefGoogle Scholar
DeVore, R., Kyriazis, G., Leviatan, D. and Tikhomirov, V. M. (1993), ‘Wavelet compression and nonlinear n-widths’, Adv. Comput. Math. 1, 197–214.CrossRefGoogle Scholar
DeVore, R., Lucier, B. and Yang, Z. (1996), Feature extraction in digital mammography, in Wavelets in Biology and Medicine (Aldroubi, A. and Unser, M., eds), CRC, Boca Raton, FL, pp. 145–156.Google Scholar
DeVore, R., Shao, W., Pierce, J., Kaymaz, E., Lerner, B. and Campbell, W. (1997), Using nonlinear wavelet compression to enhance image registration, in Wavelet Applications IV, Proceedings of the SPIE Conf. 3028, AeroSense 97 Conference, Orlando, FL, April 22–24, 1997 (Szu, H., ed.), pp. 539–551.Google Scholar
DeVore, R. A., Konyagin, S. and Temlyakov, V. (1998), ‘Hyperbolic wavelet approximation’, Constr. Approx. 14, 1–26.CrossRefGoogle Scholar
Donoho, D. (1997), ‘CART and best-ortho-basis: a connection’, Ann. Statistics 25, 1870–1911.CrossRefGoogle Scholar
Donoho, D. and Johnstone, I. (1994), ‘Ideal spatial adaptation via wavelet shrinkage’, Biometrika 81, 425–455.CrossRefGoogle Scholar
Donoho, D., Johnstone, I., Kerkyacharian, G. and Picard, D. (1996), ‘Wavelet shrinkage asymptotia?’, J. Royal Statistical Soc., Ser. B. 57, 301–369.Google Scholar
Gao, Z. and Sharpley, R. (1997), ‘Data compression and the elementary encoding of wavelet compression’. Preprint.CrossRefGoogle Scholar
Godlewski, E. and Raviart, P.-A. (1991), Hyperbolic Systems of Conservation Laws, Mathématiques et Applications, Ellipses.Google Scholar
Harten, A. (1994), ‘Adaptive multiresolution schemes for shock computations’, J. Comput. Phys. 115, 319–338.CrossRefGoogle Scholar
Jerison, D. and Kenig, C. E. (1995), ‘The inhomogeneous Dirichlet problem in Lipschitz domains’, J. Functional Analysis 93, 161–219.CrossRefGoogle Scholar
Jia, R. Q. (1983), Approximation by smooth bivariate splines on a three directional mesh, in Approximation Theory IV (Chui, C. K., Schumaker, L. L. and Ward, J., eds), Academic Press, New York, pp. 539–546.Google Scholar
Johnen, H. and Scherer, K. (1977), On the equivalence of the K-functional and moduli of continuity and some applications, in Constructive Theory of Functions of Several Variables, Vol. 571 of Lecture Notes in Mathematics, Springer, Berlin, pp. 119–140.CrossRefGoogle Scholar
Jones, L. (1992), ‘A simple lemma on greedy approximation in Hilbert space and convergence results for projection pursuit regression and neural network training’, Ann. Statistics 20, 608–613.CrossRefGoogle Scholar
Kahane, J. P. (1961), Teoria Constructiva de Functiones, Course notes, University of Buenos Aires.Google Scholar
Kashin, B. (1977) ‘The widths of certain finite dimensional sets and classes of smooth functions’, Izvestia 41, 334–351.Google Scholar
Kashin, B. and Temlyakov, V. (1997), ‘On best n-term approximation and the entropy of sets in the space L 1’, Math. Notes 56, 1137–1157.CrossRefGoogle Scholar
Kondrat'ev, V. A. and Oleinik, O. A. (1983), ‘Boundary value problems for partial differential equations in non-smooth domains’, Russian Math. Surveys 38, 1–86.CrossRefGoogle Scholar
Kyriazis, G. (1996) ‘Wavelet coefficients measuring smoothness in Hp(ℝd)’, Appl. Comput. Harm. Anal. 3, 100–119Google Scholar
Lucier, B. (1986), ‘Regularity through approximation for scalar conservation laws’, SIAM J. Math. Anal. 19, 763–773.CrossRefGoogle Scholar
Lorentz, G. G., von Golitschek, M. and Makovoz, Ju. (1996), Constructive Approximation: Advanced Problems, Springer, Berlin.CrossRefGoogle Scholar
McClure, M. and Carin, L. (1997), ‘Matched pursuits with a wave-based dictionary’. Preprint.Google Scholar
Mairov, V. and Ratasby, J. (1998), ‘On the degree of approximation using manifolds of finite pseudo-dimension’. Preprint.Google Scholar
Mallat, S. (1989), ‘Multiresolution and wavelet orthonormal bases in L 2(ℝ) Trans. Amer. Math. Soc. 315, 69–87.Google Scholar
Mallat, S. (1998), A Wavelet Tour of Signal Processing, Academic Press, New York.Google Scholar
Mallat, S. and Falzon, F. (1997), ‘Analysis of low bit rate image transform coding’. Preprint.CrossRefGoogle Scholar
Meyer, Y. (1990) Ondelettes et Opérateurs, Vols 1 and 2, Hermann, Paris.Google Scholar
Newman, D. (1964), ‘Rational approximation to │x│’, Michigan Math. J. 11, 11–14.CrossRefGoogle Scholar
Novak, E. (1996), ‘On the power of adaptation’, J. Complexity 12, 199–237.Google Scholar
Oskolkov, K. (1979), ‘Polygonal approximation of functions of two variables’, Math. USSR Sbornik 35, 851–861.Google Scholar
Oswald, P. (1980), ‘On the degree of nonlinear spline approximation in Besov–Sobolev spaces’, J. Approx. Theory 61, 131–157.CrossRefGoogle Scholar
Peetre, J. (1963) A Theory of Interpolation of Normed Spaces, Course notes, University of Brasilia.Google Scholar
Pekarski, A. (1986), ‘Relations between the rational and piecewise polynomial approximations’, Izvestia BSSR, Ser. Mat.-Fiz. Nauk 5, 36–39.Google Scholar
Peller, V. (1980), ‘Hankel operators of the class Sp, investigations of the rate of rational approximation and other applications’, Mat. Sbornik 122, 481–510.Google Scholar
Petrushev, P. P. (1986), ‘Relations between rational and spline approximations in Lp metrics’, J. Approx. Theory 50, 141–159.CrossRefGoogle Scholar
Petrushev, P. P. (1988), Direct and converse theorems for spline and rational approximation and Besov spaces, in Function Spaces and Applications (Cwikel, M. et al. , eds), Vol. 1302 of Lecture Notes in Mathematics, Springer, Berlin, pp. 363–377.Google Scholar
Petrushev, P. and Popov, V. (1987), Rational Approximation of Real Functions, Cambridge University Press, Cambridge.Google Scholar
Pisier, G. (1980) ‘Remarques sur un résultat non publié de B. Maurey’, Seminaire d'Analyse Fonctionelle 1980–81, École Polytechnique, Centre de Mathématiques, Palaiseau.Google Scholar
Schmidt, E. (1907), ‘Zur Theorie der linearen und nichtlinearen Integralgleichungen. I’, Math. Ann. 63, 433–476.CrossRefGoogle Scholar
Schoenberg, I. (1946), ‘Contributions to the problem of approximation of equidistant data by analytic functions’, Quart. Appl. Math. 4, 45–99.CrossRefGoogle Scholar
Shapiro, J. (1993), An embedded hierarchial image coder using zerotrees of wavelet coefficients, in Data Compression Conference (Storer, J. A. and Cohn, M., eds), IEEE Computer Society Press, Los Alamitos, CA, pp. 214–223.Google Scholar
Stein, E. (1970), Singular Integrals and Differentiability Properties of Functions, Princeton University Press, Princeton.Google Scholar
Strang, G. and Fix, G. (1973), A Fourier analysis of the finite element variational method, in Constructive Aspects of Functional Analysis (Geymonat, G., ed.), C.I.M.E., II, Ciclo, 1971, pp. 793–840.Google Scholar
Temlyakov, V. (1998a), ‘Best m-term approximation and greedy algorithms’. Preprint.Google Scholar
Temlyakov, V. (1998b), ‘Nonlinear m-term approximation with regard to the multivariate Haar system’. Preprint.Google Scholar
Traub, J. F., Wasilkowski, G. W. and Woźniakowski, H. (1988), Information-Based Complexity, Academic Press, Boston.Google Scholar
Vapnik, V. N. (1982), Estimation of Dependences Based on Empirical Data, Springer, Berlin.Google Scholar
Wickerhauser, M. V. (1994), Adapted Wavelet Analysis from Theory to Software, Peters.Google Scholar
Xiong, Z., Ramchandran, K. and Orchard, M. T. (1997), ‘Space-frequency quantization for wavelet image coding’, Trans. Image Processing 6, 677–693.Google Scholar