Multivariate L approximation in the worst case setting over reproducing kernel Hilbert spaces

Frances Y. Kuo, Grzegorz W. Wasilkowski, Henryk Woźniakowski

Research output: Contribution to journalArticlepeer-review

19 Scopus citations


We study the worst case setting for approximation of d variate functions from a general reproducing kernel Hilbert space with the error measured in the L norm. We mainly consider algorithms that use n arbitrary continuous linear functionals. We look for algorithms with the minimal worst case errors and for their rates of convergence as n goes to infinity. Algorithms using n function values will be analyzed in a forthcoming paper. We show that the L approximation problem in the worst case setting is related to the weighted L2 approximation problem in the average case setting with respect to a zero-mean Gaussian stochastic process whose covariance function is the same as the reproducing kernel of the Hilbert space. This relation enables us to find optimal algorithms and their rates of convergence for the weighted Korobov space with an arbitrary smoothness parameter α > 1, and for the weighted Sobolev space whose reproducing kernel corresponds to the Wiener sheet measure. The optimal convergence rates are n- (α - 1) / 2 and n- 1 / 2, respectively. We also study tractability of L approximation for the absolute and normalized error criteria, i.e., how the minimal worst case errors depend on the number of variables, d, especially when d is arbitrarily large. We provide necessary and sufficient conditions on tractability of L approximation in terms of tractability conditions of the weighted L2 approximation in the average case setting. In particular, tractability holds in weighted Korobov and Sobolev spaces only for weights tending sufficiently fast to zero and does not hold for the classical unweighted spaces.

Original languageEnglish
Pages (from-to)135-160
Number of pages26
JournalJournal of Approximation Theory
Issue number2
StatePublished - Jun 2008

Bibliographical note

Funding Information:
The first author was supported by a University of New South Wales Vice-chancellor’s Postdoctoral Research Fellowship, and later by an Australian Research Council Queen Elizabeth II Research Fellowship. The second and third authors were partially supported by the National Science Foundation under Grants DMS-0609703 and DMS-0608727, respectively. The third author was also partially supported by the Humboldt Foundation as a recipient of the Humboldt Research Award at the University of Jena. Part of this work was done when the first author visited the University of Kentucky and Columbia University.


  • Average case error
  • L approximation
  • L approximation
  • Multivariate approximation
  • Tractability
  • Worst case error

ASJC Scopus subject areas

  • Analysis
  • Numerical Analysis
  • Mathematics (all)
  • Applied Mathematics


Dive into the research topics of 'Multivariate L approximation in the worst case setting over reproducing kernel Hilbert spaces'. Together they form a unique fingerprint.

Cite this