Search

Abstract: This is a follow-up paper of “Liberating the dimension for function approximation”, where we studied approximation of infinitely variate functions by algorithms that use linear information consisting of finitely many linear functionals. In this paper, we study similar approximation problems, however, now the algorithms can only use standard information consisting of finitely many function values. We assume that the cost of one function value depends on the number of active variables. We focus on polynomial tractability, and occasionally also study weak tractability. We present non-constructive and constructive results. Non-constructive results are based on known relations between linear and standard information for finitely variate functions, whereas constructive results are based on Smolyak’s construction generalized to the case of infinitely variate functions. Surprisingly, for many cases, the results for standard information are roughly the same as for linear information. [Copyright &y& Elsevier]

In this paper, we present algorithms for the approximation of multivariate periodic functions by trigonometric polynomials. The approximation is based on sampling of multivariate functions on rank-1 lattices. To this end, we study the approximation of periodic functions of a certain smoothness. Our considerations include functions from periodic Sobolev spaces of generalized mixed smoothness. Recently an algorithm for the trigonometric interpolation on generalized sparse grids for this class of functions was investigated by Griebel and Hamaekers (2014). The main advantage of our method is that the algorithm is based mainly on a single one-dimensional fast Fourier transform, and that the arithmetic complexity of the algorithm depends only on the cardinality of the support of the trigonometric polynomial in the frequency domain. Therefore, we investigate trigonometric polynomials with frequencies supported on hyperbolic crosses and energy norm based hyperbolic crosses in more detail. Furthermore, we present an algorithm for sampling multivariate functions on perturbed rank-1 lattices and show the numerical stability of the suggested method. Numerical results are presented up to dimension d = 10 , which confirm the theoretical findings. [ABSTRACT FROM AUTHOR]

Abstract: Regularized classifiers (a leading example is support vector machine) are known to be a kind of kernel-based classification methods generated from Tikhonov regularization schemes, and the polynomial kernels are the original and also probably the most important kernels used in them. In this paper, we provide an error analysis for the regularized classifiers using multivariate polynomial kernels. We introduce Bernstein–Durrmeyer polynomials, whose reproducing kernel Hilbert space norms and approximation properties in space play a key role in the analysis of regularization error. We also introduce the standard estimation of sample error, and derive explicit learning rates for these algorithms. [Copyright &y& Elsevier]

Multivariate integration of high dimension s occurs in many applications. In many such applications, for example in finance, integrands can be well approximated by sums of functions of just a few variables. In this situation the superposition (or effective) dimension is small, and we can model the problem with finite-order weights, where the weights describe the relative importance of each distinct group of variables up to a given order (where the order is the number of variables in a group), and ignore all groups of variables of higher order.In this paper we consider multivariate integration for the anchored and unanchored (non-periodic) Sobolev spaces equipped with finite-order weights. Our main interest is tractability and strong tractability of QMC algorithms in the worst-case setting. That is, we want to find how the minimal number of function values needed to reduce the initial error by a factor ϵ depends on s and ϵ−1. If there is no dependence on s, and only polynomial dependence on ϵ−1, we have strong tractability, whereas with polynomial dependence on both s and ϵ−1 we have tractability.We show that for the anchored Sobolev space we have strong tractability for arbitrary finite-order weights, whereas for the unanchored Sobolev space we have tractability for all bounded finite-order weights. In both cases, the dependence on ϵ−1 is quadratic. We can improve the dependence on ϵ−1 at the expense of polynomial dependence on s. For finite-order weights, we may achieve almost linear dependence on ϵ−1 with a polynomial dependence on s whose degree is proportional to the order of the weights.We show that these tractability bounds can be achieved by shifted lattice rules with generators computed by the component-by-component (CBC) algorithm. The computed lattice rules depend on the weights. Similar bounds can also be achieved by well-known low discrepancy sequences such as Halton, Sobol and Niederreiter sequences which do not depend on the weights. We prove that these classical low discrepancy sequences lead to error bounds with almost linear dependence on n−1 and polynomial dependence on d. We present explicit worst-case error bounds for shifted lattice rules and for the Niederreiter sequence. Better tractability and error bounds are possible for finite-order weights, and even for general weights if they satisfy certain conditions. We present conditions on general weights that guarantee tractability and strong tractability of multivariate integration. [Copyright &y& Elsevier]