Formulas for approximating pseudo-Boolean random variables

We consider {0,1}ⁿ as a sample space with a probability measure on it, thus making pseudo-Boolean functions into random variables. We then derive explicit formulas for approximating a pseudo-Boolean random variable by a linear function if the measure is permutation-invariant, and by a function of degree at most k if the measure is a product measure. These formulas generalize results due to Hammer-Holzman and Grabisch-Marichal-Roubens. We also derive a formula for the best faithful linear approximation that extends a result due to Charnes-Golany-Keane-Rousseau concerning generalized Shapley values. We show that a theorem of Hammer-Holzman that states that a pseudo-Boolean function and its best approximation of degree at most k have the same derivatives up to order k does not generalize to this setting for arbitrary probability measures, but does generalize if the probability measure is a product measure.     

Approximations of Lovász extensions and their induced interaction index

The Lovász extension of a pseudo-Boolean function f:{0,1}ⁿ→R is defined on each simplex of the standard triangulation of [0,1]ⁿ as the unique affine function that interpolates f at the n+1 vertices of the simplex. Its degree is that of the unique multilinear polynomial that expresses f. In this paper we investigate the least squares approximation problem of an arbitrary Lovász extension by Lovász extensions of (at most) a specified degree. We derive explicit expressions of these approximations. The corresponding approximation problem for pseudo-Boolean functions was investigated by Hammer and Holzman [Approximations of pseudo-Boolean functions; applications to game theory, Z. Oper. Res. 36(1) (1992) 3-21] and then solved explicitly by Grabisch et al. [Equivalent representations of set functions, Math. Oper. Res. 25(2) (2000) 157-178], giving rise to an alternative definition of Banzhaf interaction index. Similarly we introduce a new interaction index from approximations of and we present some of its properties. It turns out that its corresponding power index identifies with the power index introduced by Grabisch and Labreuche [How to improve acts: an alternative representation of the importance of criteria in MCDM, Internat. J. Uncertain. Fuzziness Knowledge-Based Syst. 9(2) (2001) 145-157].     

On solenoidal high‐degree polynomial approximations to solutions of the stationary Stokes equations

The cell discretization algorithm, a nonconforming extension of the finite element method, is used to obtain approximations to the velocity and pressure functions satisfying the Stokes equations. Error estimates show convergence of the method. An implementation using polynomial bases is described that permits the use of the continuous approximations of the h‐p finite element method and exactly satisfies the solenoidal requirement. We express the error estimates in terms of the diameter h of a cell and degree p of the approximation on each cell. Examples of 10^th degree polynomial approximations are described that substantiate the theoretical estimates. © 2000 John Wiley & Sons, Inc. Numer Methods Partial Differential Eq 16: 480–493, 2000     

Approximation of unbounded functions via compactification

Approximants to functions f(s) that are allowed to possess infinite limits on their interval of definition, are constructed.To this end a compactification of Rⁿ is developed which is based on the projection of Rⁿ on a bowl-shaped subset of a parabolic surface. This compactification induces a bijection and a metric with several desirable properties that make it a useful tool for rational approximation of unbounded functions.Roughly speaking this compactification enables us to show that unbounded functions can be approximated by rational functions on a closed interval; thus we also obtain an extension to Weierstrass’ celebrated theorem. An extension to a Fourier-type theorem is also obtained. Roughly speaking, our result states that unbounded periodic functions can be approximated by quotients of certain trigonometric sums. The characteristics of the main results are the following. The approximations do not require the original approximated function to possess a restricted rate of growth. Neither do they require that the approximated function possess any amount of smoothness. Moreover, the numerator and denominator, in an approximating quotient are guaranteed not to vanish simultaneously. Furthermore, some of the proposed approximations are guaranteed to be bounded at every point at which the original approximated function is bounded. Beside the tool of compactification we also employ Bernstein polynomials and Cesaro means of “trigonometric sums”.     

Polynomial approximations in the complex plane

Good polynomial approximations for analytic functions are potentially useful but are in short supply. A new approach introduced here involves the Lanczos τ-method, with perturbations proportional to Faber or Chebyshev polynomials for specific regions of the complex plane. The results show that suitable forms of the τ-method, which are easy to use, can produce near-minimax polynomial approximations for functions which satisfy linear differential equations with polynomial coefficients. In particular, some accurate approximations of low degree for Bessel functions are presented. An appendix describes a simple algorithm which generates polynomial approximations for the Bessel function J_ν(z) of any given order ν.     

Finite-Dimensional Approximations of Operators in the Hilbert Spaces of Functions on Locally Compact Abelian Groups

A new approach to the approximation of operators in the Hilbert space of functions on a locally compact Abelian (LCA) group is developed. This approach is based on sampling the symbols of such operators. To choose the points for sampling, we use the approximations of LCA groups by finite groups, which were introduced and investigated by Gordon. In the case of the group R ⁿ , the constructed approximations include the finite-dimensional approximations of the coordinate and linear momentum operators, suggested by Schwinger. The finite-dimensional approximations of the Schrödinger operator based on Schwinger's approximations were considered by Digernes, Varadarajan, and Varadhan in Rev. Math. Phys. 6 (4) (1994), 621–648 where the convergence of eigenvectors and eigenvalues of the approximating operators to those of the Schrödinger operator was proved in the case of a positive potential increasing at infinity. Here this result is extended to the case of Schrödinger-type operators in the Hilbert space of functions on LCA groups. We consider the approximations of p-adic Schrödinger operators as an example. For the investigation of the constructed approximations, the methods of nonstandard analysis are used.     

A frequency accurate rth order spatial derivative finite difference approximation

A method for the specification and design of finite difference spatial derivative approximations of general order r is presented. The method uses a difference polynomial with undetermined coefficients. Spatial frequency domain‐based criteria, which include phase velocity, group velocity, and dissipation requirements at a priori selected spatial frequencies, are used to find the appropriate coefficient values. The method is formulated as an optimal design problem but is pursued heuristically. The general derivative approximation and the design method are suitable for use in more general design problems involving finite difference schemes for linear and nonlinear partial differential equations. © 1999 John Wiley & Sons, Inc. * Numer Methods Partial Differential Eq 15: 569–580, 1999     

Marcinkiewicz–Zygmund Inequalities and Polynomial Approximation from Scattered Data on SO(3)

We consider scattered data approximation problems on SO(3). To this end, we construct a new operator for polynomial approximation on the rotation group. This operator reproduces Wigner-D functions up to a given degree and has uniformly bounded L ^p -operator norm for all 1 ≤ p ≤ ∞. The operator provides a polynomial approximation with the same approximation degree of the best polynomial approximation. Moreover, the operator together with a Markov type inequality for Wigner-D functions enables us to derive scattered data L ^p -Marcinkiewicz–Zygmund inequalities for these functions for all 1 ≤ p ≤ ∞. As a major application of such inequalities, we consider the stability of the weighted least squares approximation problem on SO(3).     

Error estimates for approximate approximations with Gaussian kernels on compact intervals

The aim of this paper is the investigation of the error which results from the method of approximate approximations applied to functions defined on compact intervals, only. This method, which is based on an approximate partition of unity, was introduced by Maz’ya in 1991 and has mainly been used for functions defined on the whole space up to now. For the treatment of differential equations and boundary integral equations, however, an efficient approximation procedure on compact intervals is needed.In the present paper we apply the method of approximate approximations to functions which are defined on compact intervals. In contrast to the whole space case here a truncation error has to be controlled in addition. For the resulting total error pointwise estimates and L₁-estimates are given, where all the constants are determined explicitly.     

Polynomial operators and local approximation of solutions of pseudo-differential equations on the sphere

We study the solutions of an equation of the form Lu=f, where L is a pseudo-differential operator defined for functions on the unit sphere embedded in a Euclidean space, f is a given function, and u is the desired solution. We give conditions under which the solution exists, and deduce local smoothness properties of u given corresponding local smoothness properties of f, measured by local Besov spaces. We study the global and local approximation properties of the spectral solutions, describe a method to obtain approximate solutions using values of f at points on the sphere and polynomial operators, and describe the global and local rates of approximation provided by our polynomial operators. The research of this author was supported, in part, by grant DMS-0204704 from the National Science Foundation and grant W911NF-04-1-0339 from the U.S. Army Research Office     

Transforms of pseudo-Boolean random variables

As in earlier works, we consider {0,1}ⁿ as a sample space with a probability measure on it, thus making pseudo-Boolean functions into random variables. Under the assumption that the coordinate random variables are independent, we show it is very easy to give an orthonormal basis for the space of pseudo-Boolean random variables of degree at most k. We use this orthonormal basis to find the transform of a given pseudo-Boolean random variable and to answer various least squares minimization questions.     

Plane wave approximation of homogeneous Helmholtz solutions

In this paper, we study the approximation of solutions of the homogeneous Helmholtz equation Δu + ω ² u = 0 by linear combinations of plane waves with different directions. We combine approximation estimates for homogeneous Helmholtz solutions by generalized harmonic polynomials, obtained from Vekua’s theory, with estimates for the approximation of generalized harmonic polynomials by plane waves. The latter is the focus of this paper. We establish best approximation error estimates in Sobolev norms, which are explicit in terms of the degree of the generalized polynomial to be approximated, the domain size, and the number of plane waves used in the approximations.     

Tau method approximation of a generalized Epstein-Hubbell elliptic-type integral

We consider the evaluation of a recent generalization of the Epstein-Hubbell elliptic-type integral using the tau method approximation with a Chebyshev polynomial basis. This also leads to an approximation of Lauricella's hypergeometric function of three variables. Numerical results are given for polynomial approximations of degree 6.

     

A high order projection method for nonlinear two point boundary value problems

Summary Approximations to the solutions of a general class of 2m-th order nonlinear boundary value problems are developed in spaces of polynomial splines of degree 2m+1 by requiring the residual to be orthogonal to a class of polynomial splines of degree 2m–1 over the same mesh. Conditions are given for existence and uniqueness of approximations along with theoretical error rates. In some cases these rates are shown to be of the same order as the best approximation to the solution over the approximating spline spaces. Some computational notes and the results of numerical experiments are also given.     

Near-best multivariate approximation by Fourier series, Chebyshev series and Chebyshev interpolation

A set of results concerning goodness of approximation and convergence in norm is given for L_∞ and L₁ approximation of multivariate functions on hypercubes. Firstly the trigonometric polynomial formed by taking a partial sum of a multivariate Fourier series and the algebraic polynomials formed either by taking a partial sum of a multivariate Chebyshev series of the first kind or by interpolating at a tensor product of Chebyshev polynomial zeros are all shown to be near-best L_∞ approximations. Secondly the trigonometric and algebraic polynomials formed by taking, respectively, a partial sum of a multivariate Fourier series and a partial sum of a multivariate Chebyshev series of the second kind are both shown to be hear-best L₁ approximations. In all the cases considered, the relative distance of a near-best approximation from a corresponding best approximation is shown to be at most of the order of Π log n_j, where n_j (j = 1, 2,…, N) are the respective degrees of approximation in the N individual variables. Moreover, convergence in the relevant norm is established for all the sequences of near-best approximations under consideration, subject to appropriate restrictions on the function space.     

A pseudo-Boolean consensus approach to nonlinear 0–1 optimization

It is proved that any pseudo-Boolean function f can be represented as , where z is the minimum of f and φ is a polynomial with positive coefficients in the original variables x_i and in their complements . A non-constructive proof and a constructive one are given. The latter, which is based on a generalization to pseudo-Boolean functions of the well-known Boolean-theoretical operation of consensus, provides a new algorithm for the minimization of pseudo-Boolean functions.     

Semidefinite representations for finite varieties

We consider the problem of minimizing a polynomial over a set defined by polynomial equations and inequalities. When the polynomial equations have a finite set of complex solutions, we can reformulate this problem as a semidefinite programming problem. Our semidefinite representation involves combinatorial moment matrices, which are matrices indexed by a basis of the quotient vector space ℝ[x ₁, . . . ,x _n ]/I, where I is the ideal generated by the polynomial equations in the problem. Moreover, we prove the finite convergence of a hierarchy of semidefinite relaxations introduced by Lasserre. Semidefinite approximations can be constructed by considering truncated combinatorial moment matrices; rank conditions are given (in a grid case) that ensure that the approximation solves the original problem to optimality. Supported by the Netherlands Organisation for Scientific Research grant NWO 639.032.203.     

On the Problem of Describing Sequences of Best Trigonometric Rational Approximations

For a strictly decreasing sequence a_{n n=0} of nonnegative real numbers converging to zero, we construct a continuous 2-periodic function f such that R^T _n(f) = a_n, n=0,1,2,..., where R^T _n(f) are best approximations of the function f in uniform norm by trigonometric rational functions of degree at most n.     

Approximation of classes of periodic functions with small smoothness

We prove that the approximations of classes of periodic functions with small smoothness in the metrics of the spaces C and L by different linear summation methods for Fourier series are asymptotically equal to the least upper bounds of the best approximations of these classes by trigonometric polynomials of degree not higher than (n - 1). We establish that the Fejér method is asymptotically the best among all positive linear approximation methods for these classes.     

Near-circularity of the error curve in complex Chebyshev approximation

Let f(z) be analytic on the unit disk, and let p^*(z) be the best (Chebyshev) polynomial approximation to f(z) on the disk of degree at most n. It is observed that in typical problems the “error curve,” the image of the unit circle under (f − p^*)(z), often approximates to a startling degree a perfect circle with winding number n + 1. This phenomenon is approached by consideration of related problems whose error curves are exactly circular, making use of a classical theorem of Carathéodory and Fejér. This leads to a technique for calculating approximations in one step that are roughly as close to best as the best approximation error curve is close to circular, and hence to strong theorems on near-circularity as the radius of the domain shrinks to 0 or as n increases to ∞. As a computational example, very tight bounds are given for approximation of e^z on the unit disk. The generality of the near-circularity phenomenon (more general domains, rational approximation) is discussed.