Uniform approximation of min/max functions by smooth splines

In some optimization problems, min(f₁,…,f_n) usually appears as the objective or in the constraint. These optimization problems are typically non-smooth, and so are beyond the domain of smooth optimization algorithms. In this paper, we construct smooth splines to approximate min(f₁,…,f_n) uniformly so that such optimization problems can be dealt with as smooth ones.     

Quantum complexity of the approximation for the classes B(Wp ([0, 1])) and B(Hp ([0, 1]))

We study the approximation of functions from anisotropic Sobolev classes B(W^r_p([0,1]d)) and Hölder-Nikolskii classes B(H^r_p([0,1]d)) in the L_q([0,1]d) norm with q ≤ p in the quantum model of computation. We determine the quantum query complexity of this problem up to logarithmic factors. It shows that the quantum algorithms are significantly better than the classical deterministic or randomized algorithms.     

On simultaneous approximation to (α,α) with α+kα−1=0

We show that the modified Jacobi-Perron algorithm gives the best simultaneous approximation to (α,α²) with α³+kα−1=0. We claim the following facts:

(1)

the limit set of become an ellipse, where (p_n,q_n,r_n) is the nth convergent (p_n/q_n,r_n/q_n) of (α,α²) by the modified Jacobi-Perron algorithm,

(2)

the limit set of belongs to outside of the ellipse in (1).

     

A generalization of Dirichlet approximation theorem for the affine actions on real line

In this paper, we obtain strong density results for the orbits of real numbers under the action of the semigroup generated by the affine transformations T₀(x)=x/a and T₁(x)=bx+1, where a,b>1. These density results are formulated as generalizations of the Dirichlet approximation theorem and improve the results of Bergelson, Misiurewicz, and Senti. We show that for any x,u>0 there are infinitely many elements γ in the semigroup generated by T₀ and T₁ such that |γ(x)−u|<C(t1/|γ|−1), where C and t are constants independent of γ, and |γ| is the length of γ as a word in the semigroup. Finally, we discuss the problem of approximating an arbitrary real number by the ratios of prime numbers and the ratios of logarithms of prime numbers.     

Special uniform approximations of continuous vector-valued functions. Part II: special approximations in CX(T)CY(S)

In this paper, which is a continuation of Timofte (J. Approx. Theory 119 (2002) 291–299, we give special uniform approximations of functions from C_XY(T×S) and C_∞(T×S,XY) by elements of the tensor products C_X(T)C_Y(S), respectively C₀(T,X)C₀(S,Y), for topological spaces T,S and Γ-locally convex spaces X,Y (all four being Hausdorff).     

Three-space problems for the bounded compact approximation property

In this paper, the notion of the bounded compact approximation property (BCAP) of a pair [Banach space and its subspace] is used to prove that if X is a closed subspace of L∞ with the BCAP, then L∞/X has the BCAP. We also show that X* has the λ-BCAP with conjugate operators if and only if the pair (X, Y) has the λ-BCAP for each finite codimensional subspace Y∈X. Let M be a closed subspace of X such that M⊥ is complemented in X*. If X has the (bounded) approximation property of order p, then M has the (bounded) approximation property of order p.     

Application of wavelet bases in linear and nonlinear approximation to functions from Besov spaces

Linear and nonlinear approximations to functions from Besov spaces B _{p, q} ^σ ([0, 1]), σ > 0, 1 ≤ p, q ≤ ∞ in a wavelet basis are considered. It is shown that an optimal linear approximation by a D-dimensional subspace of basis wavelet functions has an error of order D ^{-min(σ, σ + 1/2 ? 1/p)} for all 1 ≤ p ≤ ∞ and σ > max(1/p ? 1/2, 0). An original scheme is proposed for optimal nonlinear approximation. It is shown how a D-dimensional subspace of basis wavelet functions is to be chosen depending on the approximated function so that the error is on the order of D ^?σ for all 1 ≤ p ≤ ∞ and σ > max(1/p ? 1/2, 0). The nonlinear approximation scheme proposed does not require any a priori information on the approximated function.     

The solvability conditions for the inverse eigenproblems of symmetric and generalized centro-symmetric matrices and their approximations

Let ∥ · ∥ be the Frobenius norm of matrices. We consider (I) the set S_E of symmetric and generalized centro-symmetric real n × n matrices R_n with some given eigenpairs (λ_j, q_j) (j = 1, 2, … , m) and (II) the element in S_E which minimizes for a given real matrix R^∗. Necessary and sufficient conditions for S_E to be nonempty are presented. A general form of elements in S_E is given and an explicit expression of the minimizer is derived. Finally, a numerical example is reported.     

Asymptotic joint distribution of the largest roots of several multivariate F matrices I. Quasi-independent case

An asymptotic expansion of the joint distribution of k largest characteristic roots C_M⁽ⁱ⁾(S_iS₀^?1), i = 1,…, k, is given, where S'_is and S₀ are independent Wishart matrices with common covariance matrix Σ. The modified second-approximation procedure to the upper percentage points of the maximum of C_M⁽ⁱ⁾(S_iS₀^?1), i = 1,…, k, is also considered. The evaluation of the expansion is based on the idea for studentization due to Welch and James with the use of differential operators and of the perturbation procedure.     

Uniform and tangential approximation in a stripe by meromorphic functions of optimal growth

The paper discusses the problem of approximation of functions continuous on a closed stripe S _h = {z: |Imz| ≤h} and holomorphic in its interior. The results relate to the uniform and tangential approximation of such functions f by meromorphic functions g with minimal growth in terms of Nevanlinna characteristic T (r, g). The growth depends on the growth of f in S _h and certain differential properties of f on ?S _h . It is assumed that the possible poles of g are restricted to the imaginary axis.     

Diffusion-equation model of slightly loaded M/M/1 queue

Another derivation of the diffusion approximation of the M/M/1 queue is presented, which results in a new boundary condition. The model proposed approximates the time-dependent behavior of the M/M/1 system for all values of channel utilization.     

Some results for the queues Mx/M/c and GIx/ G/c

We develop for the queue M^x/M/c an upper bound for the mean queue length and lower bounds for the delay probabilities (that of an arrival group and that of an arbitrary customer in the arrival group). An approximate formula is also developed for the general bulk-arrival queue GI^x/G/c. Preliminary numerical studies have indicated excellent performance of the results.     

Approximation of integrable functions by general linear operators of their fourier series

The pointwise estimates of the deviation T n,A,B f (·) f (·) in terms of moduli of continuity .f and w.f there are proved. Analogical results on norm approximation with remarks and corollaries are also given. In the results there are used the essentially weaker conditions than these in [Mittal, M. L.: J. Math. Anal. Appl., 220, 434-450 (1998) Theorem 1, p. 437].     

Average error bounds of trigonometric approximation on periodic Wiener spaces

In this paper, we study the approximation of identity operator and the convolution integral operator Bm by Fourier partial sum operators, Fejr operators, Valle-Poussin operators, Cesárooperators and Abel mean operators, respectively, on the periodic Wiener space (C1(R),Wo) and obtainthe average error estimations.     

Asymptotic property for some series of probability

Let {X, X n , n≥1} be a sequence of i.i.d.random variables with zero mean, and set Sn = Σ k=1 n X k , EX2=σ 2>0, λ(ε) =Σ n=1 ∞ P (|Sn|≥ nε). In this paper, we discuss the rate of the approximation of σ2 by ε2 λ(ε) under suitable conditions, and improve the corresponding results of Klesov (1994).     

An SDP randomized approximation algorithm for max hypergraph cut with limited unbalance

We consider the design of semidefinite programming(SDP) based approximation algorithm for the problem Max Hypergraph Cut with Limited Unbalance(MHC-LU): Find a partition of the vertices of a weighted hypergraph H =(V, E) into two subsets V1, V2 with ‖V2|- |V1‖ u for some given u and maximizing the total weight of the edges meeting both V1 and V2. The problem MHC-LU generalizes several other combinatorial optimization problems including Max Cut, Max Cut with Limited Unbalance(MC-LU), Max Set Splitting,Max Ek-Set Splitting and Max Hypergraph Bisection. By generalizing several earlier ideas, we present an SDP randomized approximation algorithm for MHC-LU with guaranteed worst-case performance ratios for various unbalance parameters τ = u/|V|. We also give the worst-case performance ratio of the SDP-algorithm for approximating MHC-LU regardless of the value of τ. Our strengthened SDP relaxation and rounding method improve a result of Ageev and Sviridenko(2000) on Max Hypergraph Bisection(MHC-LU with u = 0), and results of Andersson and Engebretsen(1999), Gaur and Krishnamurti(2001) and Zhang et al.(2004) on Max Set Splitting(MHC-LU with u = |V|). Furthermore, our new formula for the performance ratio by a tighter analysis compared with that in Galbiati and Maffioli(2007) is responsible for the improvement of a result of Galbiati and Maffioli(2007) on MC-LU for some range of τ.     

Approximation of signals of class Lip(α, p) by linear operators

Mittal, Rhoades [5], [6], [7] and [8] and Mittal et al. [9] and [10] have initiated a study of error estimates E_n(f) through trigonometric-Fourier approximation (tfa) for the situations in which the summability matrix T does not have monotone rows. In this paper we continue the work. Here we extend two theorems of Leindler [4], where he has weakened the conditions on {p_n} given by Chandra [2], to more general classes of triangular matrix methods. Our Theorem also partially generalizes Theorem 4 of Mittal et al. [11] by dropping the monotonicity on the elements of matrix rows, which in turn generalize the results of Quade [15].     

Best Simultaneous Approximation in L(I,E)

Let G be a reflexive subspace of the Banach space E and let L^p(I,E) denote the space of all p-Bochner integrable functions on the interval I=[0,1] with values in E, 1p∞. Given any norm N( , ) on R², N nondecreasing in each coordinate on the set R²₊, we prove that L^p(I,G) is N-simultaneously proximinal in L^p(I,E). Other results are also obtained.     

The weight distribution of irreducible cyclic codes with block lengths n1((q1−1)N)

We study the weight distribution of irreducible cyclic (n, k) codeswith block lengths n = n₁((q¹ ? 1)/N), where N|q ? 1, gcd(n₁,N) = 1, and gcd(l,N) = 1. We present the weight enumerator polynomial, A(z), when k = n₁l, k = (n₁ ? 1)l, and k = 2l. We also show how to find A(z) in general by studying the generator matrix of an (n₁, m) linear code, $\text{V}{}^1{}_{\mathrm{d}}$ over GF(q^d) where d = gcd (ord_n1(q), l). Specifically we study A(z) when $\text{V}{}^1{}_{\mathrm{d}}$ is a maximum distance separable code, a maximal shiftregister code, and a semiprimitive code. We tabulate some numbers A_μ which completely determine the weight distributionof any irreducible cyclic (n₁(2¹ ? 1), k) code over GF(2) for all n₁ ? 17.     

Necessary and sufficient conditions for the Robbins-Monro method

This paper examines the relation between convergence of the Robbins-Monro iterates $\text{X}{}_{\mathrm{n+1}}\text{= X}{}_{\mathrm{n}}\text{?a}{}_{\mathrm{n}}\text{?(X}{}_{\mathrm{n}}\text{)+a}{}_{\mathrm{n}}\text{ξ}{}_{\mathrm{n}}\text{, ?(θ)=0}$, and the laws of large numbers S_n=a_nΣ^n?1_j=0ξ_j→0 as n→+∞. If a_n is decreasing at least as rapidly as c/n, then X_n→θw.p. 1 (resp. in L_p, p?1) implies S_n→0 w.p. 1 (resp. in L_p, p?1) as n→+∞. If a_n is decreasing at least as slowly as c?n and lim_n→+∞a_n=0, then S_n→0 w.p. 1 (resp. in L_p, p?2) implies X_n→θw.p. 1 (resp. in L_p, p?2) as n →+∞. Thus, there is equivalence in the frequently examined case $\text{a}{}_{\mathrm{n}}\text{?c?n}$. Counter examples show that the LLN must have the form of S_n, that the rate of decrease conditions are sharp, that the weak LLN is neither necessary nor sufficient for the convergence in probability of X_n to θ when $\text{a}{}_{\mathrm{n}}\text{?c?n}$.