Where does smoothness count the most for Fredholm equations of the second kind with noisy information?

We study the complexity of Fredholm problems (I−T_k)u=f of the second kind on I^d=[0,1]^d, where T_k is an integral operator with kernel k. Previous work on the complexity of this problem has assumed either that we had complete information about k or that k and f had the same smoothness. In addition, most of this work has assumed that the information about k and f was exact. In this paper, we assume that k and f have different smoothness; more precisely, we assume that fW^r,p(I^d) with r>d/p and that kW^s,∞(I^2d) with s>0. In addition, we assume that our information about k and f is contaminated by noise. We find that the nth minimal error is Θ(n^−μ+δ), where μ=min{r/d,s/(2d)} and δ is a bound on the noise. We prove that a noisy modified finite element method has nearly minimal error. This algorithm can be efficiently implemented using multigrid techniques. We thus find tight bounds on the -complexity for this problem. These bounds depend on the cost c(δ) of calculating a δ-noisy information value. As an example, if the cost of a δ-noisy evaluation is proportional to δ^−t, then the -complexity is roughly (1/)^t+1/μ.     

On Sperner families in which no k sets have an empty intersection, II

Let n_c,d(r, k) denote the maximal cardinality of Sperner families (i.e., XY for all X, Y ε ) on an r-element set satisfying c X d for all X ε and in which no k sets have an empty intersection. n_c,d(r, k) was determined by Frankl (J. Combin. Theory Ser. A 20 (1976), 1–11) if c r/k, and, if c = 0 and d = r, by Frankl and the author (J. Combin. Theory Ser. A 28 (1980), 54–63; Acta Cybernet. 4 (1978), 213–220 for all r and k with exception of 60 values of r if k = 3. In this paper we solve the problem of determination of n_c,d(r, 3) in nearly all unknown cases. In particular, we obtain n_0,r(r, 3) for 33 of the exceptional cases.     

An efficient fixed-parameter algorithm for 3-Hitting Set

Given a collection C of subsets of size three of a finite set S and a positive integer k, the 3-Hitting Set problem is to determine a subset S′S with |S′|k, so that S′ contains at least one element from each subset in C. The problem is NP-complete, and is motivated, for example, by applications in computational biology. Improving previous work, we give an O(2.270^k+n) time algorithm for 3-Hitting Set, which is efficient for small values of k, a typical occurrence in some applications. For d-Hitting Set we present an O(c^k+n) time algorithm with c=d−1+O(d⁻¹).     

Moment methods in two point Padé approximation

In the separable Hilbert space (H, ·, ·) the following “operator moment problem” is solved: given a complex sequence (c_k)_{k ε Z} generated by a meromorphic function f, find T ε B(H) and u₀ ε H such that T^ku₀, u₀ = c_k (k ε Z). If the sequence (c_k)_{k ε Z} is “normal,” an adapted form of Vorobyev's method of moments yields a sequence of two point Padé approximants to f. A sufficient condition for convergence of this sequence of approximants is given.     

Distributions of Points in <Emphasis Type="Italic">d</Emphasis> Dimensions and Large <Emphasis Type="Italic">k</Emphasis>-Point Simplices

We consider a variant of Heilbronn’s triangle problem by investigating for a fixed dimension d≥2 and for integers k≥2 with k≤d distributions of n points in the d-dimensional unit cube [0,1] ^d , such that the minimum volume of the simplices, which are determined by (k+1) of these n points is as large as possible. Denoting by Δ _k,d (n), the supremum of this minimum volume over all distributions of n points in [0,1] ^d , we show that c _k,d ⋅(log n)^1/(d−k+1)/n ^k/(d−k+1)≤Δ _k,d (n)≤c _k,d ′/n ^k/d for fixed 2≤k≤d, and, moreover, for odd integers k≥1, we show the upper bound Δ _k,d (n)≤c _k,d ″/n ^{k/d+(k−1)/(2d(d−1))}, where c _k,d ,c _k,d ′,c _k,d ″>0 are constants. A preliminary version of this paper appeared in COCOON ’05.     

On the L convergence of Lagrange interpolating entire functions of exponential type

Let f: be a continuous, 2π-periodic function and for each n ε let t_n(f; ·) denote the trigonometric polynomial of degree n interpolating f in the points 2kπ/(2n + 1) (k = 0, ±1, …, ±n). It was shown by J. Marcinkiewicz that lim_{n → ∞} ∝₀^2π¦f(θ) − t_n(f θ)¦^p dθ = 0 for every p > 0. We consider Lagrange interpolation of non-periodic functions by entire functions of exponential type τ > 0 in the points kπ/τ (k = 0, ± 1, ± 2, …) and obtain a result analogous to that of Marcinkiewicz.     

A self-normalized Erd s—Rényi type strong law of large numbers

The original Erd s—Rényi theorem states that max_0kn∑^k+[clogn]_i=k+1X_i/[clogn]→α(c),c>0, almost surely for i.i.d. random variables {X_n, n1} with mean zero and finite moment generating function in a neighbourhood of zero. The latter condition is also necessary for the Erd s—Rényi theorem, and the function α(c) uniquely determines the distribution function of X₁. We prove that if the normalizing constant [c log n] is replaced by the random variable ∑^k+[clogn]_i=k+1(X²_i+1), then a corresponding result remains true under assuming only the exist first moment, or that the underlying distribution is symmetric.     

The Complexity of Indefinite Elliptic Problems with Noisy Data

We study the complexity of second-order indefinite elliptic problems −div(au) +bu=f(with homogeneous Dirichlet boundary conditions) over ad-dimensional domain Ω, the error being measured in theH¹(Ω)-norm. The problem elementsfbelong to the unit ball ofW^{r, p}, (Ω), wherep [2, ∞] andr>d/p. Information consists of (possibly adaptive) noisy evaluations off,a, orb(or their derivatives). The absolute error in each noisy evaluation is at most δ. We find that thenth minimal radius for this problem is proportional ton^−r/d+ δ and that a noisy finite element method with quadrature (FEMQ), which uses only function values, and not derivatives, is a minimal error algorithm. This noisy FEMQ can be efficiently implemented using multigrid techniques. Using these results, we find tight bounds on the -complexity (minimal cost of calculating an -approximation) for this problem, said bounds depending on the costc(δ) of calculating a δ-noisy information value. As an example, if the cost of a δ-noisy evaluation isc(δ) = δ^−s(fors> 0), then the complexity is proportional to (1/)^{d/r + s}.     

Graceful Signed Graphs

A (p, q)-sigraph S is an ordered pair (G, s) where G = (V, E) is a (p, q)-graph and s is a function which assigns to each edge of G a positive or a negative sign. Let the sets E ⁺ and E ^– consist of m positive and n negative edges of G, respectively, where m + n = q. Given positive integers k and d, S is said to be (k, d)-graceful if the vertices of G can be labeled with distinct integers from the set {0, 1, ..., k + (q – 1)d such that when each edge uv of G is assigned the product of its sign and the absolute difference of the integers assigned to u and v the edges in E ⁺ and E ^– are labeled k, k + d, k + 2d, ..., k + (m – 1)d and –k, – (k + d), – (k + 2d), ..., – (k + (n – 1)d), respectively.In this paper, we report results of our preliminary investigation on the above new notion, which indeed generalises the well-known concept of (k, d)-graceful graphs due to B. D. Acharya and S. M. Hegde.     

Wavelength routing of uniform instances in all-optical rings

We consider the problem of routing uniform communication instances in switched optical rings that use wavelength-division multiplexing technology. A communication instance is called uniform if it consists exactly of all pairs of nodes in the graph whose distance is equal to one from a specified set S={d₁,d₂,…,d_k}. When k=1 or 2, we prove necessary and sufficient conditions on the values in S relative to n for the optimal wavelength index to be equal to the optimal load in the ring R_n. When k=2, we show that for any uniform instance specified by {d₁,d₂}, there is an optimal wavelength assignment on the ring R_n, if n>(d₁/q-2)d₁+(d₁/q-1)d₂, where q=GCD(d₁,d₂). For general k and n, we show a -approximation for the optimal wavelength index; this is the best possible for arbitrary S. We also show that an optimal assignment can always be obtained provided n is large enough compared to the values in S.     

An Asymptotic Property of Schachermayer's Space under Renorming

Let X be a Banach space with closed unit ball B. Given k , X is said to be k-β, respectively, (k + 1)-nearly uniformly convex ((k + 1)-NUC), if for every ε > 0 there exists δ, 0 < δ < 1, so that for every x B and every ε-separated sequence (x_n) B there are indices (n_i)^k_{i = 1}, respectively, (n_i)^{k + 1}_{i = 1}, such that (1/(k + 1))||x + ∑^k_{i = 1} x_ni|| ≤ 1 − δ, respectively, (1/(k + 1))||∑^{k + 1}_{i = 1} x_ni|| ≤ 1 − δ. It is shown that a Banach space constructed by Schachermayer is 2-β, but is not isomorphic to any 2-NUC Banach space. Modifying this example, we also show that there is a 2-NUC Banach space which cannot be equivalently renormed to be 1-β.     

The wave equation for Dunkl operators

Let k = (k_α)_αε, be a positive-real valued multiplicity function related to a root system , and Δ_k be the Dunkl-Laplacian operator. For (x, t) ε ^N, × , denote by u_k(x, t) the solution to the deformed wave equation Δ_ku_k,(x, t) = δ_ttu_k(x, t), where the initial data belong to the Schwartz space on ^N. We prove that for k 0 and N l, the wave equation satisfies a weak Huygens' principle, while a strict Huygens' principle holds if and only if (N − 3)/2 + Σ_αε+k_α ε . Here ⁺ is a subsystem of positive roots. As a particular case, if the initial data are supported in a closed ball of radius R > 0 about the origin, the strict Huygens principle implies that the support of u_k(x, t) is contained in the conical shell {(x, t), ε ^N × | |t| − R x |t| + R}. Our approach uses the representation theory of the group SL(2, ), and Paley-Wiener theory for the Dunkl transform. Also, we show that the (t-independent) energy functional of u_k is, for large |t|, partitioned into equal potential and kinetic parts.     

On the degree of weak convergence of a sequence of finite measures to the unit measure under convexity

This is a study of the degree of weak convergence under convexity of a sequence of finite measures μ_j on ^k, k 1, to the unit measure δ_x0. LetQ denote a convex and compact subset of ^k, let ƒ ε C^m(Q), m 0, satisfy a convexity condition and let μ be a finite measure on Q. Using standard moment methods, upper bounds and best upper bounds are obtained for ¦∝_Qƒdμ − ƒ(x₀)¦. They sometimes lead to sharp inequalities which are attained for particular μ and ƒ. These estimates are better than the corresponding ones found in the literature.     

An inequality relating the order,maximum degree,diameter and connectivity of a strongly connected digraph

We prove that if there is a strongly connected digraph of ordern, maximum degreed, diameterk and connectivityc, thennc d ^k–d /d–1+d+1. It improves the previous known results, and it, in fact, is the best possible for several interesting cases. A similar result for arc connectivity is also established.This project is supported by the National Natural Science Foundation of China.     

On the Strong Law of Large Numbers and the Law of the Logarithm for Weighted Sums of Independent Random Variables with Multidimensional Indices

Let (X, X ; ^d} be a field of independent identically distributed real random variables, 0 < p < 2, and {a _, ; ( , ) ^d × ^d, ≤ } a triangular array of real numbers, where ^d is the d-dimensional lattice. Under the minimal condition that sup _, |a _, | < ∞, we show that | |^{− 1/p} ∑ _≤ a _, X → 0 a.s. as | | → ∞ if and only if E(|X|^p(L|X|)^{d − 1}) < ∞ provided d ≥ 2. In the above, if 1 ≤ p < 2, the random variables are needed to be centered at the mean. By establishing a certain law of the logarithm, we show that the Law of the Iterated Logarithm fails for the weighted sums ∑ _≤ a _, X under the conditions that EX = 0, EX² < ∞, and E(X²(L|X|)^{d − 1}/L₂|X|) < ∞ for almost all bounded families {a _, ; ( , ) ^d × ^d, ≤ of numbers.     

Precise asymptotics in some strong limit theorems for multidimensionally indexed random variables

Consider Z₊^d (d2)—the positive d-dimensional lattice points with partial ordering , let {X_k,kZ₊^d} be i.i.d. random variables with mean 0, and set S_n=∑_knX_k, nZ₊^d. We establish precise asymptotics for ∑_n|n|^r/p−2P(|S_n||n|^1/p), and for

Full-size image

, (0δ1) as 0, and for

Full-size image

as .     

Spectral Density for Third Order Cumulants under Strong Mixing Conditions

If X{X_v: v ^d} is a strictly stationary random field, with X₀ bounded and expressible as a sum of indicator functions satisfying certain conditions, if the mixing coefficient α(s) is summable over ^d (that, is, ∑_m m^d−1α(m)<∞), and if a mixing condition involving three sets is satisfied, then the third order cumulant Cum(X_a, X_b, X_c) of X has a continuous spectral density. We do not begin with the assumption that the cumulants are absolutely summable.     

The Price of Pessimism for Multidimensional Quadrature

We study multivariate integration in the worst case setting for weighted Korobov spaces of smooth periodic functions of d variables. We wish to reduce the initial error by a factor for functions from the unit ball of the weighted Korobov space. Tractability means that the minimal number of function samples needed to solve the problem is polynomial in ⁻¹ and d. Strong tractability means that we have only a polynomial dependence in ⁻¹. This problem has been recently studied for quasi-Monte Carlo quadrature rules and for quadrature rules with non-negative coefficients. In this paper we study arbitrary quadrature rules. We show that tractability and strong tractability in the worst case setting hold under the same assumptions on the weights of the Korobov space as for the restricted classes of quadrature rules. More precisely, let γ_j moderate the behavior of functions with respect to the jth variable in the weighted Korobov space. Then strong tractability holds iff ∑^∞_j=1 γ_j<∞, whereas tractability holds iff lim sup_d→∞ ∑^d_j=1 γ_j/ln d<∞. We obtain necessary conditions on tractability and strong tractability by showing that multivariate integration for the weighted Korobov space is no easier than multivariate integration for the corresponding weighted Sobolev space of smooth functions with boundary conditions. For the weighted Sobolev space we apply general results from E. Novak and H. Woźniakowski (J. Complexity17 (2001), 388–441) concerning decomposable kernels.     

Representations for the first associated q-classical orthogonal polynomials

Let {p_k(x; q)} be any system of the q-classical orthogonal polynomials, and let be the corresponding weight function, satisfying the q-difference equation D_q(σ)=τ, where σ and τ are polynomials of degree at most 2 and exactly 1, respectively. Further, let {p_k⁽¹⁾(x;q)} be associated polynomials of the polynomials {p_k(x; q)}. Explicit forms of the coefficients b_n,k and c_n,k in the expansions

are given in terms of basic hypergeometric functions. Here _k(x) equals x^k if σ⁺(0)=0, or (x;q)_k if σ⁺(1)=0, where σ⁺(x)σ(x)+(q−1)xτ(x). The most important representatives of those two classes are the families of little q-Jacobi and big q-Jacobi polynomials, respectively.Writing the second-order nonhomogeneous q-difference equation satisfied by p_n−1⁽¹⁾(x;q) in a special form, recurrence relations (in k) for b_n,k and c_n,k are obtained in terms of σ and τ.     

A general framework of compactly supported splines and wavelets

Let {V_k} be a nested sequence of closed subspaces that constitute a multiresolution analysis of L²( ). We characterize the family Φ = {φ} where each φ generates this multiresolution analysis such that the two-scale relation of φ is governed by a finite sequence. In particular, we identify the ε Φ that has minimum support. We also characterize the collection Ψ of functions η such that each η generates the orthogonal complementary subspaces W_k of V_k, . In particular, the minimally supported ψ ε Ψ is determined. Hence, the “B-spline” and “B-wavelet” pair (, ψ) provides the most economical and computational efficient “spline” representations and “wavelet” decompositions of L² functions from the “spline” spaces V_k and “wavelet” spaces W_k, k . A very general duality principle, which yields the dual bases of both {(·−j):j and {η(·−j):j } for any η ε Ψ by essentially interchanging the pair of two-scale sequences with the pair of decomposition sequences, is also established. For many filtering applications, it is very important to select a multiresolution for which both and ψ have linear phases. Hence, “non-symmetric” and ψ, such as the compactly supported orthogonal ones introduced by Daubechies, are sometimes undesirable for these applications. Conditions on linear-phase φ and ψ are established in this paper. In particular, even-order polynomial B-splines and B-wavelets φ_m and ψ_m have linear phases, but the odd-order B-wavelet only has generalized linear phases.