V. N. Temlyakov

Nonlinear approximation and numerical integration

The main goal of this talk is to demonstrate connections between the following t hree big areas of research: the theory of cubature formulas (numerical integration), the d iscrepancy theory, and nonlinear approximation. In the introductory part we will discuss a relation between results on cubature formulas and on discrepancy. In particular, we will show how standard in the theory of cubature formulas settings can be translated into the d iscrepancy problem and into a natural generalization of the discrepancy problem. This lea ds to a concept of the $r$-discrepancy. Next, we will present results on a relation betwee n construction of an optimal cubature formula with $m$ knots for a given function class an d best nonlinear $m$-term approximation of a special function determined by the function c lass. The nonlinear $m$-term approximation is taken with regard to a redundant dictionary also determined by the function class. We use greedy type algorithms for $m$-term approxi! mation. In particular, we use them to construct deterministic sets of points $\{\xi^1,\d ots,\xi^m\} \subset [0,1]^d$ with the $L_p$ discrepancy less than $Cp^{1/2}m^{-1/2}$, $C$ is an effective absolute cons tant.