The power of adaption for approximating functions with singularities
HTML articles powered by AMS MathViewer
- by Leszek Plaskota, Grzegorz W. Wasilkowski and Yaxi Zhao PDF
- Math. Comp. 77 (2008), 2309-2338 Request permission
Abstract:
Consider approximating functions based on a finite number of their samples. We show that adaptive algorithms are much more powerful than nonadaptive ones when dealing with piecewise smooth functions. More specifically, let $F_r^1$ be the class of scalar functions $f:[0,T]\to \mathbb {R}$ whose derivatives of order up to $r$ are continuous at any point except for one unknown singular point. We provide an adaptive algorithm $\mathcal {A}_n^\textrm {ad}$ that uses at most $n$ samples of $f$ and whose worst case $L^p$ error ($1\le p<\infty$) with respect to ‘reasonable’ function classes $\mathcal {F}_r^1\subset F_r^1$ is proportional to $n^{-r}$. On the other hand, the worst case error of any nonadaptive algorithm that uses $n$ samples is at best proportional to $n^{-1/p}$.
The restriction to only one singularity is necessary for superiority of adaption in the worst case setting. Fortunately, adaption regains its power in the asymptotic setting even for a very general class $F_r^\infty$ consisting of piecewise $C^{r}$-smooth functions, each having a finite number of singular points. For any $f\in F_r^\infty$ our adaptive algorithm approximates $f$ with error converging to zero at least as fast as $n^{-r}$. We also prove that the rate of convergence for nonadaptive methods cannot be better than $n^{-1/p}$, i.e., is much slower.
The results mentioned above do not hold if the errors are measured in the $L^\infty$ norm, since no algorithm produces small $L^\infty$ errors for functions with unknown discontinuities. However, we strongly believe that the $L^\infty$ norm is inappropriate when dealing with singular functions and that the Skorohod metric should be used instead. We show that our adaptive algorithm retains its positive properties when the approximation error is measured in the Skorohod metric. That is, the worst case error with respect to $\mathcal {F}_r^1$ equals $\Theta (n^{-r})$, and the convergence in the asymptotic setting for $F_r^\infty$ is $n^{-r}$.
Numerical results confirm the theoretical properties of our algorithms.
References
- Francesc Arandiga, Albert Cohen, Rosa Donat, and Nira Dyn, Interpolation and approximation of piecewise smooth functions, SIAM J. Numer. Anal. 43 (2005), no. 1, 41–57. MR 2177955, DOI 10.1137/S0036142903426245
- Kendall E. Atkinson, An introduction to numerical analysis, 2nd ed., John Wiley & Sons, Inc., New York, 1989. MR 1007135
- N. S. Bahvalov, The optimality of linear operator approximation methods on convex function classes, Ž. Vyčisl. Mat i Mat. Fiz. 11 (1971), 1014–1018 (Russian). MR 290523
- Patrick Billingsley, Convergence of probability measures, John Wiley & Sons, Inc., New York-London-Sydney, 1968. MR 0233396
- Emmanuel J. Candès and David L. Donoho, New tight frames of curvelets and optimal representations of objects with piecewise $C^2$ singularities, Comm. Pure Appl. Math. 57 (2004), no. 2, 219–266. MR 2012649, DOI 10.1002/cpa.10116
- Philip J. Davis and Philip Rabinowitz, Methods of numerical integration, Computer Science and Applied Mathematics, Academic Press [Harcourt Brace Jovanovich, Publishers], New York-London, 1975. MR 0448814
- C. de Boor, CADRE: An algorithm for numerical quadrature, Mathematical Software, pp. 201–209, Academic Press, New York, 1971.
- Ingrid Daubechies, Ten lectures on wavelets, CBMS-NSF Regional Conference Series in Applied Mathematics, vol. 61, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1992. MR 1162107, DOI 10.1137/1.9781611970104
- David L. Donoho, Martin Vetterli, R. A. DeVore, and Ingrid Daubechies, Data compression and harmonic analysis, IEEE Trans. Inform. Theory 44 (1998), no. 6, 2435–2476. Information theory: 1948–1998. MR 1658775, DOI 10.1109/18.720544
- Shmuel Gal and Charles A. Micchelli, Optimal sequential and nonsequential procedures for evaluating a functional, Applicable Anal. 10 (1980), no. 2, 105–120. MR 575536, DOI 10.1080/00036818008839292
- A. N. Kolmogorov, On the Skorohod convergence, Teor. Veroyatnost. i Primenen. 1 (1956), 239–247 (Russian, with English summary). MR 0085638
- Arnold R. Krommer and Christoph W. Ueberhuber, Computational integration, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1998. MR 1625683, DOI 10.1137/1.9781611971460
- J. N. Lyness, Notes on the adaptive Simpson quadrature routine, J. Assoc. Comput. Mach. 16 (1969), 483–495. MR 240981, DOI 10.1145/321526.321537
- W. M. McKeeman, Algorithm 145, adaptive numerical integration by Simpson’s rule, Comm. ACM 5 (1962), pp. 604.
- H. N. Mhaskar and J. Prestin, Polynomial frames: a fast tour, Approximation theory XI: Gatlinburg 2004, Mod. Methods Math., Nashboro Press, Brentwood, TN, 2005, pp. 287–318. MR 2126687
- Erich Novak, Deterministic and stochastic error bounds in numerical analysis, Lecture Notes in Mathematics, vol. 1349, Springer-Verlag, Berlin, 1988. MR 971255, DOI 10.1007/BFb0079792
- Erich Novak, On the power of adaption, J. Complexity 12 (1996), no. 3, 199–237. MR 1408328, DOI 10.1006/jcom.1996.0015
- K. R. Parthasarathy, Probability measures on metric spaces, Probability and Mathematical Statistics, No. 3, Academic Press, Inc., New York-London, 1967. MR 0226684
- Robert Piessens, Elise de Doncker-Kapenga, Christoph W. Überhuber, and David K. Kahaner, QUADPACK, Springer Series in Computational Mathematics, vol. 1, Springer-Verlag, Berlin, 1983. A subroutine package for automatic integration. MR 712135, DOI 10.1007/978-3-642-61786-7
- Leszek Plaskota, Noisy information and computational complexity, Cambridge University Press, Cambridge, 1996. MR 1446005, DOI 10.1017/CBO9780511600814
- Leszek Plaskota and Grzegorz W. Wasilkowski, Adaption allows efficient integration of functions with unknown singularities, Numer. Math. 102 (2005), no. 1, 123–144. MR 2206675, DOI 10.1007/s00211-005-0640-3
- Anthony Ralston and Philip Rabinowitz, A first course in numerical analysis, 2nd ed., International Series in Pure and Applied Mathematics, McGraw-Hill Book Co., New York-Auckland-Bogotá, 1978. MR 0494814
- John R. Rice, A metalgorithm for adaptive quadrature, J. Assoc. Comput. Mach. 22 (1975), 61–82. MR 483327, DOI 10.1145/321864.321870
- Klaus Ritter, Average-case analysis of numerical problems, Lecture Notes in Mathematics, vol. 1733, Springer-Verlag, Berlin, 2000. MR 1763973, DOI 10.1007/BFb0103934
- Krzysztof A. Sikorski, Optimal solution of nonlinear equations, Oxford University Press, Oxford, 2001. MR 1827804
- A. V. Skorohod, Limit theorems for stochastic processes, Teor. Veroyatnost. i Primenen. 1 (1956), 289–319 (Russian, with English summary). MR 0084897
- G. M. Trojan, Asymptotic Setting for Linear Problems, unpublished Ph.D. dissertation, 1980. (See also [28, Sect. 2, Chap. 10].)
- J. F. Traub, G. W. Wasilkowski, and H. Woźniakowski, Information-based complexity, Computer Science and Scientific Computing, Academic Press, Inc., Boston, MA, 1988. With contributions by A. G. Werschulz and T. Boult. MR 958691
- J. F. Traub and A. G. Werschulz, Complexity and information, Lezioni Lincee. [Lincei Lectures], Cambridge University Press, Cambridge, 1998. MR 1692462, DOI 10.1080/16073606.1997.9631861
- Joe Fred Traub and H. Woźniakowsi, A general theory of optimal algorithms, ACM Monograph Series, Academic Press, Inc. [Harcourt Brace Jovanovich, Publishers], New York-London, 1980. MR 584446
- G. W. Wasilkowski, Information of varying cardinality, J. Complexity 2 (1986), no. 3, 204–228. MR 922813, DOI 10.1016/0885-064X(86)90002-6
- Grace Wahba, Spline models for observational data, CBMS-NSF Regional Conference Series in Applied Mathematics, vol. 59, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1990. MR 1045442, DOI 10.1137/1.9781611970128
- Arthur G. Werschulz, The computational complexity of differential and integral equations, Oxford Mathematical Monographs, The Clarendon Press, Oxford University Press, New York, 1991. An information-based approach; Oxford Science Publications. MR 1144521
Additional Information
- Leszek Plaskota
- Affiliation: Faculty of Mathematics, Informatics, and Mechanics, University of Warsaw, Banacha 2, 02-097 Warsaw, Poland
- Email: leszekp@mimuw.edu.pl
- Grzegorz W. Wasilkowski
- Affiliation: Department of Computer Science, University of Kentucky, 773 Anderson Hall, Lexington, Kentucky 40506-0046
- MR Author ID: 189251
- ORCID: 0000-0003-4727-7368
- Email: greg@cs.uky.edu
- Yaxi Zhao
- Affiliation: Department of Computer Science, University of Kentucky, 773 Anderson Hall, Lexington, Kentucky 40506-0046
- Email: yaxi@uky.edu
- Received by editor(s): July 24, 2007
- Published electronically: April 24, 2008
- © Copyright 2008
American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication. - Journal: Math. Comp. 77 (2008), 2309-2338
- MSC (2000): Primary 65Y20, 65D05, 41A10, 41A25
- DOI: https://doi.org/10.1090/S0025-5718-08-02103-0
- MathSciNet review: 2429887