Localized sampling in the presence of noise

When the sampled values are corrupted by noise, error estimates for the localized sampling series for approximating a band-limited function are obtained. The result provides error bounds for practical cases including error caused by average sampling, jitter error and amplitude error.     

Double sampling derivatives and truncation error estimates

This paper investigates double sampling series derivatives for bivariate functions defined on R² that are in the Bernstein space. For this sampling series, we estimate some of the pointwise and uniform bounds when the function satisfies some decay conditions. The truncated series of this formula allow us to approximate any order of partial derivatives for function from Bernstein space using only a finite number of samples from the function itself. This sampling formula will be useful in the approximation theory and its applications, especially after having the truncation error well-established. Examples with tables and figures are given at the end of the paper to illustrate the advantages of this formula.     

Compositions of convex functions and fully linear models

Derivative-free optimization (DFO) is the mathematical study of the optimization algorithms that do not use derivatives. One branch of DFO focuses on model-based DFO methods, where an approximation of the objective function is used to guide the optimization algorithm. Proving convergence of such methods often applies an assumption that the approximations form fully linear models—an assumption that requires the true objective function to be smooth. However, some recent methods have loosened this assumption and instead worked with functions that are compositions of smooth functions with simple convex functions (the max-function or the \(\ell _1\) norm). In this paper, we examine the error bounds resulting from the composition of a convex lower semi-continuous function with a smooth vector-valued function when it is possible to provide fully linear models for each component of the vector-valued function. We derive error bounds for the resulting function values and subgradient vectors.     

Geometry of interpolation sets in derivative free optimization

We consider derivative free methods based on sampling approaches for nonlinear optimization problems where derivatives of the objective function are not available and cannot be directly approximated. We show how the bounds on the error between an interpolating polynomial and the true function can be used in the convergence theory of derivative free sampling methods. These bounds involve a constant that reflects the quality of the interpolation set. The main task of such a derivative free algorithm is to maintain an interpolation sampling set so that this constant remains small, and at least uniformly bounded. This constant is often described through the basis of Lagrange polynomials associated with the interpolation set. We provide an alternative, more intuitive, definition for this concept and show how this constant is related to the condition number of a certain matrix. This relation enables us to provide a range of algorithms whilst maintaining the interpolation set so that this condition number or the geometry constant remain uniformly bounded. We also derive bounds on the error between the model and the function and between their derivatives, directly in terms of this condition number and of this geometry constant.     

Error bounds for anisotropic RBF interpolation

We present error bounds for the interpolation with anisotropically transformed radial basis functions for both a function and its partial derivatives. The bounds rely on a growth function and do not contain unknown constants. For polyharmonic basic functions in ${\mathbb{R}}^2$, we show that the anisotropic estimates predict a significant improvement of the approximation error if both the target function and the placement of the centers are anisotropic, and this improvement is confirmed numerically.     

Learning Theory Estimates via Integral Operators and Their Approximations

The regression problem in learning theory is investigated with least square Tikhonov regularization schemes in reproducing kernel Hilbert spaces (RKHS). We follow our previous work and apply the sampling operator to the error analysis in both the RKHS norm and the L² norm. The tool for estimating the sample error is a Bennet inequality for random variables with values in Hilbert spaces. By taking the Hilbert space to be the one consisting of Hilbert-Schmidt operators in the RKHS, we improve the error bounds in the L² metric, motivated by an idea of Caponnetto and de Vito. The error bounds we derive in the RKHS norm, together with a Tsybakov function we discuss here, yield interesting applications to the error analysis of the (binary) classification problem, since the RKHS metric controls the one for the uniform convergence.     

Time shifted aliasing error upper bounds for truncated sampling cardinal series

Time shifted aliasing error upper bound extremals for the sampling reconstruction procedure are fully characterized. Sharp upper bounds are found on the aliasing error of truncated cardinal series and the corresponding extremals are described for entire functions from certain specific Lp, p>1, classes. Analogous results are obtained in multidimensional regular sampling. Truncation error analysis is provided in all cases considered. Moreover, sharpness of bounding inequalities, convergence rates and various sufficient conditions are discussed.     

Aliasing Effects and Sampling Theorems of Spherical Random Fields when Sampled on a Finite Grid

Aliasing effects are investigated for spherical random fields sampled on a finite grid. Using the spherical harmonics expansion, it is shown that for a band-limited spherical random field its trend and spectrum can be uniquely reconstructed from the sampled field if the sampling points are judiciously designed. Analytical expressions are also obtained for aliasing errors in the trend and the spectrum when the field is not band-limited.     

Higher-order total variation bounds for expectations of periodic functions and simple integer recourse approximations

We derive bounds on the expectation of a class of periodic functions using the total variations of higher-order derivatives of the underlying probability density function. These bounds are a strict improvement over those of Romeijnders et al. (Math Program 157:3–46, 2016b), and we use them to derive error bounds for convex approximations of simple integer recourse models. In fact, we obtain a hierarchy of error bounds that become tighter if the total variations of additional higher-order derivatives are taken into account. Moreover, each error bound decreases if these total variations become smaller. The improved bounds may be used to derive tighter error bounds for convex approximations of more general recourse models involving integer decision variables.     

Explicit error bounds for lazy reversible Markov chain Monte Carlo

We prove explicit, i.e., non-asymptotic, error bounds for Markov Chain Monte Carlo methods, such as the Metropolis algorithm. The problem is to compute the expectation (or integral) of f$f$ with respect to a measure π$\pi$ which can be given by a density ?$?$ with respect to another measure. A straight simulation of the desired distribution by a random number generator is in general not possible. Thus it is reasonable to use Markov chain sampling with a burn-in. We study such an algorithm and extend the analysis of Lovasz and Simonovits [L. Lovász, M. Simonovits, Random walks in a convex body and an improved volume algorithm, Random Structures Algorithms 4 (4) (1993) 359–412] to obtain an explicit error bound.     

A Modification of Hermite Sampling with a Gaussian Multiplier

The Hermite sampling series is used to approximate bandlimited functions. In this article, we introduce two modifications of Hermite sampling with a Gaussian multiplier to approximate bandlimited and non-bandlimited functions. The convergence rate of those modifications is much higher than the convergence rate of Hermite sampling. Based on complex analysis, we establish some error bounds for approximating different classes of functions by these modifications. Theoretically and numerically, we demonstrate that the approximation by these modifications is highly efficient.     

Equivalent Optimization Formulations and Error Bounds for Variational Inequality Problems

We investigate whether some merit functions for variational inequality problems (VIP) provide error bounds for the underlying VIP. Under the condition that the involved mapping F is strongly monotone, but not necessarily Lipschitz continuous, we prove that the so-called regularized gap function provides an error bound for the underlying VIP. We give also an example showing that the so-called D-gap function might not provide error bounds for a strongly monotone VIP.This research was supported by United College and by a direct grant of the Chinese University of Hong Kong. The authors thank the referees for helpful comments and suggestions.     

Regularized Kernel-Based Reconstruction in Generalized Besov Spaces

We present a theoretical framework for reproducing kernel-based reconstruction methods in certain generalized Besov spaces based on positive, essentially self-adjoint operators. An explicit representation of the reproducing kernel is given in terms of an infinite series. We provide stability estimates for the kernel, including inverse Bernstein-type estimates for kernel-based trial spaces, and we give condition estimates for the interpolation matrix. Then, a deterministic error analysis for regularized reconstruction schemes is presented by means of sampling inequalities. In particular, we provide error bounds for a regularized reconstruction scheme based on a numerically feasible approximation of the kernel. This allows us to derive explicit coupling relations between the series truncation, the regularization parameters and the data set.     

Interpolation Wavelets in Boundary Value Problems

We propose and validate a simple numerical method that finds an approximate solution with any given accuracy to the Dirichlet boundary value problem in a disk for a homogeneous equation with the Laplace operator. There are many known numerical methods that solve this problem, starting with the approximate calculation of the Poisson integral, which gives an exact representation of the solution inside the disk in terms of the given boundary values of the required functions. We employ the idea of approximating a given 2π-periodic boundary function by trigonometric polynomials, since it is easy to extend them to harmonic polynomials inside the disk so that the deviation from the required harmonic function does not exceed the error of approximation of the boundary function. The approximating trigonometric polynomials are constructed by means of an interpolation projection to subspaces of a multiresolution analysis (approximation) with basis 2π-periodic scaling functions (more exactly, their binary rational compressions and shifts). Such functions were constructed by the authors earlier on the basis of Meyer-type wavelets; they are either orthogonal and at the same time interpolating on uniform grids of the corresponding scale or only interpolating. The bounds on the rate of approximation of the solution to the boundary value problem are based on the property ofMeyer wavelets to preserve trigonometric polynomials of certain (large) orders; this property was used for other purposes in the first two papers listed in the references. Since a numerical bound of the approximation error is very important for the practical application of the method, a considerable portion of the paper is devoted to this issue, more exactly, to the explicit calculation of the constants in the order bounds of the error known earlier.     

Error estimates for scattered data interpolation on spheres

We study Sobolev type estimates for the approximation order resulting from using strictly positive definite kernels to do interpolation on the -sphere. The interpolation knots are scattered. Our approach partly follows the general theory of Golomb and Weinberger and related estimates. These error estimates are then based on series expansions of smooth functions in terms of spherical harmonics. The Markov inequality for spherical harmonics is essential to our analysis and is used in order to find lower bounds for certain sampling operators on spaces of spherical harmonics.

     

Truncation error estimates for generalized Hermite sampling

The generalized Hermite sampling uses samples from the function itself and its derivatives up to order r. In this paper, we investigate truncation error estimates for the generalized Hermite sampling series on a complex domain for functions from Bernstein space. We will extend some known techniques to derive those estimates and the bounds of Jagerman (SIAM J. Appl. Math. 14, 714–723 1966), Li (J. Approx. Theory 93, 100–113 1998), Annaby-Asharabi (J. Korean Math. Soc. 47, 1299–1316 2010), and Ye and Song (Appl. Math. J. Chinese Univ. 27, 412–418 2012) will be special cases for our results. Some examples with tables and figures are given at the end of the paper.     

Numerical inversion of a class of characteristic functions

In this paper a simple method is proposed to invert numerically a given characteristic function of an absolutely continuous distribution function. The method is based on Fourier series expansions. Exact error bounds are given and a few examples are discussed.     

On Uniform Global Error Bounds for Convex Inequalities

This paper studies the existence of a uniform global error bound when a convex inequality g 0, where g is a closed proper convex function, is perturbed. The perturbation neighborhoods are defined by small arbitrary perturbations of the epigraph of its conjugate function. Under certain conditions, it is shown that for sufficiently small arbitrary perturbations the perturbed system is solvable and there exists a uniform global error bound if and only if g satisfies the Slater condition and the solution set is bounded or its recession function satisfies the Slater condition. The results are used to derive lower bounds on the distance to ill-posedness.     

A unified approach to error bounds for structured convex optimization problems

Error bounds, which refer to inequalities that bound the distance of vectors in a test set to a given set by a residual function, have proven to be extremely useful in analyzing the convergence rates of a host of iterative methods for solving optimization problems. In this paper, we present a new framework for establishing error bounds for a class of structured convex optimization problems, in which the objective function is the sum of a smooth convex function and a general closed proper convex function. Such a class encapsulates not only fairly general constrained minimization problems but also various regularized loss minimization formulations in machine learning, signal processing, and statistics. Using our framework, we show that a number of existing error bound results can be recovered in a unified and transparent manner. To further demonstrate the power of our framework, we apply it to a class of nuclear-norm regularized loss minimization problems and establish a new error bound for this class under a strict complementarity-type regularity condition. We then complement this result by constructing an example to show that the said error bound could fail to hold without the regularity condition. We believe that our approach will find further applications in the study of error bounds for structured convex optimization problems.     

Truncation and aliasing errors for Whittaker-Kotelnikov-Shannon sampling expansion

Let B _?? ^p , 1 ?? p < ??, be the space of all bounded functions from L _p (?) which can be extended to entire functions of exponential type ??. The uniform error bounds for truncated Whittaker-Kotelnikov-Shannon series based on local sampling are derived for functions f ?? B _?? ^p without decay assumption at infinity. Then the optimal bounds of the aliasing error and truncation error of Whittaker-Kotelnikov-Shannon expansion for non-bandlimited functions from Sobolev classes U(W _p ^r (?)) are determined up to a logarithmic factor.