Estimation of dimension functions of band-limited wavelets

The dimension function D_ψ of a band-limited wavelet ψ is bounded by n if its Fourier transform is supported in [−(2ⁿ⁺²/3)π,(2ⁿ⁺²/3)π]. For each and for each , 0<<δ=δ(n), we construct a wavelet ψ with supp

Full-size image

such that D_ψ>n on a set of positive measure, which proves that [−(2ⁿ⁺²/3)π,(2ⁿ⁺²/3)π] is the largest symmetric interval for estimating the dimension function by n. This construction also provides a family of (uncountably many) wavelet sets each consisting of infinite number of intervals.     

Theorems about the attractor for incompressible non-Newtonian flow driven by external forces that are rapidly oscillating in time but have a smooth average

This paper discusses the incompressible non-Newtonian fluid with rapidly oscillating external forces g(x,t)=g(x,t,t/) possessing the average g⁰(x,t) as →0⁺, where 0<₀<1. Firstly, with assumptions (A₁)–(A₅) on the functions g(x,t,ξ) and g⁰(x,t), we prove that the Hausdorff distance between the uniform attractors and in space H, corresponding to the oscillating equations and the averaged equation, respectively, is less than O() as →0⁺. Then we establish that the Hausdorff distance between the uniform attractors and in space V is also less than O() as →0⁺. Finally, we show for each [0,₀].     

Approximate range searching using binary space partitions

We show how any BSP tree for the endpoints of a set of n disjoint segments in the plane can be used to obtain a BSP tree of size for the segments themselves, such that the range-searching efficiency remains almost the same. We apply this technique to obtain a BSP tree of size O(nlogn) such that -approximate range searching queries with any constant-complexity convex query range can be answered in O(min_>0{(1/)+k}logn) time, where k is the number of segments intersecting the -extended range. The same result can be obtained for disjoint constant-complexity curves, if we allow the BSP to use splitting curves along the given curves.We also describe how to construct a linear-size BSP tree for low-density scenes consisting of n objects in such that -approximate range searching with any constant-complexity convex query range can be done in O(logn+min_>0{(1/^d−1)+k}) time.     

Inscribing an axially symmetric polygon and other approximation algorithms for planar convex sets

Given a planar convex set C, we give sublinear approximation algorithms to determine approximations of the largest axially symmetric convex set S contained in C, and the smallest such set S^′ that contains C. More precisely, for any >0, we find an axially symmetric convex polygon QC with area |Q|>(1−)|S| and we find an axially symmetric convex polygon Q^′ containing C with area |Q^′|<(1+)|S^′|. We assume that C is given in a data structure that allows to answer the following two types of query in time T_C: given a direction u, find an extreme point of C in direction u, and given a line ℓ, find C∩ℓ. For instance, if C is a convex n-gon and its vertices are given in a sorted array, then T_C=O(logn). Then we can find Q and Q^′ in time O(^−1/2T_C+^−3/2). Using these techniques, we can also find approximations to the perimeter, area, diameter, width, smallest enclosing rectangle and smallest enclosing circle of C in time O(^−1/2T_C).     

A note on perturbation of non-symmetric Dirichlet forms by signed smooth measures

This article discusses the perturbation of a non-symmetric Dirichlet form,(ε, D(ε)), by a signed smooth measure μ, whereμ=μ1 -μ2 with μ1 and μ2 being smooth measures. It gives a sufficient condition for the perturbed form (εμ, D(εμ)) (for some αo ≥ 0) to be a coercive closed form.     

Maximal Inequalities and Lebesgue's Differentiation Theorem for Best Approximant by Constant over Balls

For fL_p( ⁿ), with 1p<∞, >0 and x ⁿ we denote by T(f)(x) the set of every best constant approximant to f in the ball B(x, ). In this paper we extend the operators T_p to the space L_p−1( ⁿ)+L_∞( ⁿ), where L₀ is the set of every measurable functions finite almost everywhere. Moreover we consider the maximal operators associated to the operators T_p and we prove maximal inequalities for them. As a consequence of these inequalities we obtain a generalization of Lebesgue's Differentiation Theorem.     

Lattice-Nyström method for Fredholm integral equations of the second kind with convolution type kernels

We consider Fredholm integral equations of the second kind of the form , where g and k are given functions from weighted Korobov spaces. These spaces are characterized by a smoothness parameter α>1 and weights γ₁≥γ₂≥. The weight γ_j moderates the behavior of the functions with respect to the jth variable. We approximate f  by the Nyström method using n rank-1 lattice points. The combination of convolution and lattice group structure means that the resulting linear system can be solved in O(nlogn) operations. We analyze the worst case error measured in sup norm for functions g in the unit ball and a class of functions k in weighted Korobov spaces. We show that the generating vector of the lattice rule can be constructed component-by-component to achieve the optimal rate of convergence O(n^-α/2+δ), δ>0, with the implied constant independent of the dimension d under an appropriate condition on the weights. This construction makes use of an error criterion similar to the worst case integration error in weighted Korobov spaces, and the computational cost is only O(nlognd) operations. We also study the notion of QMC-Nyström tractability: tractability means that the smallest n needed to reduce the worst case error (or normalized error) to is bounded polynomially in ^-1 and d; strong tractability means that the bound is independent of d. We prove that strong QMC-Nyström tractability in the absolute sense holds iff , and QMC-Nyström tractability holds in the absolute sense iff .     

A note on asymptotic behavior for negative drift random walk with dependent heavy-tailed steps and its application to risk theory

In this article, the dependent steps of a negative drift random walk are modelled as a two-sided linear process Xn =-μ ∞∑j=-∞ψn-jεj, where {ε, εn; -∞＜ n ＜ ∞}is a sequence of independent, identically distributed random variables with zero mean, μ＞0 is a constant and the coefficients {ψi;-∞＜ i ＜∞} satisfy 0 ＜∞∑j=-∞|jψj| ＜∞. Under the conditions that the distribution function of |ε| has dominated variation and ε satisfies certain tail balance conditions, the asymptotic behavior of P{supn≥0(-nμ ∞∑j=-∞εjβnj) ＞ x}is discussed. Then the result is applied to ultimate ruin probability.     

Attractors of the reaction-diffusion systems with rapidly oscillating coefficients and their homogenization

The following reaction-diffusion system in spatially non-homogeneous almost-periodic media is considered in a bounded domain : (1)∂_tu=Au−f(u)+g, u|_∂Ω=0. Here u=(u¹,…,u^k) is an unknown vector-valued function, f is a given nonlinear interaction function and the second order elliptic operator A has the following structure: where a_ij^l(y) are given almost-periodic functions. We prove that, under natural assumptions on the nonlinear term f(u), the longtime behavior of solutions of (1) can be described in terms of the global attractor of the associated dynamical system and that the attractors  , 0<<₀1, converge to the attractor of the homogenized problem (1) as →0. Moreover, in the particular case of periodic media, we give explicit estimates for the distance between the non-homogenized and the homogenized attractors in terms of the parameter .     

A (2 + )-Approximation Scheme for Minimum Domination on Circle Graphs

The main result of this paper is a (2 + )-approximation scheme for the minimum dominating set problem on circle graphs. We first present an O(n²) time 8-approximation algorithm for this problem and then extend it to an time (2 + )-approximation scheme for this problem. Here n and m are the number of vertices and the number of edges of the circle graph. We then present simple modifications to this algorithm that yield (3 + )-approximation schemes for the minimum connected and the minimum total dominating set problems on circle graphs. Keil (1993, Discrete Appl. Math.42, 51–63) shows that these problems are NP-complete for circle graphs and leaves open the problem of devising approximation algorithms for them. These are the first O(1)-approximation algorithms for domination problems on circle graphs.     

Entropy of C(K)-Valued Operators

We investigate how the entropy numbers (e_n(T)) of an arbitrary Hölder-continuous operator T: E→C(K) are influenced by the entropy numbers (_n(K)) of the underlying compact metric space K and the geometry of E. We derive diverse universal inequalities relating finitely many _n(K)'s with finitely many e_n(T)'s which yield statements about the asymptotically optimal behaviour of the sequence (e_n(T)) in terms of the sequence (_n(K)). As an application we present new methods for estimating the entropy numbers of a precompact and convex subset in a Banach space E, provided that the entropy numbers of its extremal points are known.     

A nonlinear oblique derivative boundary value problem for the heat equation Part 2: Singular self-similar solutions

This paper continues the study started in [12]. In the upper half-plane, consider the elliptic equation

Full-size image

, submitted to the nonlinear oblique derivative boundary condition U_x = UU_z on the axis x = 0. The solution of this problem appears to be the self-similar solution of the heat equation with the same boundary condition. As goes to 0, the function U converges to the non trivial solution U of the corresponding degenerate problem. Moreover there exists z₀ > 0 such that U vanishes for z ≥ z₀, is C^∞ on ]0, z₀[× ₊, is continuous on the boundary x = 0 and is discontinuous on the half-axis {z = 0, x> 0}.     

A note on two fixed point problems

We extend the applicability of the Exterior Ellipsoid Algorithm for approximating n-dimensional fixed points of directionally nonexpanding functions. Such functions model many practical problems that cannot be formulated in the smaller class of globally nonexpanding functions. The upper bound 2n²ln(2/) on the number of function evaluations for finding -residual approximations to the fixed points remains the same for the larger class. We also present a modified version of a hybrid bisection-secant method for efficient approximation of univariate fixed point problems in combustion chemistry.     

Enumeration and limit laws for series–parallel graphs

We show that the number g_n of labelled series–parallel graphs on n vertices is asymptotically g_ngn^−5/2γⁿn!, where γ and g are explicit computable constants. We show that the number of edges in random series–parallel graphs is asymptotically normal with linear mean and variance, and that it is sharply concentrated around its expected value. Similar results are proved for labelled outerplanar graphs and for graphs not containing K_2,3 as a minor.     

Estimation of Linear Error-in-Covariables Models with Validation Data Under Random Censorship

Consider the linear models of the form Y=X^τβ+ with the response Y censored randomly on the right and X measured erroneously. Without specifying any error models, in this paper, a semiparametric method is applied to the estimation of the parametric vector β with the help of proper validation data. For the proposed estimator, an asymptotic representation is established and the asymptotic normality is also proved.     

Interlacing and spacing properties of zeros of polynomials, in particular of orthogonal and -minimal polynomials,

Let be a sequence of polynomials with real coefficients such that uniformly for [α-δ,β+δ] with G(eⁱ)≠0 on [α,β], where 0α<βπ and δ>0. First it is shown that the zeros of are dense in [α,β], have spacing of precise order π/n and are interlacing with the zeros of p_n+1(cos) on [α,β] for every nn₀. Let be another sequence of real polynomials with uniformly on [α-δ,β+δ] and on [α,β]. It is demonstrated that for all sufficiently large n the zeros of p_n(cos) and strictly interlace on [α,β] if on [α,β]. If the last expression is zero then a weaker kind of interlacing holds. These interlacing properties of the zeros are new for orthogonal polynomials also. For instance, for large n a simple criteria for interlacing of zeros of Jacobi polynomials on [-1+,1-], >0, is obtained. Finally it is shown that the results hold for wide classes of weighted L_q-minimal polynomials, q[1,∞], linear combinations and products of orthogonal polynomials, etc.     

The maximum asymptotic bias of S-estimates for regression over the neighborhoods defined by certain special capacities

The maximum asymptotic bias of an S-estimate for regression in the linear model is evaluated over the neighborhoods (called (c,γ)-neighborhoods) defined by certain special capacities, and its lower and upper bounds are derived. As special cases, the (c,γ)-neighborhoods include those in terms of -contamination, total variation distance and Rieder's (,δ)-contamination. It is shown that when the model distribution is normal and the (,δ)-contamination neighborhood is adopted, the lower and upper bounds of an S-estimate (including the LMS-estimate) based on a jump function coincide with the maximum asymptotic bias. The tables of the maximum asymptotic bias of the LMS-estimate are given. These results are an extension of the corresponding ones due to Martin et al. (Ann. Statist. 17 (1989) 1608), who used -contamination neighborhoods.     

Deformation of Minimal Polynomials and Approximation of Several Intervals by an Inverse Polynomial Mapping

In this paper we show that for a given set of l real disjoint intervals E_l=^l_j=1 [a_2j−1, a_2j] and given >0 there exists a real polynomial and a set of l disjoint intervals E_l=^l_j=1 [ã_2j−1, ã_2j] with E_lE_l and (ã₁, …, ã_2l)−(a₁, …, a_2l)_max<, such that ⁻¹([−1, 1])=E_l. The statement follows by showing how to get in a constructive way by a continuous deformation procedure from a minimal polynomial on E_l with respect to the maximum norm a polynomial mapping of E_l.     

A polynomial time approximation scheme for the two-source minimum routing cost spanning trees

Let G be an undirected graph with nonnegative edge lengths. Given two vertices as sources and all vertices as destinations, we investigated the problem how to construct a spanning tree of G such that the sum of distances from sources to destinations is minimum. In the paper, we show the NP-hardness of the problem and present a polynomial time approximation scheme. For any >0, the approximation scheme finds a (1+)-approximation solution in O(n^1/+1) time. We also generalize the approximation algorithm to the weighted case for distances that form a metric space.     

Wilson's functional equation on C

Summary We find the complete set of continuous solutionsf, g of Wilson's functional equation _{n = 0} ^{N – 1} f(x + wⁿy) = Nf(x)g(y), x, y C, given a primitiveN ^th rootw of unity.Disregarding the trivial solutionf = 0 andg any complex function, it is known thatg satisfies a version of d'Alembert's functional equation and so has the formg(z) = g (z) = N^–1 _{n = 0} ^{N – 1} E(wⁿz) for some C². HereE ₍₁, ₂)(x + iy) = exp( ₁x + ₂).For fixedg = g the space of solutionsf of Wilson's functional equation can be decomposed into theN isotypic subspaces for the action of Z _N on the continuous functions on C. We prove that ther ^th component, wherer {0, 1, ,N – 1}, of any solution satisfies the signed functional equation _{n = 0} ^{N – 1} f(x + wⁿy)w^nr = Ng(x)f(y), x, y C. We compute the solution spaces of each of these signed equations: They are 1-dimensional and spanned byz _{n = 0} ^{N – 1} w^nr E(wⁿz), except forg = 1 andr 0 where they are spanned by andz ^{N – r}. Adding the components we get the solution of Wilson's equation. Analogous results are obtained with the action ofZ _N on C replaced by that ofSO(2).The case ofg = 0 in the signed equations is special and solved separately both for Z _N andSO(2).