On the power of standard information for tractability for L∞ approximation of periodic functions in the worst case setting

We study multivariate approximation of periodic functions in the worst case setting with the error measured in the $L_{\infty }$ norm. We consider algorithms that use standard information ${\mathrm{\Lambda }}^{\mathrm{std}}$ consisting of function values or general linear information ${\mathrm{\Lambda }}^{\mathrm{all}}$ consisting of arbitrary continuous linear functionals. We investigate equivalences of various notions of algebraic and exponential tractability for ${\mathrm{\Lambda }}^{\mathrm{std}}$ and ${\mathrm{\Lambda }}^{\mathrm{all}}$ under the absolute or normalized error criterion, and show that the power of ${\mathrm{\Lambda }}^{\mathrm{std}}$ is the same as the one of ${\mathrm{\Lambda }}^{\mathrm{all}}$ for various notions of algebraic and exponential tractability. Our results can be applied to weighted Korobov spaces and Korobov spaces with exponential weights. This gives a special solution to Open Problem 145 as posed by Novak and Woźniakowski (2012) [40].     

确定性与随机化框架下的Sobolev类上的嵌入与积分的复杂性

本文研究各向异性Sobolev类上的嵌入以及积分问题的复杂性.我们得到这些问题在确定性、随机化框架以及平均框架下n-重最小误差的精确阶.所得结果表明在非嵌入连续函数空间情形,随机误差与平均误差实质性地小于确定性误差.从数量级看,对于嵌入问题,收敛阶最大改进可达到n-1+ε,这里ε是任意正数.对于积分问题最大改进可达到n...     

On the tractability of linear tensor product problems in the worst case

It has been an open problem to derive a necessary and sufficient condition for a linear tensor product problem to be weakly tractable in the worst case. The complexity of linear tensor product problems in the worst case depends on the eigenvalues _{λi}i∈N${\left\{{\lambda }_i\right\}}_{i\in \mathbb{N}}$ of a certain operator. It is known that if _λ1=1${\lambda }_1=1$ and _λ2∈(0,1)${\lambda }_2\in (0,1)$ then _λn=o((lnn)⁻²)${\lambda }_n=o\left({(lnn)}^{-2}\right)$, as n→∞$n\to \infty$, is a necessary condition for a problem to be weakly tractable. We show that this is a sufficient condition as well.     

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

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 L₂ 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 L₂ 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.     

Worst case complexity of multivariate Feynman–Kac path integration

We study the multivariate Feynman–Kac path integration problem. This problem was studied in Plaskota et al. (J. Comp. Phys. 164 (2000) 335) for the univariate case. We describe an algorithm based on uniform approximation, instead of the L₂-approximation used in Plaskota et al. (2000). Similarly to Plaskota et al. (2000), our algorithm requires extensive precomputing. We also present bounds on the complexity of our problem. The lower bound is provided by the complexity of a certain integration problem, and the upper bound by the complexity of the uniform approximation problem. The algorithm presented in this paper is almost optimal for the classes of functions for which uniform approximation and integration have roughly the same complexities.     

Average case tractability of non-homogeneous tensor product problems with the absolute error criterion

We study average case tractability of non-homogeneous tensor product problems with the absolute error criterion. We consider algorithms that use finitely many evaluations of arbitrary linear functionals. For general non-homogeneous tensor product problems, we obtain the matching necessary and sufficient conditions for strong polynomial tractability in terms of the one-dimensional eigenvalues. We give some examples to show that strong polynomial tractability is not equivalent to polynomial tractability, and polynomial tractability is not equivalent to quasi-polynomial tractability. But for non-homogeneous tensor product problems with decreasing eigenvalues, we prove that strong polynomial tractability is always equivalent to polynomial tractability, and strong polynomial tractability is even equivalent to quasi-polynomial tractability when the one-dimensional largest eigenvalues are less than one. In particular, we find an example that quasi-polynomial tractability with the absolute error criterion is not equivalent to that with the normalized error criterion even if all the one-dimensional largest eigenvalues are one. Finally we consider a special class of non-homogeneous tensor product problems with improved monotonicity condition of the eigenvalues.     

单形积上的Sobolev类逼近问题的易处理性

我们在最大框架下研究定义于单纯形T~dR~d的m重积上的Sobolev类逼近问题的易处理性.对于信息类A~(all),得到了问题具有几种易处理性相匹配的充要条件,结果是依赖于问题参数的.本文是相应积分问题的继续研究.     

Sample Numbers and Optimal Lagrange Interpolation of Sobolev Spaces Wr1*

This paper investigates the optimal recovery of Sobolev spaces W^r₁[?1, 1], r ∈ N in the space L1[?1, 1]. They obtain the values of the sampling numbers of W^r₁[?1, 1] in L₁[?1, 1] and show that the Lagrange interpolation algorithms based on the extreme points of Chebyshev polynomials are optimal algorithms. Meanwhile, they prove that the extreme points of Chebyshev polynomials are optimal Lagrange interpolation nodes.     

A heuristic approximation of the worst case of Shellsort

A heuristic algorithm is presented to construct permutations which require as many moves in sorting by Shellsort as possible. The approximations obtained are compared with those found by other known methods. Experiments were performed with up ton=2047 elements to be sorted, and the results show the distinct superiority of the heuristic approximations. The actual times needed by Shellsort to sort the worst permutations achieved were determined and compared with the corresponding times of Shellsort in the average case, as well as with the times of quicksort and heapsort in their worst cases.     

Lattice-Nyström method for Fredholm integral equations of the second kind with convolution type kernels

We consider Fredholm integral equations of the second kind of the form , where g and k are given functions from weighted Korobov spaces. These spaces are characterized by a smoothness parameter α>1 and weights γ₁≥γ₂≥. The weight γ_j moderates the behavior of the functions with respect to the jth variable. We approximate f  by the Nyström method using n rank-1 lattice points. The combination of convolution and lattice group structure means that the resulting linear system can be solved in O(nlogn) operations. We analyze the worst case error measured in sup norm for functions g in the unit ball and a class of functions k in weighted Korobov spaces. We show that the generating vector of the lattice rule can be constructed component-by-component to achieve the optimal rate of convergence O(n^-α/2+δ), δ>0, with the implied constant independent of the dimension d under an appropriate condition on the weights. This construction makes use of an error criterion similar to the worst case integration error in weighted Korobov spaces, and the computational cost is only O(nlognd) operations. We also study the notion of QMC-Nyström tractability: tractability means that the smallest n needed to reduce the worst case error (or normalized error) to is bounded polynomially in ^-1 and d; strong tractability means that the bound is independent of d. We prove that strong QMC-Nyström tractability in the absolute sense holds iff , and QMC-Nyström tractability holds in the absolute sense iff .     

Approximation and relaxation of perimeter in the Wiener space

We characterize the relaxation of the perimeter in an infinite dimensional Wiener space, with respect to the weak L²$L^2$-topology. We also show that the rescaled Allen–Cahn functionals approximate this relaxed functional in the sense of Γ-convergence.     

Quasi-polynomial tractability of linear problems in the average case setting

We study d$d$-variate approximation problems in the average case setting with respect to a zero-mean Gaussian measure. We consider algorithms that use finitely many evaluations of arbitrary linear functionals. For the absolute error criterion, we obtain the necessary and sufficient conditions in terms of the eigenvalues of its covariance operator and obtain an estimate of the exponent t^qpol-avg$t^{\text{qpol-avg}}$ of quasi-polynomial tractability which cannot be improved in general. For the linear tensor product problems, we find that the quasi-polynomial tractability is equivalent to the strong polynomial tractability. For the normalized error criterion, we solve a problem related to the Korobov kernels, which is left open in Lifshits et al. (2012).