Approximation of Gaussian Random Fields: General Results and Optimal Wavelet Representation of the Lévy Fractional Motion

We investigate the approximation rate for certain centered Gaussian fields by a general approach. Upper estimates are proved in the context of so–called Hölder operators and lower estimates follow from the eigenvalue behavior of some related self–adjoint integral operator in a suitable L ₂(μ)–space. In particular, we determine the approximation rate for the Lévy fractional Brownian motion X _H with Hurst parameter H∈(0,1), indexed by a self–similar set T?? ^N of Hausdorff dimension D. This rate turns out to be of order n ^?H/D (log?n)^1/2. In the case T=[0,1] ^N we present a concrete wavelet representation of X _H leading to an approximation of X _H with the optimal rate n ^?H/N (log?n)^1/2.     

Integral approximation of the characteristic function of an interval by trigonometric polynomials

We prove that the value E _n?1(χ _h ) _L of the best integral approximation of the characteristic function χ _h of an interval (?h, h) on the period [?π,π) by trigonometric polynomials of degree at most n ? 1 is expressed in terms of zeros of the Bernstein function cos {nt ? arccos[(2q ? (1 + q ²) cost)/(1 + q ² ? 2q cost)]}, t ∈ [0, π], q ∈ (?1,1). Here, the parameters q, h, and n are connected in a special way; in particular, q = sech ? tanh for h = π/n.     

Improved Approximation for Guarding Simple Galleries from the Perimeter

We provide an O(log?log?opt)-approximation algorithm for the problem of guarding a simple polygon with guards on the perimeter. We first design a polynomial-time algorithm for building ε-nets of size \(O(\frac{1}{\varepsilon}\log\log\frac{1}{\varepsilon})\) for the instances of Hitting Set associated with our guarding problem. We then apply the technique of Brönnimann and Goodrich to build an approximation algorithm from this ε-net finder. Along with a simple polygon P, our algorithm takes as input a finite set of potential guard locations that must include the polygon’s vertices. If a finite set of potential guard locations is not specified, e.g., when guards may be placed anywhere on the perimeter, we use a known discretization technique at the cost of making the algorithm’s running time potentially linear in the ratio between the longest and shortest distances between vertices. Our algorithm is the first to improve upon O(log?opt)-approximation algorithms that use generic net finders for set systems of finite VC-dimension.     

Linear and nonlinear methods of relief approximation

In this paper, we compare the effectiveness of free (nonlinear) relief approximation, equidistant relief approximation, and polynomial approximation {ie129-01}, and {ie129-02} of an individual function ?(x) in the metric {ie129-03}, where {ie129-04} is the unit ball |x| ≤ 1 in the plane ?². The notation we use is the following: {fx129-01}. Here {ie129-05} is the set of all N-term linear combinations of functions of the plane-wave type {fx129-02} with arbitrary profiles W _j (x), x ∈ ?¹ and transmission directions {θ _j } ₁ ^N ; {ie129-06} is the subset of {ie129-07} associated with N equidistant directions; {fx129-03} denotes the subspace of algebraic polynomials of degree less than or equal to N ? 1 in two real variables. Obviously, the inequalities {ie129-08} hold.We state the following model problem. What are the functions which satisfy the relation {ie129-09}, i.e., where the nonlinear approximation {ie129-10} is more effective than a linear one? This effect has been proved for harmonic functions, namely, for any ε > 0 there exists c _ε > 0 such that if Δ?(x) = 0, |x| < 1, and ? ∈ {ie129-11}, then {fx129-04}. On the other hand, {ie129-12}. Thus, {ie129-13} has an “almost squared effectiveness” of {ie129-14} for ? = ?_harm. However, this ultra-high order of approximation is obtained via a collapse of wave vectors.On the other hand, the nonlinearity of {ie129-15} which corresponds to the freedom of choice of wave vectors does not much improve the order of approximation, for instance, for all the radial functions. If {ie129-16}, then {ie129-17} and {ie129-18}.The technique we use is the Fourier-Chebyshev analysis (which is related to the inverse Radon transform on {ie129-19}) and a duality between the relief approximation problem and the optimization of quadrature formulas in the sense of Kolmogorov-Nikolskii [14] for trigonometric polynomial classes.     

On homogenization for non-self-adjoint locally periodic elliptic operators

In this note we consider the homogenization problem for a matrix locally periodic elliptic operator on R ^d of the form A ^ε = ?divA(x, x/ε)?. The function A is assumed to be Hölder continuous with exponent s ∈ [0, 1] in the “slow” variable and bounded in the “fast” variable. We construct approximations for (A ^ε ? μ)^?1, including one with a corrector, and for (?Δ) ^s/2(A ^ε ? μ)^?1 in the operator norm on L ₂(R ^d ) ⁿ . For s ≠ 0, we also give estimates of the rates of approximation.     

An improved approximation algorithm for the <Emphasis Type="Italic">k</Emphasis>-level facility location problem with soft capacities

We consider the k-level facility location problem with soft capacities (k-LFLPSC). In the k-LFLPSC, each facility i has a soft capacity u _i along with an initial opening cost f _i ≥ 0, i.e., the capacity of facility i is an integer multiple of u _i incurring a cost equals to the corresponding multiple of f _i . We firstly propose a new bifactor (ln(1/β)/(1 ?β),1+2/(1 ?β))-approximation algorithm for the k-level facility location problem (k-LFLP), where β ∈ (0, 1) is a fixed constant. Then, we give a reduction from the k-LFLPSC to the k-LFLP. The reduction together with the above bifactor approximation algorithm for the k-LFLP imply a 5.5053-approximation algorithm for the k-LFLPSC which improves the previous 6-approximation.     

Spectral properties of the complex airy operator on the half-line

We prove a theorem on the completeness of the system of root functions of the Schrödinger operator L = ?d ²/dx ² + p(x) on the half-line R₊ with a potential p for which L appears to be maximal sectorial. An application of this theorem to the complex Airy operator L _c = ?d ²/dx ² + cx, c = const, implies the completeness of the system of eigenfunctions of L _c for the case in which |arg c| < 2π/3.We use subtler methods to prove a theorem stating that the system of eigenfunctions of this special operator remains complete under the condition that |arg c| < 5π/6.     

On Homogenization for Non-Self-Adjoint Periodic Elliptic Operators on an Infinite Cylinder

We consider an operator A^ε on L₂(\({\mathbb{R}^{{d_1}}} \times {T^{{d_2}}}\)) (d₁ is positive, while d₂ can be zero) given by A^ε = ?div A(ε^?1x₁,x₂)?, where A is periodic in the first variable and smooth in a sense in the second. We present approximations for (A^ε ? μ)^?1 and ?(A^ε ? μ)^?1 (with appropriate μ) in the operator norm when ε is small. We also provide estimates for the rates of approximation that are sharp with respect to the order.     

Approximation by Linear Fractional Transformations of Simple Partial Fractions and Their Differences

Let f be a function and ρ be a simple partial fraction of degree at most n. Under linear-fractional transformations, the difference f ? ρ becomes the difference of another function and a certain simple partial fraction of degree at most n with a quadratic weight. We study applications of this important property. We prove a theorem on uniqueness of interpolating simple partial fraction, generalizing known results, and obtain estimates for the best uniform approximation of certain functions on the real semi-axis ?⁺. For continuous functions of rather common type we first obtain estimates of the best approximation by differences of simple partial fractions on ?⁺. For odd functions we obtain such estimates on the whole axis ?.     

Nonmatricial version of the Arveson-Wittstock extension principle,and its generalization

We consider the algebra ? = ?(H) of bounded operators in a Hilbert space H, ?-bimodules, and morphisms of these bimodules into the algebra ?(L ? H), where L is a Hilbert space. We study the problem of extension of a morphism defined on a sub-?-bimodule Y ? Z to Z. This problem is solved for Ruan bimodules.     

Variational Approximation for Fokker–Planck Equation on Riemannian Manifold

Under the bounded geometry assumption on Riemannian manifold M, a variational approximation for Fokker–Planck equation on M is constructed by the scheme of Jordan et al. in SIAM J Math Anal 29(1):1–17, 1998. Moreover, the uniqueness and global L ^p -estimate of the solution for 1 < p < dim(M)/(dim(M) ? 1) are obtained for a broad class of potential.     

On a result by geronimus

In 1935, Ya.L. Geronimus found the best integral approximation on the period [?π,π) of the function sin(n + 1)t ? 2q sin nt, q ∈ ?, by the subspace of trigonometric polynomials of degree at most n ? 1. This result is an integral analog of the known theorem by E.I. Zolotarev (1868). At present, there are several methods of proving this fact. We propose one more variant of the proof. In the case |q| ≥ 1, we apply the (2π/n)-periodization and the fact that the function | sin nt| is orthogonal to the harmonic cos t on the period. In the case |q| < 1, we use the duality relations for Chebyshev’s theorem (1859) on a rational function least deviating from zero on a closed interval with respect to the uniform metric.     

An Algorithm for Approximating the Second Moment of the Normalizing Constant Estimate from a Particle Filter

We propose a new algorithm for approximating the non-asymptotic second moment of the marginal likelihood estimate, or normalizing constant, provided by a particle filter. The computational cost of the new method is O(M) per time step, independently of the number of particles N in the particle filter, where M is a parameter controlling the quality of the approximation. This is in contrast to O(M N) for a simple averaging technique using M i.i.d. replicates of a particle filter with N particles. We establish that the approximation delivered by the new algorithm is unbiased, strongly consistent and, under standard regularity conditions, increasing M linearly with time is sufficient to prevent growth of the relative variance of the approximation, whereas for the simple averaging technique it can be necessary to increase M exponentially with time in order to achieve the same effect. This makes the new algorithm useful as part of strategies for estimating Monte Carlo variance. Numerical examples illustrate performance in the context of a stochastic Lotka–Volterra system and a simple AR(1) model.     

Equiconvergence of the trigonometric Fourier series and the expansion in eigenfunctions of the Sturm-Liouville operator with a distribution potential

We consider the Sturm-Liouville operator L = ?d ²/dx ² + q(x) with the Dirichlet boundary conditions in the space L ₂[0, π] under the assumption that the potential q(x) belongs to W ₂ ^?1 [0, π]. We study the problem of uniform equiconvergence on the interval [0, π] of the expansion of a function f(x) in the system of eigenfunctions and associated functions of the operator L and its Fourier sine series expansion. We obtain sufficient conditions on the potential under which this equiconvergence holds for any function f(x) of class L ₁. We also consider the case of potentials belonging to the scale of Sobolev spaces W ₂ ^?θ [0, π] with ½ < θ ≤ 1. We show that if the antiderivative u(x) of the potential belongs to some space W ₂ ^θ [0, π] with 0 < θ < 1/2, then, for any function in the space L ₂[0, π], the rate of equiconvergence can be estimated uniformly in a ball lying in the corresponding space and containing u(x). We also give an explicit estimate for the rate of equiconvergence.     

Riesz transform characterization of Hardy spaces associated with Schrödinger operators with compactly supported potentials

Let L=?Δ+V be a Schrödinger operator on ? ^d , d≥3. We assume that V is a nonnegative, compactly supported potential that belongs to L ^p (? ^d ), for some p>d /2. Let K _t be the semigroup generated by ?L. We say that an L ¹(? ^d )-function f belongs to the Hardy space \(H^{1}_{L}\) associated with L if sup?_t>0|K _t f| belongs to L ¹(? ^d ). We prove that \(f\in H^{1}_{L}\) if and only if R _j f∈L ¹(? ^d ) for j=1,…,d, where R _j =(?/? x _j )L ^?1/2 are the Riesz transforms associated with L.     

On the complexity of the gradient of a rational function

The Baur-Strassen method implies L(?f) ? 4L(f), where L(f) is the complexity of computing a rational function f by arithmetic circuits, and ?f is the gradient of f. We show that L(? f) ? 3L(f) + n, where n is the number of variables in f. In addition, the depth of a circuit for the gradient is estimated.     

Equiconvergence of spectral decompositions for the Dirac system with potential in Lebesgue spaces

The problem of equiconvergence of spectral decompositions corresponding to the systems of root functions of two one-dimensional Dirac operators ?_P,U and ?_0,U with potential P summable on a finite interval and Birkhoff-regular boundary conditions is analyzed. It is proved that in the case of P ∈ L_?[0, π], ? ∈ (1,∞], equiconvergence holds for every function f ∈ L_μ[0, π], μ ∈ [1,∞], in the norm of the space L_ν[0, π], ν ∈ [1,∞], if the indices ?, μ, and ν satisfy the inequality 1/? + 1/μ ? 1/ν ≤ 1 (except for the case when ? = ν = ∞ and μ = 1). In particular, in the case of a square summable potential, the uniform equiconvergence on the interval [0, π] is proved for an arbitrary function f ∈ L₂[0, π].     

On the Distribution of Zero Sets of Holomorphic Functions

Let M be a subharmonic function with Riesz measure ν _M in a domain D in the n-dimensional complex Euclidean space ? _n , and let f be a nonzero function that is holomorphic in D, vanishes on a set Z ? D, and satisfies |f| ? expM on D. Then restrictions on the growth of ν _M near the boundary of D imply certain restrictions on the dimensions or the area/volume of Z. We give a quantitative study of this phenomenon in the subharmonic framework.     

Inner and outer approximation of convex sets using alignment

We show that there exists, for each closed bounded convex set C in the Euclidean plane with nonempty interior, a quadrangle Q having the following two properties. Its sides support C at the vertices of a rectangle r and at least three of the vertices of Q lie on the boundary of a rectangle R that is a dilation of r with ratio 2. We will prove that this implies that quadrangle Q is contained in rectangle R and that, consequently, the inner approximation r of C has an area of at least half the area of the outer approximation Q of C. The proof makes use of alignment or Schüttelung, an operation on convex sets.     

Rational integrability of trigonometric polynomial potentials on the flat torus

We consider a lattice ? ? ? ⁿ and a trigonometric potential V with frequencies k ∈ ?. We then prove a strong rational integrability condition on V, using the support of its Fourier transform. We then use this condition to prove that a real trigonometric polynomial potential is rationally integrable if and only if it separates up to rotation of the coordinates. Removing the real condition, we also make a classification of rationally integrable potentials in dimensions 2 and 3 and recover several integrable cases. After a complex change of variables, these potentials become real and correspond to generalized Toda integrable potentials. Moreover, along the proof, some of them with high-degree first integrals are explicitly integrated.