Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)



Approximation using scattered shifts of a multivariate function

Authors: Ronald DeVore and Amos Ron
Journal: Trans. Amer. Math. Soc. 362 (2010), 6205-6229
MSC (2010): Primary 41A15, 41A46, 41A25, 68T05
Published electronically: July 15, 2010
MathSciNet review: 2678971
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: The approximation of a general $ d$-variate function $ f$ by the shifts $ \phi(\cdot-\xi)$, $ \xi\in\Xi\subset \mathbb{R}^d$, of a fixed function $ \phi$ occurs in many applications such as data fitting, neural networks, and learning theory. When $ \Xi=h\mathbb{Z}^d$ is a dilate of the integer lattice, there is a rather complete understanding of the approximation problem using Fourier techniques. However, in most applications, the center set $ \Xi$ is either given, or can be chosen with complete freedom. In both of these cases, the shift-invariant setting is too restrictive. This paper studies the approximation problem in the case that $ \Xi$ is arbitrary. It establishes approximation theorems whose error bounds reflect the local density of the points in $ \Xi$. Two different settings are analyzed. The first occurs when the set $ \Xi$ is prescribed in advance. In this case, the theorems of this paper show that, in analogy with the classical univariate spline approximation, an improved approximation occurs in regions where the density is high. The second setting corresponds to the problem of nonlinear approximation. In that setting the set $ \Xi$ can be chosen using information about the target function $ f$. We discuss how to `best' make these choices and give estimates for the approximation error.

References [Enhancements On Off] (What's this?)

  • 1. R. A. BROWNLEE, E. H. GEORGOULIS, AND J. LEVESLEY, Extending the range of error estimates for radial approximation in Euclidean space and on spheres, SIAM J. Math. Anal., 39 (2007), pp. 554-564. MR 2338420 (2008j:41002)
  • 2. M. BUHMANN, N. DYN, AND D. LEVIN, On quasi-interpolation by radial basis functions with scattered centers, Constructive Approximation, 11 (2) (1995), pp. 239-254. MR 1342386 (96h:41038)
  • 3. M. BUHMANN AND A. RON, Radial basis functions: $ L \sb p$-approximation orders with scattered centres, in Curves and Surfaces II, P.J. Laurent, A. Le Méhauté and L.L. Schumaker, eds., A K Peters, 1994. MR 1302241 (95h:41011)
  • 4. M. D. BUHMANN, Multivariate cardinal interpolation with radial-basis functions, Constr. Approx., 6 (1990), pp. 225-255. MR 1054754 (91f:41001)
  • 5. I. DAUBECHIES, Ten Lectures on Wavelets, vol. 61 of CBMS-NSF Lecture Notes, SIAM, 1992. MR 1162107 (93e:42045)
  • 6. C. DE BOOR, A Practical Guide to Splines, Revised Edition, vol. 27 of Applied Mathematical Sciences, Springer-Verlag, Berlin, 2001. MR 1900298 (2003f:41001)
  • 7. C. DE BOOR, R. A. DEVORE, AND A. RON, Approximation from shift-invariant subspaces of $ L\sb 2({\bf R}\sp d)$, Trans. Amer. Math. Soc., 341 (1994), pp. 787-806. MR 1195508 (94d:41028)
  • 8. C. DE BOOR AND A. RON, The exponentials in the span of the multi-integer translates of a compactly supported function; quasi-interpolation and approximation order, Journal of the London Mathematical Society, 45 (1992), pp. 519-535. MR 1180260 (94e:41021)
  • 9. -, Fourier analysis of the approximation power of principal shift-invariant spaces, Constructive Approximation, 8 (1992), pp. 427-462. MR 1194028 (94c:41023)
  • 10. R. DEVORE, B. JAWERTH, AND V. POPOV, Compression of wavelet decompositions, American Journal of Mathematics, 114 (1992), pp. 737-785. MR 1175690 (94a:42045)
  • 11. R. DEVORE AND V. POPOV, Interpolation spaces and nonlinear approximation, in Function Spaces and Applications, eds. M. Cwikel, J. Peetre, Y. Sagher, and H. Wallin, Springer, Berlin, 1988, pp. 191-205. Lecture Notes in Math., Vol. 1302. MR 942269 (89d:41035)
  • 12. R. DEVORE AND X. M. YU, Degree of adaptive approximation, Math. Comp., 55 (1990), pp. 625-635. MR 1035930 (91g:41022)
  • 13. R. A. DEVORE AND G. G. LORENTZ, Constructive approximation, vol. 303 of Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], Springer-Verlag, Berlin, 1993. MR 1261635 (95f:41001)
  • 14. J. DUCHON, Splines minimizing rotation-invariant semi-norms in Sobolev spaces, in Constructive theory of functions of several variables (Proc. Conf., Math. Res. Inst., Oberwolfach, 1976), Springer, Berlin, 1977, pp. 85-100. Lecture Notes in Math., Vol. 571. MR 0493110 (58:12146)
  • 15. -, Sur l'erreur d'interpolation des fonctions de plusieurs variables par les $ D\sp{m}$-splines, RAIRO Anal. Numér., 12 (1978), pp. 325-334. MR 519016 (80j:41052)
  • 16. N. DYN AND A. RON, Radial basis function approximation: From gridded centres to scattered centres, Proc. London Math. Soc. (3), 71 (1995), pp. 76-108. MR 1327934 (96f:41040)
  • 17. C. FEFFERMAN AND E. STEIN, Some maximal inequalities, Amer. J. Math, 93 (1971), pp. 107-115. MR 0284802 (44:2026)
  • 18. T. HANGELBROEK, Error estimates for thin plate spline approximation in the disk, Constr. Approx., 28 (2008), pp. 27-59. MR 2357985
  • 19. M. J. JOHNSON, On the approximation order of principal shift-invariant subspaces of $ L\sb p({\bf R}\sp d)$, J. Approx. Theory, 91 (1997), pp. 279-319. MR 1486470 (99b:41010)
  • 20. M. J. JOHNSON, A bound on the approximation order of surface splines, Constr. Approx., 14 (1998), pp. 429-438. MR 1626718 (99c:41023)
  • 21. M. J. JOHNSON, Approximation in $ L_p(R^d)$ from spaces spanned by the perturbed integer translates of a radial function, J. Approx. Theory, 107 (2000), pp. 163-203. MR 1806949 (2002a:41019)
  • 22. W. R. MADYCH AND S. A. NELSON, Multivariate interpolation: A variational theory, unpublished, 1983.
  • 23. Y. MEYER, Ondelettes et opérateurs, I: Ondelettes, II: Opérateurs de Calderón-Zygmund, III: Opérateurs multilinéaires, Hermann, Paris, 1990. MR 1085487 (93i:42002)
  • 24. C. A. MICCHELLI, Interpolation of scattered data: Distance matrices and conditionally positive definite functions, Constr. Approx., 2 (1986), pp. 11-22. MR 891767 (88d:65016)
  • 25. F. J. NARCOWICH AND J. D. WARD, Scattered-data interpolation on $ {\bf R}\sp n$: Error estimates for radial basis and band-limited functions, SIAM J. Math. Anal., 36 (2004), pp. 284-300. MR 2083863 (2005g:41011)
  • 26. P. PETRUSHEV, Direct and converse theorems for rational and spline approximation and Besov spaces, in Function Spaces and Applications, eds. M. Cwikel, J. Peetre, Y. Sagher, and H. Wallin, Springer, Berlin, 1988, pp. 363-377. Lecture Notes in Math., Vol. 1302. MR 942281 (89d:41027)
  • 27. M. J. D. POWELL, The uniform convergence of thin plate spline interpolation in two dimensions, Numer. Math., 68 (1994), pp. 107-128. MR 1278451 (95c:41037)
  • 28. A. RON, The $ L\sb 2$-approximation orders of principal shift-invariant spaces generated by a radial basis function, in Numerical Methods of Approximation Theory, Vol. 9, D. Braess & L.L. Schumaker, eds., International Series of Numerical Mathematics, 1992, pp. 245-268. MR 1269365 (95d:41035)
  • 29. R. SCHABACK, Approximation by radial basis functions with finitely many centers, Constr. Approx., 12 (1996), pp. 331-340. MR 1405002 (97d:41013)
  • 30. I. J. SCHOENBERG, Metric spaces and completely monotone functions, Ann. of Math. (2), 39 (1938), pp. 811-841. MR 1503439
  • 31. -, Metric spaces and positive definite functions, Trans. Amer. Math. Soc., 44 (1938), pp. 522-536. MR 1501980
  • 32. H. TRIEBEL, Interpolation Theory, Function Spaces, and Differential Operators, North-Holland, Amsterdam, 1978. MR 503903 (80i:46032b)
  • 33. H. WENDLAND, Scattered data approximation, vol. 17 of Cambridge Monographs on Applied and Computational Mathematics, Cambridge University Press, Cambridge, 2005. MR 2131724 (2006i:41002)
  • 34. Z. M. WU AND R. SCHABACK, Local error estimates for radial basis function interpolation of scattered data, IMA J. Numer. Anal., 13 (1993), pp. 13-27. MR 1199027 (93m:65012)
  • 35. J. YOON, Approximation in $ L\sb p({\bf R}\sp d)$ from a space spanned by the scattered shifts of a radial basis function, Constr. Approx., 17 (2001), pp. 227-247. MR 1814356 (2002a:41021)
  • 36. -, Interpolation by radial basis functions on Sobolev space, Journal of Approximation Theory, 112 (2001), pp. 1-15. MR 1857599 (2003c:41027)
  • 37. -, Spectral approximation orders of radial basis function interpolation on the Sobolev space, Siam Journal on Mathematical Analysis, 33 (2001), pp. 946-958. MR 1885291 (2002m:41012)

Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC (2010): 41A15, 41A46, 41A25, 68T05

Retrieve articles in all journals with MSC (2010): 41A15, 41A46, 41A25, 68T05

Additional Information

Ronald DeVore
Affiliation: Department of Mathematics, Texas A&M University, College Station, Texas 77843

Amos Ron
Affiliation: Computer Science Department, University of Wisconsin-Madison, Madison, Wisconsin 53706

Keywords: Image/signal processing, computation, nonlinear approximation, optimal approximation, radial basis functions, scattered data, thin-plate splines, surface splines, approximation order
Received by editor(s): February 17, 2008
Published electronically: July 15, 2010
Additional Notes: This work was supported by the Office of Naval Research Contracts ONR-N00014-08-1-1113; the Army Research Office Contracts DAAD 19-02-1-0028, W911NF-05-1-0227, and W911NF-07-1-0185; the National Institute of General Medical Sciences under Grant NIH-1-R01-GM072000-01; and the National Science Foundation under Grants DMS-0221642, DMS-9872890, DMS-354707, DBI-9983114, ANI-0085984, DMS-0602837 and DMS-0915231
Article copyright: © Copyright 2010 American Mathematical Society

American Mathematical Society