Integration and Approximation Based on Scramble Sampling in Arbitrary Dimensions

This paper considers integration in the worst case setting and approximation in the average case setting based on the scramble sampling scheme proposed by A. B. Owen (1995, Lecture Notes in Statistics, Vol. 106, pp. 299–317, Springer-Verlag, New York.) The tractability and strong tractability exponents are found for function spaces with reproducing/covariance kernels that are scramble-invariant. Integration and approximation for a space with a non-scramble-invariant kernel are no harder than the corresponding problems with the associated scramble-invariant kernel. This enables us to derive tractability results for weighted Sobolev spaces.     

Tractability through increasing smoothness

We prove that some multivariate linear tensor product problems are tractable in the worst case setting if they are defined as tensor products of univariate problems with logarithmically increasing smoothness. This is demonstrated for the approximation problem defined over Korobov spaces and for the approximation problem of certain diagonal operators. For these two problems we show necessary and sufficient conditions on the smoothness parameters of the univariate problems to obtain strong polynomial tractability. We prove that polynomial tractability is equivalent to strong polynomial tractability, and that weak tractability always holds for these problems. Under a mild assumption, the Korobov space consists of periodic functions. Periodicity is crucial since the approximation problem defined over Sobolev spaces of non-periodic functions with a special choice of the norm is not polynomially tractable for all smoothness parameters no matter how fast they go to infinity. Furthermore, depending on the choice of the norm we can even lose weak tractability.     

Tractability of approximating multivariate linear functionals

We review selected tractability results for approximating linear tensor product functionals defined over reproducing kernel Hilbert spaces. This review is based on Volume II of our book Tractability of Multivariate Problems. In particular, we show that all nontrivial linear tensor product functionals defined over a standard tensor product unweighted Sobolev space suffer the curse of dimensionality and therefore they are intractable. To vanquish the curse of dimensionality we need to consider weighted spaces, in which all groups of variables are monitored by weights. We restrict ourselves to product weights and provide necessary and sufficient conditions on these weights to obtain various kinds of tractability.     

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.     

Orthogonality from disjoint support in reproducing kernel Hilbert spaces

We investigate reproducing kernel Hilbert spaces (RKHS) where two functions are orthogonal whenever they have disjoint support. Necessary and sufficient conditions in terms of feature maps for the reproducing kernel are established. We also present concrete examples of finite dimensional RKHS and RKHS with a translation invariant reproducing kernel. In particular, it is shown that a Sobolev space has the orthogonality from disjoint support property if and only if it is of integer index.     

Integration and approximation in arbitrary dimensions

We study multivariate integration and approximation for various classes of functions of d variables with arbitrary d. We consider algorithms that use function evaluations as the information about the function. We are mainly interested in verifying when integration and approximation are tractable and strongly tractable. Tractability means that the minimal number of function evaluations needed to reduce the initial error by a factor of ɛ is bounded by C(d)ɛ^−p for some exponent p independent of d and some function C(d). Strong tractability means that C(d) can be made independent of d. The ‐exponents of tractability and strong tractability are defined as the smallest powers of ɛ{^-1} in these bounds. We prove that integration is strongly tractable for some weighted Korobov and Sobolev spaces as well as for the Hilbert space whose reproducing kernel corresponds to the covariance function of the isotropic Wiener measure. We obtain bounds on the ‐exponents, and for some cases we find their exact values. For some weighted Korobov and Sobolev spaces, the strong ‐exponent is the same as the ‐exponent for d=1, whereas for the third space it is 2. For approximation we also consider algorithms that use general evaluations given by arbitrary continuous linear functionals as the information about the function. Our main result is that the ‐exponents are the same for general and function evaluations. This holds under the assumption that the orthonormal eigenfunctions of the covariance operator have uniformly bounded L∞ norms. This assumption holds for spaces with shift-invariant kernels. Examples of such spaces include weighted Korobov spaces. For a space with non‐shift‐invariant kernel, we construct the corresponding space with shift-invariant kernel and show that integration and approximation for the non-shift-invariant kernel are no harder than the corresponding problems with the shift-invariant kernel. If we apply this construction to a weighted Sobolev space, whose kernel is non-shift-invariant, then we obtain the corresponding Korobov space. This enables us to derive the results for weighted Sobolev spaces. This revised version was published online in June 2006 with corrections to the Cover Date.     

Real Inversion Formulas of the Laplace Transform on Weighted Function Spaces

We investigate compactness of linear operators associated with the real inversion formulas of the Laplace transform, coming with weighted Sobolev reproducing kernel Hilbert spaces on the half line R ⁺. We present concrete reproducing kernels along with several typical examples. Submitted: October 13, 2007. Accepted: November 11, 2007.     

Tight frame expansions of multiscale reproducing kernels in Sobolev spaces

Multiscale kernels are a new type of positive definite reproducing kernels in Hilbert spaces. They are constructed by a superposition of shifts and scales of a single refinable function and were introduced in the paper of R. Opfer [Multiscale kernels, Adv. Comput. Math. (2004), in press]. By applying standard reconstruction techniques occurring in radial basis function- or machine learning theory, multiscale kernels can be used to reconstruct multivariate functions from scattered data. The multiscale structure of the kernel allows to represent the approximant on several levels of detail or accuracy. In this paper we prove that multiscale kernels are often reproducing kernels in Sobolev spaces. We use this fact to derive error bounds. The set of functions used for the construction of the multiscale kernel will turn out to be a frame in a Sobolev space of certain smoothness. We will establish that the frame coefficients of approximants can be computed explicitly. In our case there is neither a need to compute the inverse of the frame operator nor is there a need to compute inner products in the Sobolev space. Moreover we will prove that a recursion formula between the frame coefficients of different levels holds. We present a bivariate numerical example illustrating the mutiresolution and data compression effect.     

Sampling in Reproducing Kernel Banach Spaces

It is well-known the close relationship between reproducing kernel Hilbert spaces and sampling theory. The concept of reproducing kernel Hilbert space has been recently generalized to the case of Banach spaces. In this paper, some sampling results are proven in this new setting of reproducing kernel Banach spaces.     

Analytical and numerical inversion formulas in the Gaussian convolution by using the Paley–Wiener spaces

We shall discuss the relations among sampling theory (Sinc method), reproducing kernels and the Tikhonov regularization. Here, we see the important difference of the Sobolev Hilbert spaces and the Paley–Wiener spaces when we use their reproducing kernel Hibert spaces as approximate spaces in the Tikhonov regularization. Further, by using the Paley–Wiener spaces, we shall illustrate numerical experiments for new inversion formulas for the Gaussian convolution as a much more powerful and improved method by using computers. In this article, we shall be able to give practical numerical and analytical inversion formulas for the Gaussian convolution that is realized by computers.     

Solutions of Tikhonov Functional Equations and Applications to Multiplication Operators on Szegö Spaces

We consider a natural representation of solutions for Tikhonov functional equations. This will be done by applying the theory of reproducing kernels to the approximate solutions of general bounded linear operator equations (when defined from reproducing kernel Hilbert spaces into general Hilbert spaces), by using the Hilbert–Schmidt property and tensor product of Hilbert spaces. As a concrete case, we shall consider generalized fractional functions formed by the quotient of Bergman functions by Szegö functions considered from the multiplication operators on the Szegö spaces.     

ON THE POWER OF STANDARD INFORMATION FOR APPROXIMATION IN RANDOMIZED SETTING

This article considers weighted approximation of multivariate function inreproducing kernel Hilbert space, and gives a relation between nth minimal errors for standard and linear information in the randomized setting. Using this relation we canestimate the nth minimal error for standard information by the nth minimal errorfor linear information, and study the tractability and strong tractability for these twoclasses of information.     

Fractional Generalized Random Fields of Variable Order

Abstract

We study the class of random fields having their reproducing kernel Hilbert space isomorphic to a fractional Sobolev space of variable order on ? ⁿ . Prototypes of this class include multifractional Brownian motion, multifractional free Markov fields, and multifractional Riesz–Bessel motion. The study is carried out using the theory of generalized random fields defined on fractional Sobolev spaces of variable order. Specifically, we consider the class of generalized random fields satisfying a pseudoduality condition of variable order. The factorization of the covariance operator of the pseudodual allows the definition of a white-noise linear filter representation of variable order. In the ordinary case, the Hölder continuity, in the mean-square sense, of the class of random fields introduced is proved, and its mean-square Hölder spectrum is defined in terms of the variable regularity order of the functions in the associated reproducing kernel Hilbert space. The pseudodifferential representation of variable order of the resulting class of multifractal random fields is also defined. Some examples of pseudodifferential models of variable order are then given.     

Reproducing kernels of Sobolev spaces via a green kernel approach with differential operators and boundary operators

We introduce a vector differential operator P and a vector boundary operator B to derive a reproducing kernel along with its associated Hilbert space which is shown to be embedded in a classical Sobolev space. This reproducing kernel is a Green kernel of differential operator L:?=?P ^???T P with homogeneous or nonhomogeneous boundary conditions given by B, where we ensure that the distributional adjoint operator P ^??? of P is well-defined in the distributional sense. We represent the inner product of the reproducing-kernel Hilbert space in terms of the operators P and B. In addition, we find relationships for the eigenfunctions and eigenvalues of the reproducing kernel and the operators with homogeneous or nonhomogeneous boundary conditions. These eigenfunctions and eigenvalues are used to compute a series expansion of the reproducing kernel and an orthonormal basis of the reproducing-kernel Hilbert space. Our theoretical results provide perhaps a more intuitive way of understanding what kind of functions are well approximated by the reproducing kernel-based interpolant to a given multivariate data sample.     

Component-by-Component Construction of Good Lattice Rules with a Composite Number of Points

We develop algorithms to construct rank-1 lattice rules in weighted Korobov spaces of periodic functions and shifted rank-1 lattice rules in weighted Sobolev spaces of non-periodic functions. Analyses are given which show that the rules so constructed achieve strong QMC tractability error bounds. Unlike earlier analyses, there is no assumption that n, the number of quadrature points, be a prime number. However, we do assume that there is an upper bound on the number of distinct prime factors of n. The generating vectors and shifts characterizing the rules are constructed ‘component-by-component,’ that is, the (d+1)th components of the generating vectors and shifts are obtained using one-dimensional searches, with the previous d components kept unchanged.     

若干周期再生核空间的覆盖数

借助离散Fourier变换给出估计Mercer核矩阵逆矩阵范数上界的一种方法,由此给出了估计周期再生核Hilbert空间覆盖数的上、下界的一般方法.特别, 对两种特殊的周期再生核空间覆盖数的上、下界进行了比较.     

Solutions of fractional gas dynamics equation by a new technique

In this paper, a novel technique is formed to obtain the solution of a fractional gas dynamics equation. Some reproducing kernel Hilbert spaces are defined. Reproducing kernel functions of these spaces have been found. Some numerical examples are shown to confirm the efficiency of the reproducing kernel Hilbert space method. The accurate pulchritude of the paper is arisen in its strong implementation of Caputo fractional order time derivative on the classical equations with the success of the highly accurate solutions by the series solutions. Reproducing kernel Hilbert space method is actually capable of reducing the size of the numerical work. Numerical results for different particular cases of the equations are given in the numerical section.     

Construction algorithms for polynomial lattice rules for multivariate integration

We introduce a new construction algorithm for digital nets for integration in certain weighted tensor product Hilbert spaces. The first weighted Hilbert space we consider is based on Walsh functions. Dick and Pillichshammer calculated the worst-case error for integration using digital nets for this space. Here we extend this result to a special construction method for digital nets based on polynomials over finite fields. This result allows us to find polynomials which yield a small worst-case error by computer search. We prove an upper bound on the worst-case error for digital nets obtained by such a search algorithm which shows that the convergence rate is best possible and that strong tractability holds under some condition on the weights.

We extend the results for the weighted Hilbert space based on Walsh functions to weighted Sobolev spaces. In this case we use randomly digitally shifted digital nets. The construction principle is the same as before, only the worst-case error is slightly different. Again digital nets obtained from our search algorithm yield a worst-case error achieving the optimal rate of convergence and as before strong tractability holds under some condition on the weights. These results show that such a construction of digital nets yields the until now best known results of this kind and that our construction methods are comparable to the construction methods known for lattice rules.

We conclude the article with numerical results comparing the expected worst-case error for randomly digitally shifted digital nets with those for randomly shifted lattice rules.

     

Random Fields with Multifractional Regularity Order on Heterogenous Fractal Domains

In this article, we study the effect of the geometry of a domain with variable local dimension on the regularity/singularity of the restriction of a multifractional random field on such a domain. The theories of reproducing kernel Hilbert spaces (RKHS) and generalized random fields are applied. Fractional Sobolev spaces of variable order are considered as RKHSs of random fields satisfying certain elliptic multifractional pseudodifferential equations. The multifractal spectra of these random fields are trivial due to the regularity assumptions on the variable order of the fractional derivatives. In this article, we introduce a family of RKHSs defined by isomorphic identification with the trace on a compact heterogeneous fractal domain of a fractional Sobolev space of variable order. The local regularity/singularity order of functions in these spaces, which depends on the variable order of the fractional Sobolev space considered and on the local dimension of the domain, is derived. We also study the spectral properties of the family of models introduced in the mean-square sense. In the Gaussian case, random fields with sample paths having multifractional local Hölder exponent are covered in this framework.     

Generation of point sets by convex optimization for interpolation in reproducing kernel Hilbert spaces

Numerical Algorithms - We propose algorithms to take point sets for kernel-based interpolation of functions in reproducing kernel Hilbert spaces (RKHSs) by convex optimization. We consider the case...