Lattice algorithms for multivariate L approximation in the worst-case setting

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

Research output: Contribution to journalArticlepeer-review

11 Scopus citations


We approximate d-variate functions from weighted Korobov spaces with the error of approximation defined in the L sense. We study lattice algorithms and consider the worst-case setting in which the error is defined by its worst-case behavior over the unit ball of the space of functions. A lattice algorithm is specified by a generating (integer) vector. We propose three choices of such vectors, each corresponding to a different search criterion in the component-by-component construction. We present worst-case error bounds that go to zero polynomially with n-1, where n is the number of function values used by the lattice algorithm. Under some assumptions on the weights of the function space, the worst-case error bounds are also polynomial in d, in which case we have (polynomial) tractability, or even independent of d, in which case we have strong (polynomial) tractability. We discuss the exponents of n-1 and stress that we do not know if these exponents can be improved.

Original languageEnglish
Pages (from-to)475-493
Number of pages19
JournalConstructive Approximation
Issue number3
StatePublished - Nov 2009


  • Average-case error
  • L2 approximation
  • Lattice algorithm
  • L∞ approximation
  • Multivariate approximation
  • Tractability
  • Worst-case error

ASJC Scopus subject areas

  • Analysis
  • General Mathematics
  • Computational Mathematics


Dive into the research topics of 'Lattice algorithms for multivariate L approximation in the worst-case setting'. Together they form a unique fingerprint.

Cite this