Compactly supported wavelet bases for Sobolev spaces

In this paper we investigate compactly supported wavelet bases for Sobolev spaces. Starting with a pair of compactly supported refinable functions φ and in satisfying a very mild condition, we provide a general principle for constructing a wavelet ψ such that the wavelets ψ_jk:=2^j/2ψ(2^j·−k) ( ) form a Riesz basis for . If, in addition, φ lies in the Sobolev space , then the derivatives 2^j/2ψ^(m)(2^j·−k) ( ) also form a Riesz basis for . Consequently, is a stable wavelet basis for the Sobolev space . The pair of φ and are not required to be biorthogonal or semi-orthogonal. In particular, φ and can be a pair of B-splines. The added flexibility on φ and allows us to construct wavelets with relatively small supports.     

Compactly Supported Tight Frames Associated with Refinable Functions

It is well known that in applied and computational mathematics, cardinal B-splines play an important role in geometric modeling (in computer-aided geometric design), statistical data representation (or modeling), solution of differential equations (in numerical analysis), and so forth. More recently, in the development of wavelet analysis, cardinal B-splines also serve as a canonical example of scaling functions that generate multiresolution analyses of L²(−∞,∞). However, although cardinal B-splines have compact support, their corresponding orthonormal wavelets (of Battle and Lemarie) have infinite duration. To preserve such properties as self-duality while requiring compact support, the notion of tight frames is probably the only replacement of that of orthonormal wavelets. In this paper, we study compactly supported tight frames Ψ={ψ¹,…,ψ^N} for L²(−∞,∞) that correspond to some refinable functions with compact support, give a precise existence criterion of Ψ in terms of an inequality condition on the Laurent polynomial symbols of the refinable functions, show that this condition is not always satisfied (implying the nonexistence of tight frames via the matrix extension approach), and give a constructive proof that when Ψ does exist, two functions with compact support are sufficient to constitute Ψ, while three guarantee symmetry/anti-symmetry, when the given refinable function is symmetric.     

Partial pluricomplex energy and integrability exponents of plurisubharmonic functions

We first prove a quantitative estimate of the volume of the sublevel sets of a plurisubharmonic function in a hyperconvex domain with boundary values 0 (in a quite general sense) in terms of its Monge–Ampère mass in the domain. Then we deduce a sharp sufficient condition on the Monge–Ampère mass of such a plurisubharmonic function φ for exp(−2φ) to be globally integrable as well as locally integrable.     

Worst case behavior of the steepest edge simplex method

At each nondegenerate iteration of the steepest-edge simplex method one moves from a vertex of the polyhedron, P, of feasible points to an adjacent vertex along an edge that is steepest with respect to the linear objective function ψ. In this paper we show how to construct a sequence of linear programs (P_n,ψ_n) in n variables for which the number of iterations required by the steepest edge simplex method is 2ⁿ−1.     

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.     

On the Almost Everywhere Convergence of Wavelet Summation Methods

Let ψ be a rapidly decreasing one-dimensional wavelet. We show that the wavelet expansion of anyL^pfunction converges pointwise almost everywhere under the wavelet projection, hard sampling, and soft sampling summation methods, for 1 <p< ∞. In fact, the partial sums are uniformly dominated by the Hardy–Littlewood maximal function.     

Super-connectivity and super-edge-connectivity for some interconnection networks

Let G=(V,E) be a k-regular graph with connectivity κ and edge connectivity λ. G is maximum connected if κ=k, and G is maximum edge connected if λ=k. Moreover, G is super-connected if it is a complete graph, or it is maximum connected and every minimum vertex cut is {x|(v,x)E} for some vertex vV; and G is super-edge-connected if it is maximum edge connected and every minimum edge disconnecting set is {(v,x)|(v,x)E} for some vertex vV. In this paper, we present three schemes for constructing graphs that are super-connected and super-edge-connected. Applying these construction schemes, we can easily discuss the super-connected property and the super-edge-connected property of hypercubes, twisted cubes, crossed cubes, möbius cubes, split-stars, and recursive circulant graphs.     

Adaptivity and computational complexity in the numerical solution of ODEs

In this paper we analyze the problem of adaptivity for one-step numerical methods for solving ODEs, both IVPs and BVPs, with a view to generating grids of minimal computational cost for which the local error is below a prescribed tolerance (optimal grids). The grids are generated by introducing an auxiliary independent variable τ and finding a grid deformation map, t=Θ(τ), that maps an equidistant grid {τ_j} to a non-equidistant grid in the original independent variable, {t_j}. An optimal deformation map Θ is determined by a variational approach. Finally, we investigate the cost of the solution procedure and compare it to the cost of using equidistant grids. We show that if the principal error function is non-constant, an adaptive method is always more efficient than a non-adaptive method.     

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.     

Resource augmentation for online bounded space bin packing

We study online bounded space bin packing in the resource augmentation model of competitive analysis. In this model, the online bounded space packing algorithm has to pack a list L of items in (0,1] into a small number of bins of size b1. Its performance is measured by comparing the produced packing against the optimal offline packing of the list L into bins of size 1.We present a complete solution to this problem: For every bin size b1, we design online bounded space bin packing algorithms whose worst case ratio in this model comes arbitrarily close to a certain bound ρ(b). Moreover, we prove that no online bounded space algorithm can perform better than ρ(b) in the worst case.     

Necessary and sufficient conditions for functions involving the tri- and tetra-gamma functions to be completely monotonic

The psi function ψ(x) is defined by ψ(x)=Γ^′(x)/Γ(x), where Γ(x) is the gamma function. We give necessary and sufficient conditions for the function ψ^″(x)+[ψ^′(x+α)]² or its negative to be completely monotonic on (−α,∞), where . We also prove that the function [ψ^′(x)]²+λψ^″(x) is completely monotonic on (0,∞) if and only if λ1. As an application of the latter conclusion, the monotonicity and convexity of the function e^pψ(x+1)−qx with respect to x(−1,∞) are thoroughly discussed for p≠0 and .     

Construction Techniques for Highly Accurate Quasi-Interpolation Operators

Under mild additional assumptions this paper constructs quasi-interpolants in the form

Full-size image

with approximation order ℓ−1, where_h(x) is a linear combination of translatesψ(x−jh) of a functionψinC^ℓ( ). Thus the order of convergence of such operators can be pushed up to a limit that only depends on the smoothness of the functionψ. This approach can be generalized to the multivariate setting by using discrete convolutions with tensor products of odd-degreeB-splines.     

The vertex-cover polynomial of a graph

In this paper we define the vertex-cover polynomial Ψ(G,τ) for a graph G. The coefficient of τ^r in this polynomial is the number of vertex covers V′ of G with |V′|=r. We develop a method to calculate Ψ(G,τ). Motivated by a problem in biological systematics, we also consider the mappings f from {1, 2,…,m} into the vertex set V(G) of a graph G, subject to f⁻¹(x)f⁻¹(y)≠ for every edge xy in G. Let F(G,m) be the number of such mappings f. We show that F(G,m) can be determined from Ψ(G,τ).     

Asymptotic expansions of the distributions of some test statistics for Gaussian ARMA processes

Let {X_t} be a Gaussian ARMA process with spectral density f_θ(λ), where θ is an unknown parameter. The problem considered is that of testing a simple hypothesis H:θ = θ₀ against the alternative A:θ ≠ θ₀. For this problem we propose a class of tests , which contains the likelihood ratio (LR), Wald (W), modified Wald (MW) and Rao (R) tests as special cases. Then we derive the χ² type asymptotic expansion of the distribution of T up to order n⁻¹, where n is the sample size. Also we derive the χ² type asymptotic expansion of the distribution of T under the sequence of alternatives A_n: θ = θ₀ + /√n, ε > 0. Then we compare the local powers of the LR, W, MW, and R tests on the basis of their asymptotic expansions.     

Perturbation of Orthogonal Polynomials on an Arc of the Unit Circle

Orthogonal polynomials on the unit circle are completely determined by their reflection coefficients through the Szeg recurrences. We assume that the reflection coefficients converge to some complex number a with 0 < |a| < 1. The polynomials then live essentially on the are {e^iθ : α ≤ θ ≤ 2 π − α) where cos(α/2) [formula] with α (0, π). We analyze the orthogonal polynomials by comparing them with the orthogonal polynomials with constant reflection coefficients, which were studied earlier by Ya. L. Geronimus and N. I. Akhiezer. In particular, we show that under certain assumptions on the rate of convergence of the reflection coefficients the orthogonality measure will be absolutely continuous on the are. In addition, we also prove the unit circle analogue of M. G. Krein′s characterization of compactly supported nonnegative Borel measures on the real line whose support contains one single limit point in terms of the corresponding system of orthogonal polynomials.     

Acyclic graphoidal covers and path partitions in a graph

An acyclic graphoidal cover of a graph G is a collection ψ of paths in G such that every path in ψ has at least two vertices, every vertex of G is an internal vertex of at most one path in ψ and every edge of G is in exactly one path in ψ. The minimum cardinality of an acyclic graphoidal cover of G is called the acyclic graphoidal covering number of G and is denoted by η_a. A path partition of a graph G is a collection P of paths in G such that every edge of G is in exactly one path in P. The minimum cardinality of a path partition of G is called thepath partition number of G and is denoted by π. In this paper we determine η_a and π for several classes of graphs and obtain a characterization of all graphs with Δ 4 and η_a = Δ − 1. We also obtain a characterization of all graphs for which η_a = π.     

The heat flow in nonlinear Hodge theory

We study the nonlinear Hodge system dω=0 and δ(ρ(|ω|²)ω)=0 for an exterior form ω on a compact oriented Riemannian manifold M, where ρ(Q) is a given positive function. The solutions are called ρ-harmonic forms. They are the stationary points on cohomology classes of the functional with e′(Q)=ρ(Q)/2. The ρ-codifferential of a form ω is defined as δ_ρω=ρ⁻¹δ(ρω) with ρ=ρ(|ω|²).We evolve a given closed form ω₀ by the nonlinear heat flow system for a time-dependent exterior form ω(x,t) on M. This system is the differential of the normalized gradient flow for E(ω) with ω=ω₀+du. Under a technical assumption on the function 2ρ′(Q)Q/ρ(Q), we show that the nonlinear heat flow system , with initial condition ω(·,0)=ω₀, has a unique solution for all times, which converges to a ρ-harmonic form in the cohomology class of ω₀. This yields a nonlinear Hodge theorem that every cohomology class of M has a unique ρ-harmonic representative.     

Edge colorings of graphs embeddable in a surface of low genus

In this paper, by using the Discharging Method, we show that any graph with maximum degree Δ 8 that is embeddable in a surface Σ of characteristic χ(Σ) 0 is class one and any graph with maximum degree Δ 9 that is embeddable in a surface Σ of characteristic χ(Σ) = − 1 is class one. For surfaces of characteristic 0 or −1, these results improve earlier results of Mel'nikov.     

Asymptotic properties of Cramér-Smirnov statistics—A new approach

Let Y₁,…, Y_n be independent identically distributed random variables with distribution function F(x, θ), θ = (θ′₁, θ′₂), where θ_i (i = 1, 2) is a vector of p_i components, p = p₁ + p₂ and for θI, an open interval in ^p, F(x, θ) is continuous. In the present paper the author shows that the asymptotic distribution of modified Cramér-Smirnov statistic under H_n: θ₁ = θ₁₀ + n^−1/2γ, θ₂ unspecified, where γ is a given vector independent of n, is the distribution of a sum of weighted noncentral χ₁² variables whose weights are eigenvalues of a covariance function of a Gaussian process and noncentrality parameters are Fourier coefficients of the mean function of the Gaussian process. Further, the author exploits the special form of the covariance function by using perturbation theory to obtain the noncentrality parameters and the weights. The technique is applicable to other goodness-of-fit statistics such as U² [G. S. Watson, Biometrika 48 (1961), 109–114].     

Complete on Average Boolean Satisfiability

We present in this paper a dynamic binary coding scheme α on CNF formulas ψ, and show that under a uniform distribution μ_α on binary string α(ψ), SAT is complete on average, where μ_α(ψ) is proportional to α(ψ)⁻²2^−α(ψ). We then show that there is k₀>2 such that for all kk₀, kSAT under μ_α is complete on average.