Error bounds for least squares approximation by polynomials

Let f ε Cⁿ⁺¹[−1, 1] and let H[f](x) be the nth degree weighted least squares polynomial approximation to f with respect to the orthonormal polynomials q_k associated with a distribution dα on [−1, 1]. It is shown that if q_n+1/q_n max(q_n+1(1)/q_n(1), −q_n+1(−1)/q_n(−1)), then f − H[f] f^{n + 1} · q_n+1/q_{n + 1}^{(n + 1)}, where · denotes the supremum norm. Furthermore, it is shown that in the case of Jacobi polynomials with distribution (1 − t)^α (1 + t)^β dt, α, β > −1, the condition on q_n+1/q_n is satisfied when either max(α,β) −1/2 or −1 < α = β < −1/2.     

Multi-Dimensional Pattern Matching with Dimensional Wildcards: Data Structures and Optimal On-Line Search Algorithms

We introduce a new multidimensional pattern matching problem that is a natural generalization of string matching, a well studied problem[1]. The motivation for its algorithmic study is mainly theoretical. LetA[1:n₁,…,1:n_d] be a text matrix withN = n₁…n_dentries andB[1:m₁,…,1:m_r] be a pattern matrix withM = m₁…m_rentries, whered ≥ r ≥ 1 (the matrix entries are taken from an ordered alphabet Σ). We study the problem of checking whether somer-dimensional submatrix ofAis equal toB(i.e., adecisionquery).Acan be preprocessed andBis given on-line. We define a new data structure for preprocessingAand propose CRCW-PRAM algorithms that build it inO(log N) time withN²/n_maxprocessors, wheren_max = max(n₁,…,n_d), such that the decision query forBtakesO(M) work andO(log M) time. By using known techniques, we would get the same preprocessing bounds but anO((^d_r)M) work bound for the decision query. The latter bound is undesirable since it can depend exponentially ond; our bound, in contrast, is independent ofdand optimal. We can also answer, in optimal work, two further types of queries: (a) anenumerationquery retrieving all ther-dimensional submatrices ofAthat are equal toBand (b) anoccurrencequery retrieving only the distinct positions inAthat correspond to all of these submatrices. As a byproduct, we also derive the first efficient sequential algorithms for the new problem.     

Stochastic comparisons of order statistics from heterogeneous populations, with applications in reliability

The basic result of the paper states: Let F₁, …, F_n, F₁^′,…, F_n^′ have proportional hazard functions with λ₁ ,…, λ_n , λ₁^′ ,…, λ_n^′ as the constants of proportionality. Let X₍₁₎ ≤ … ≤ X_(n) (X₍₁₎^′ ≤ … ≤ X_(n)^′) be the order statistics in a sample of size n from the heterogeneous populations {F₁ ,…, F_n}({F₁^′ ,…, F_n^′}). Then (λ₁ ,…, λ_n) majorizes (λ₁^′ ,…, λ_n^′) implies that (X₍₁₎ ,…, X_(n)) is stochastically larger than (X₍₁₎^′ ,…, X_(n)^′). Earlier results stochastically comparing individual order statistics are shown to be special cases. Applications of the main result are made in the study of the robustness of standard estimates of the failure rate of the exponential distribution, when observations actually come from a set of heterogeneous exponential distributions. Further applications are made to the comparisons of linear combinations of Weibull random variables and of binomial random variables.     

On the evaluation of the Eigenvalues of a banded toeplitz block matrix

Let A = (a_ij) be an n × n Toeplitz matrix with bandwidth k + 1, K = r + s, that is, a_ij = a_j−i, i, J = 1,… ,n, a_i = 0 if i > s and if i < -r. We compute p(λ)= det(A - λI), as well as p(λ)/p′(λ), where p′(λ) is the first derivative of p(λ), by using O(k log k log n) arithmetic operations. Moreover, if a_i are m × m matrices, so that A is a banded Toeplitz block matrix, then we compute p(λ), as well as p(λ)/p′(λ), by using O(m³k(log² k + log n) + m²k log k log n) arithmetic operations. The algorithms can be extended to the computation of det(A − λB) and of its first derivative, where both A and B are banded Toeplitz matrices. The algorithms may be used as a basis for iterative solution of the eigenvalue problem for the matrix A and of the generalized eigenvalue problem for A and B.     

Asymptotic distributions of regression and autoregression coefficients with martingale difference disturbances

In this paper a form of the Lindeberg condition appropriate for martingale differences is used to obtain asymptotic normality of statistics for regression and autoregression. The regression model is y_t = Bz_t + v_t. The unobserved error sequence {v_t} is a sequence of martingale differences with conditional covariance matrices {Σ_t} and satisfying sup_{t=1,…, n} {v′_tv_tI(v′_tv_t>a) |z_t, v_t−1, z_t−1, …} 0 as a → ∞. The sample covariance of the independent variables z₁, …, z_n, is assumed to have a probability limit M, constant and nonsingular; max_t=1,…,nz′_tz_t/n 0. If (1/n)Σ_t=1ⁿΣ_t Σ, constant, then √nvec( _n−B) N(0,M⁻¹Σ) and _n Σ. The autoregression model is x_t = Bx_{t − 1} + v_t with the maximum absolute value of the characteristic roots of B less than one, the above conditions on {v_t}, and (1/n)Σ_t=max(r,s)+1(Σ_tv_t−1−rv′_t−1−s) δ_rs(ΣΣ), where δ_rs is the Kronecker delta. Then √nvec( _n−B) N(0,Γ⁻¹Σ), where Γ = Σ_{s = 0}^∞B^sΣ(B′)^s.     

On constants in some inequalities for intermediate derivatives on a finite interval

Let L_q (1q<∞) be the space of functions f measurable on I=[−1,1] and integrable to the power q, with normL_∞ is the space of functions measurable on I with normWe denote by AC the set of all functions absolutely continuous on I. For nN, q[1,∞] we setW_n,q={f:f⁽ⁿ⁻¹⁾AC, f⁽ⁿ⁾L_q}.In this paper, we consider the problem of accuracy of constants A, B in the inequalities (1)|| f^(m)||_qA|| f||_p+B|| f^(m+k+1)||_r, mN, kW; p,q,r[1,∞], fW_m+k+1,r.     

Minimax estimation of the mean of spherically symmetric distributions under general quadratic loss

For X one observation on a p-dimensional (p ≥ 4) spherically symmetric (s.s.) distribution about θ, minimax estimators whose risks dominate the risk of X (the best invariant procedure) are found with respect to general quadratic loss, L(δ, θ) = (δ − θ)′ D(δ − θ) where D is a known p × p positive definite matrix. For C a p × p known positive definite matrix, conditions are given under which estimators of the form δ_a,r,C,D(X) = (I − (ar(|X|²)) D^−1/2CD^1/2 |X|⁻²)X are minimax with smaller risk than X. For the problem of estimating the mean when n observations X₁, X₂, …, X_n are taken on a p-dimensional s.s. distribution about θ, any spherically symmetric translation invariant estimator, δ(X₁, X₂, …, X_n), with have a s.s. distribution about θ. Among the estimators which have these properties are best invariant estimators, sample means and maximum likelihood estimators. Moreover, under certain conditions, improved robust estimators can be found.     

Matroids with No (q+2)-Point-Line Minors

It is known that a geometry with rankrand no minor isomorphic to the (q+2)-point line has at most (q^r−1)/(q−1) points, with strictly fewer points ifr>3 andqis not a prime power. Forqnot a prime power andr>3, we show thatq^r−1−1 is an upper bound. Forqa prime power andr>3, we show that any rank-rgeometry with at leastq^r−1points and no (q+2)-point-line minor is representable overGF(q). We strengthen these bounds toq^r−1−(q^r−2−1)/(q−1)−1 andq^r−1−(q^r−2−1)/(q−1) respectively whenqis odd. We give an application to unique representability and a new proof of Tutte's theorem: A matroid is binary if and only if the 4-point line is not a minor.     

Small Point Sets that Meet All Generators of W(2n+1,q)

Let W(2n+1,q), n1, be the symplectic polar space of finite order q and (projective) rank n. We investigate the smallest cardinality of a set of points that meets every generator of W(2n+1,q). For q even, we show that this cardinality is q ⁿ⁺¹+q ^{n–1, and we characterize all sets of this cardinality. For q odd, better bounds are known.     

Schur functions and the invariant polynomials characterizing U(n) tensor operators

We give a direct formulation of the invariant polynomials _μG_q⁽ⁿ⁾(, Δ_i,;, x_{i,i + 1},) characterizing U(n) tensor operators p, q, …, q, 0, …, 0 in terms of the symmetric functions S_λ known as Schur functions. To this end, we show after the change of variables Δ_i = γ_i − δ_i and x_{i, i + 1} = δ_i − δ_{i + 1} that_μG_q⁽ⁿ⁾(,Δ_i;, x_{i, i + 1},) becomes an integral linear combination of products of Schur functions S_α(, γ_i,) · S_β(, δ_i,) in the variables {γ₁,…, γ_n} and {δ₁,…, δ_n}, respectively. That is, we give a direct proof that _μG_q⁽ⁿ⁾(,Δ_i,;, x_{i, i + 1},) is a bisymmetric polynomial with integer coefficients in the variables {γ₁,…, γ_n} and {δ₁,…, δ_n}. By making further use of basic properties of Schur functions such as the Littlewood-Richardson rule, we prove several remarkable new symmetries for the yet more general bisymmetric polynomials _μ^mG_q⁽ⁿ⁾(γ₁,…, γ_n; δ₁,…, δ_m). These new symmetries enable us to give an explicit formula for both _μ^mG₁⁽ⁿ⁾(γ; δ) and ₁G₂⁽ⁿ⁾(γ; δ). In addition, we describe both algebraic and numerical integration methods for deriving general polynomial formulas for _μ^mG_q⁽ⁿ⁾(γ; δ).     

On improved estimators of the generalized variance

Treated in this paper is the problem of estimating with squared error loss the generalized variance | Σ | from a Wishart random matrix S: p × p W_p(n, Σ) and an independent normal random matrix X: p × k N(ξ, Σ I_k) with ξ(p × k) unknown. Denote the columns of X by X₍₁₎ ,…, X_(k) and set ψ⁽⁰⁾(S, X) = {(n − p + 2)!/(n + 2)!} | S |, ψ⁽ⁱ⁾(X, X) = min[ψ⁽ⁱ⁻¹⁾(S, X), {(n − p + i + 2)!/(n + i + 2)!} | S + X₍₁₎ X′₍₁₎ + + X_(i) X′_(i) |] and Ψ⁽ⁱ⁾(S, X) = min[ψ⁽⁰⁾(S, X), {(n − p + i + 2)!/(n + i + 2)!}| S + X₍₁₎ X′₍₁₎ + + X_(i) X′_(i) |], i = 1,…,k. Our result is that the minimax, best affine equivariant estimator ψ⁽⁰⁾(S, X) is dominated by each of Ψ⁽ⁱ⁾(S, X), i = 1,…,k and for every i, ψ⁽ⁱ⁾(S, X) is better than ψ⁽ⁱ⁻¹⁾(S, X). In particular, ψ^(k)(S, X) = min[{(n − p + 2)!/(n + 2)!} | S |, {(n − p + 2)!/(n + 2)!} | S + X₍₁₎X′₍₁₎|,…,| {(n − p + k + 2)!/(n + k + 2)!} | S + X₍₁₎X′₍₁₎ + + X_(k)X′_(k)|] dominates all other ψ's. It is obtained by considering a multivariate extension of Stein's result (Ann. Inst. Statist. Math. 16, 155–160 (1964)) on the estimation of the normal variance.     

Compensated Compactness, Paracommutators, and Hardy Spaces

LetB₁: ⁿ× ^N₁→ ^m₁,B₂: ⁿ× ^N₂→ ^m₂andQ: ^m₂→ ^m₁be bilinear forms which are related as follows: ifμandνsatisfyB₁(ξ, μ)=0 andB₂(ξ, ν)=0 for someξ≠0, thenμ^τQν=0. Supposep⁻¹+q⁻¹=1. Coifman, Lions, Meyer and Semmes proved that, ifuL^p( ⁿ) andvL^q( ⁿ), and the first order systemsB₁(D, u)=0,B₂(D, v)=0 hold, thenu^τQvbelongs to the Hardy spaceH¹( ⁿ), provided that both (i)p=q=2, and (ii) the ranks of the linear mapsB_j(ξ, ·) : ^N_j→ ^m₁are constant. We apply the theory of paracommutators to show that this result remains valid when only one of the hypotheses (i), (ii) is postulated. The removal of the constant-rank condition whenp=q=2 involves the use of a deep result of Lojasiewicz from singularity theory.     

On the Erd s-Ginzburg-Ziv theorem and the Ramsey numbers for stars and matchings

A link between Ramsey numbers for stars and matchings and the Erd s-Ginzburg-Ziv theorem is established. Known results are generalized. Among other results we prove the following two theorems. Theorem 5. Let m be an even integer. If c : e (K_2m−1)→{0, 1,…, m−1} is a mapping of the edges of the complete graph on 2m−1 vertices into {0, 1,…, m−1}, then there exists a star K_1,m in K_2m−1 with edges e₁, e₂,…, e_m such that c(e₁)+c(e₂)++c(e_m)≡0 (mod m). Theorem 8. Let m be an integer. If c : e(K^r_(r+1)m−1)→{0, 1,…, m−1} is a mapping of all the r-subsets of an (r+1)m−1 element set S into {0, 1,…, m−1}, then there are m pairwise disjoint r-subsets Z₁, Z₂,…, Z_m of S such that c(Z₁)+c(Z₂)++c(Z_m)≡0 (mod m).     

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,τ).     

Kolmogorov Width of Classes of Smooth Functions on the Sphere

Let ^d−1{(x₁,…,x_d) ^d:x²₁+···+x²_d=1} be the unit sphere of the d-dimensional Euclidean space ^d. For r>0, we denote by B^r_p (1p∞) the class of functions f on ^d−1 representable in the formwhere dσ(y) denotes the usual Lebesgue measure on ^d−1, and P^λ_k(t) is the ultraspherical polynomial.For 1p,q∞, the Kolmogorov N-width of B^r_p in L^q( ^d−1) is given bythe left-most infimum being taken over all N-dimensional subspaces X_N of L^q( ^d−1).The main result in this paper is that for r2(d−1)²,where A_NB_N means that there exists a positive constant C, independent of N, such that C⁻¹A_NB_NCA_N.This extends the well-known Kashin theorem on the asymptotic order of the Kolmogorov widths of the Sobolev class of the periodic functions.     

Capture in linear functional differential games of pursuit

The problem of capture in a pursuit game which is described by a linear retarded functional differential equation is considered. The initial function belongs to the Sobolev space W₂⁽¹⁾. The target is either a subset of W₂⁽¹⁾ a point in W₂⁽¹⁾, a subset of the Euclidean space Eⁿ or a point of Eⁿ. There is capture if the initial function can be forced to the target by the pursuer no matter what the quarry does. The concept of capture therefore formalizes the concepts of controllability under unpredictable disturbances. This is proved to be equivalent to the controllability of an associated linear retarded functional differential equation. There is nothing in (2) (6) or (7) below which restricts the control sets to be of the same dimension as the phase space. Our results can be applied in (2) for example, if the constraint sets Q′, P′ are subsets of E^m and Eⁱ respectively with q(t) = C(t) q′(t), − p(t) = B(t) p′(t), q′(t) ε E^mp′(t) ε E^r and B(t) is an n × r′-matrices and C(t) an n × m-matrix.     

Asymptotic expansions in the conditional central limit theorem

Let X_n, n , be i.i.d. with mean 0, variance 1, and E(¦X_n¦^r) < ∞ for some r 3. Assume that Cramér's condition is fulfilled. We prove that the conditional probabilities P(1/√n Σ_{i = 1}ⁿ X_i t¦B) can be approximated by a modified Edgeworth expansion up to order o(1/n^{(r − 2)/2)}), if the distances of the set B from the σ-fields σ(X₁, …, X_n) are of order O(1/n^{(r − 2)/2)}(lg n)^β), where β < −(r − 2)/2 for r and β < −r/2 for r . An example shows that if we replace β < −(r − 2)/2 by β = −(r − 2)/2 for r (β < −r/2 by β = −r/2 for r ) we can only obtain the approximation order O(1/n^{(r − 2)/2)}) for r (O(lg lgn/n^{(r − 2)/2)}) for r ).     

Global nonparametric estimation of conditional quantile functions and their derivatives

Let (X, Y) be a random vector such that X is d-dimensional, Y is real valued, and θ(X) is the conditional αth quantile of Y given X, where α is a fixed number such that 0 < α < 1. Assume that θ is a smooth function with order of smoothness p > 0, and set r = (p − m)/(2p + d), where m is a nonnegative integer smaller than p. Let T(θ) denote a derivative of θ of order m. It is proved that there exists estimate of T(θ), based on a set of i.i.d. observations (X₁, Y₁), …, (X_n, Y_n), that achieves the optimal nonparametric rate of convergence n^−r in L_q-norms (1 ≤ q < ∞) restricted to compacts under appropriate regularity conditions. Further, it has been shown that there exists estimate of T(θ) that achieves the optimal rate (n/log n)^−r in L_∞-norm restricted to compacts.     

Coloring of distance graphs with intervals as distance sets

Let D be a set of positive integers. The distance graph G(Z,D) with distance set D is the graph with vertex set Z in which two vertices x,y are adjacent if and only if |x−y|D. The fractional chromatic number, the chromatic number, and the circular chromatic number of G(Z,D) for various D have been extensively studied recently. In this paper, we investigate the fractional chromatic number, the chromatic number, and the circular chromatic number of the distance graphs with the distance sets of the form D_m,[k,k^′]={1,2,…,m}−{k,k+1,…,k^′}, where m, k, and k^′ are natural numbers with m≥k^′≥k. In particular, we completely determine the chromatic number of G(Z,D_m,[2,k^′]) for arbitrary m, and k^′.     

On Rado numbers for

For all integers m3 and all natural numbers a₁,a₂,…,a_m−1, let n=R(a₁,a₂,…,a_m−1) represent the least integer such that for every 2-coloring of the set {1,2,…,n} there exists a monochromatic solution to

a₁x₁+a₂x₂++a_m−1x_m−1=x_m.