Adaptive confidence region for the direction in semiparametric regressions

In this paper we aim to construct adaptive confidence region for the direction of ξ in semiparametric models of the form Y=G(ξ^TX,ε) where G(⋅) is an unknown link function, ε is an independent error, and ξ is a p_n×1 vector. To recover the direction of ξ, we first propose an inverse regression approach regardless of the link function G(⋅); to construct a data-driven confidence region for the direction of ξ, we implement the empirical likelihood method. Unlike many existing literature, we need not estimate the link function G(⋅) or its derivative. When p_n remains fixed, the empirical likelihood ratio without bias correlation can be asymptotically standard chi-square. Moreover, the asymptotic normality of the empirical likelihood ratio holds true even when the dimension p_n follows the rate of p_n=o(n^1/4) where n is the sample size. Simulation studies are carried out to assess the performance of our proposal, and a real data set is analyzed for further illustration.     

Berry-Esseen bounds for wavelet estimator in a regression model with linear process errors

In this paper, we derive the Berry-Esseen bounds of the wavelet estimator for a nonparametric regression model with linear process errors generated by φ-mixing sequences. As application, by the suitable choice of some constants, the convergence rate O(n^−1/6) of uniformly asymptotic normality of the wavelet estimator is obtained. Our results generalize some known results in the literature.     

Application of fast spherical Fourier transform to density estimation

This paper is on density estimation on the 2-sphere, S², using the orthogonal series estimator corresponding to spherical harmonics. In the standard approach of truncating the Fourier series of the empirical density, the Fourier transform is replaced with a version of the discrete fast spherical Fourier transform, as developed by Driscoll and Healy. The fast transform only applies to quantitative data on a regular grid. We will apply a kernel operator to the empirical density, to produce a function whose values at the vertices of such a grid will be the basis for the density estimation. The proposed estimation procedure also contains a deconvolution step, in order to reduce the bias introduced by the initial kernel operator. The main issue is to find necessary conditions on the involved discretization and the bandwidth of the kernel operator, to preserve the rate of convergence that can be achieved by the usual computationally intensive Fourier transform. Density estimation is considered in L²(S²) and more generally in Sobolev spaces H_v(S²), any v?0, with the regularity assumption that the probability density to be estimated belongs to H_s(S²) for some s>v. The proposed technique to estimate the Fourier transform of an unknown density keeps computing cost down to order O(n), where n denotes the sample size.     

A third-order optimum property of the maximum likelihood estimator

Let θ⁽ⁿ⁾ denote the maximum likelihood estimator of a vector parameter, based on an i.i.d. sample of size n. The class of estimators θ⁽ⁿ⁾ + n^?1q(θ⁽ⁿ⁾), with q running through a class of sufficiently smooth functions, is essentially complete in the following sense: For any estimator T⁽ⁿ⁾ there exists q such that the risk of θ⁽ⁿ⁾ + n^?1q(θ⁽ⁿ⁾) exceeds the risk of T⁽ⁿ⁾ by an amount of order o(n^?1) at most, simultaneously for all loss functions which are bounded, symmetric, and neg-unimodal. If $\text{q}{}^1$ is chosen such that $\text{θ}{}^{\mathrm{(n)}}\text{+ n}{}^{\mathrm{?1}}\text{q}{}^1\text{(θ}{}^{\mathrm{(n)}}\text{)}$ is unbiased up to $\text{o(n}{}^{\mathrm{<mtext>?1</mtext><mtext>2</mtext>}}\text{)}$, then this estimator minimizes the risk up to an amount of order o(n^?1) in the class of all estimators which are unbiased up to $\text{o(n}{}^{\mathrm{<mtext>?1</mtext><mtext>2</mtext>}}\text{)}$.The results are obtained under the assumption that T⁽ⁿ⁾ admits a stochastic expansion, and that either the distributions have—roughly speaking—densities with respect to the lebesgue measure, or the loss functions are sufficiently smooth.     

Optimum two level fractional factorial plans for model identification and discrimination

Model identification and discrimination are two major statistical challenges. In this paper we consider a set of models M_k for factorial experiments with the parameters representing the general mean, main effects, and only k out of all two-factor interactions. We consider the class D of all fractional factorial plans with the same number of runs having the ability to identify all the models in M_k, i.e., the full estimation capacity.The fractional factorial plans in D with the full estimation capacity for k?2 are able to discriminate between models in M_u for u?k^*, where k^*=(k/2) when k is even, k^*=((k-1)/2) when k is odd. We obtain fractional factorial plans in D satisfying the six optimality criterion functions AD, AT, AMCR, GD, GT, and GMCR for 2^m factorial experiments when m=4 and 5. Both single stage and multi-stage (hierarchical) designs are given. Some results on estimation capacity of a fractional factorial plan for identifying models in M_k are also given. Our designs D4.1 and D10 stand out in their performances relative to the designs given in Li and Nachtsheim [Model-robust factorial designs, Technometrics 42(4) (2000) 345-352.] for m=4 and 5 with respect to the criterion functions AD, AT, AMCR, GD, GT, and GMCR. Our design D4.2 stands out in its performance relative the Li-Nachtsheim design for m=4 with respect to the four criterion functions AT, AMCR, GT, and GMCR. However, the Li-Nachtsheim design for m=4 stands out in its performance relative to our design D4.2 with respect to the criterion functions AD and GD. Our design D14 does have the full estimation capacity for k=5 but the twelve run Li-Nachtsheim design does not have the full estimation capacity for k=5.     

Approximation algorithms for art gallery problems in polygons

In this paper, we present approximation algorithms for minimum vertex and edge guard problems for polygons with or without holes with a total of n vertices. For simple polygons, approximation algorithms for both problems run in O(n⁴) time and yield solutions that can be at most O(logn) times the optimal solution. For polygons with holes, approximation algorithms for both problems give the same approximation ratio of O(logn), but the running time of the algorithms increases by a factor of n to O(n⁵).     

Corrected version of AIC for selecting multivariate normal linear regression models in a general nonnormal case

This paper deals with the bias reduction of Akaike information criterion (AIC) for selecting variables in multivariate normal linear regression models when the true distribution of observation is an unknown nonnormal distribution. We propose a corrected version of AIC which is partially constructed by the jackknife method and is adjusted to the exact unbiased estimator of the risk when the candidate model includes the true model. It is pointed out that the influence of nonnormality in the bias of our criterion is smaller than the ones in AIC and TIC. We verify that our criterion is better than the AIC, TIC and EIC by conducting numerical experiments.     

On the unlinking conjecture of independent polynomial functions

The celebrated U-conjecture states that under the N_n(0,I_n) distribution of the random vector X=(X₁,…,X_n) in Rⁿ, two polynomials P(X) and Q(X) are unlinkable if they are independent [see Kagan et al., Characterization Problems in Mathematical Statistics, Wiley, New York, 1973]. Some results have been established in this direction, although the original conjecture is yet to be proved in generality. Here, we demonstrate that the conjecture is true in an important special case of the above, where P and Q are convex nonnegative polynomials with P(0)=0.     

Hermite series estimates of a probability density and its derivatives

The following estimate of the pth derivative of a probability density function is examined: $\text{Σ}{}_{\mathrm{k\; =\; 0}}{}^{\mathrm{N}}\text{a}\text{?}{}_{\mathrm{k}}\text{h}{}_{\mathrm{k}}\text{(x)}$, where h_k is the kth Hermite function and $\text{a}\text{?}{}_{\mathrm{k}}\text{= (}\text{(?1)}{}^{\mathrm{p}}\text{n}\text{)}$Σ_{i = 1}ⁿh_k^(p)(X_i) is calculated from a sequence X₁,…, X_n of independent random variables having the common unknown density. If the density has r derivatives the integrated square error converges to zero in the mean and almost completely as rapidly as O(n^?α) and O(n^?α log n), respectively, where $\text{α =}\text{2(r ? p)}\text{(2r + 1)}$. Rates for the uniform convergence both in the mean square and almost complete are also given. For any finite interval they are O(n^?β) and $\text{O(n}{}^{\mathrm{<mtext>?\beta </mtext><mtext>2</mtext>}}\text{log}\text{n)}$, respectively, where $\text{β =}\text{(2(r ? p) ? 1)}\text{(2r + 1)}$.     

On the complexity of calculating factorials

It is shown that n! can be evaluated with time complexity O(log log nM (n log n)), where M(n) is the complexity of multiplying two n-digit numbers together. This is effected, in part, by writing n! in terms of its prime factors. In conjunction with a fast multiplication this yields an O(n(log n log log n)²) complexity algorithm for n!. This might be compared to computing n! by multiplying 1 times 2 times 3, etc., which is ω(n² log n) and also to computing n! by binary splitting which is O(log nM(n log n)).     

Asymptotic power comparison of three tests in GMANOVA when the number of observed points is large

This paper is concerned with the testing problem of generalized multivariate linear hypothesis for the mean in the growth curve model(GMANOVA). Our interest is the case in which the number of the observed points p is relatively large compared to the sample size N. Asymptotic expansions of the non-null distributions of the likelihood ratio criterion, Lawley-Hotelling’s trace criterion and Bartlett-Nanda-Pillai’s trace criterion are derived under the asymptotic framework that N and p go to infinity together, while p/N→c∈(0,1). It also can be confirmed that Rothenberg’s condition on the magnitude of the asymptotic powers of the three tests is valid when p is relatively large, theoretically and numerically.     

Nonparametric estimation of mixed partial derivatives of a multivariate density

On the basis of a random sample of size n on an m-dimensional random vector X, this note proposes a class of estimators f_n^(p) of f^(p), where f is a density of X w.r.t. a σ-finite measure dominated by the Lebesgue measure on R^m, p = (p₁,…,p_m), p_j ≥ 0, fixed integers, and for x = (x₁,…,x_m) in R^m, f^(p)(x) = ?^p₁+…+p_m f(x)/(?^p₁x₁ … ?^p_mx_m). Asymptotic unbiasedness as well as both almost sure and mean square consistencies of f_n^(p) are examined. Further, a necessary and sufficient condition for uniform asymptotic unbisedness or for uniform mean square consistency of f_n^(p) is given. Finally, applications of estimators of this note to certain statistical problems are pointed out.     

Efficient partition trees

We prove a theorem on partitioning point sets inE ^d (d fixed) and give an efficient construction of partition trees based on it. This yields a simplex range searching structure with linear space,O(n logn) deterministic preprocessing time, andO(n ^1?1/d (logn) ^O(1)) query time. WithO(nlogn) preprocessing time, where δ is an arbitrary positive constant, a more complicated data structure yields query timeO(n ^1?1/d (log logn) ^O(1)). This attains the lower bounds due to Chazelle [C1] up to polylogarithmic factors, improving and simplifying previous results of Chazelleet al. [CSW]. The partition result implies that, forr ^d≤n ^1?δ, a (1/r)-approximation of sizeO(r ^d) with respect to simplices for ann-point set inE ^d can be computed inO(n logr) deterministic time. A (1/r)-cutting of sizeO(r ^d) for a collection ofn hyperplanes inE ^d can be computed inO(n logr) deterministic time, provided thatr≤n ^1/(2d?1).     

An exact algorithm for MAX-CUT in sparse graphs

We study exact algorithms for the MAX-CUT problem. Introducing a new technique, we present an algorithmic scheme that computes a maximum cut in graphs with bounded maximum degree. Our algorithm runs in time O^*(2^(1-(2/Δ))n). We also describe a MAX-CUT algorithm for general graphs. Its time complexity is O^*(2^mn/(m+n)). Both algorithms use polynomial space.     

Extremal problems on triangle areas in two and three dimensions

The study of extremal problems on triangle areas was initiated in a series of papers by Erd?s and Purdy in the early 1970s. In this paper we present new results on such problems, concerning the number of triangles of the same area that are spanned by finite point sets in the plane and in 3-space, and the number of distinct areas determined by the triangles.In the plane, our main result is an O(n44/19)=O(n^2.3158) upper bound on the number of unit-area triangles spanned by n points, which is the first breakthrough improving the classical bound of O(n7/3) from 1992. We also make progress in a number of important special cases. We show that: (i) For points in convex position, there exist n-element point sets that span Ω(nlogn) triangles of unit area. (ii) The number of triangles of minimum (nonzero) area determined by n points is at most ; there exist n-element point sets (for arbitrarily large n) that span (6/π²−o(1))n² minimum-area triangles. (iii) The number of acute triangles of minimum area determined by n points is O(n); this is asymptotically tight. (iv) For n points in convex position, the number of triangles of minimum area is O(n); this is asymptotically tight. (v) If no three points are allowed to be collinear, there are n-element point sets that span Ω(nlogn) minimum-area triangles (in contrast to (ii), where collinearities are allowed and a quadratic lower bound holds).In 3-space we prove an O(n17/7β(n))=O(n^2.4286) upper bound on the number of unit-area triangles spanned by n points, where β(n) is an extremely slowly growing function related to the inverse Ackermann function. The best previous bound, O(n8/3), is an old result of Erd?s and Purdy from 1971. We further show, for point sets in 3-space: (i) The number of minimum nonzero area triangles is at most n²+O(n), and this is worst-case optimal, up to a constant factor. (ii) There are n-element point sets that span Ω(n4/3) triangles of maximum area, all incident to a common point. In any n-element point set, the maximum number of maximum-area triangles incident to a common point is O(n4/3+ε), for any ε>0. (iii) Every set of n points, not all on a line, determines at least Ω(n2/3/β(n)) triangles of distinct areas, which share a common side.     

Minimum distance classification rules for high dimensional data

In this article, the problem of classifying a new observation vector into one of the two known groups Π_i,i=1,2, distributed as multivariate normal with common covariance matrix is considered. The total number of observation vectors from the two groups is, however, less than the dimension of the observation vectors. A sample-squared distance between the two groups, using Moore-Penrose inverse, is introduced. A classification rule based on the minimum distance is proposed to classify an observation vector into two or several groups. An expression for the error of misclassification when there are only two groups is derived for large p and n=O(p^δ),0<δ<1.     

The just-in-time scheduling problem in a flow-shop scheduling system

We study the problem of maximizing the weighted number of just-in-time (JIT) jobs in a flow-shop scheduling system under four different scenarios. The first scenario is where the flow-shop includes only two machines and all the jobs have the same gain for being completed JIT. For this scenario, we provide an O(n³) time optimization algorithm which is faster than the best known algorithm in the literature. The second scenario is where the job processing times are machine-independent. For this scenario, the scheduling system is commonly referred to as a proportionate flow-shop. We show that in this case, the problem of maximizing the weighted number of JIT jobs is NP-hard in the ordinary sense for any arbitrary number of machines. Moreover, we provide a fully polynomial time approximation scheme (FPTAS) for its solution and a polynomial time algorithm to solve the special case for which all the jobs have the same gain for being completed JIT. The third scenario is where a set of identical jobs is to be produced for different customers. For this scenario, we provide an O(n³) time optimization algorithm which is independent of the number of machines. We also show that the time complexity can be reduced to O(n log n) if all the jobs have the same gain for being completed JIT. In the last scenario, we study the JIT scheduling problem on m machines with a no-wait restriction and provide an O(mn²) time optimization algorithm.     

Displacement structure approach to Chebyshev-Vandermonde and related matrices

In this paper we use the displacement structure concept to introduce a new class of matrices, designated asChebyshev-Vandermonde-like matrices, generalizing ordinary Chebyshev-Vandermonde matrices, studied earlier by different authors. Among other results the displacement structure approach allows us to give a nice explanation for the form of the Gohberg-Olshevsky formulas for the inverses of ordinary Chebyshev-Vandermonde matrices. Furthermore, the fact that the displacement structure is inherited by Schur complements leads to a fastO(n ²) implementation of Gaussian elimination withpartial pivoting for Chebyshev-Vandermonde-like matrices.     

On some algorithmic problems regarding the hairpin completion

We consider a few algorithmic problems regarding the hairpin completion. The first problem we consider is the membership problem of the hairpin and iterated hairpin completion of a language. We propose an O(nf(n)) and O(n²f(n)) time recognition algorithm for the hairpin completion and iterated hairpin completion, respectively, of a language recognizable in O(f(n)) time. We show that the n factor is not needed in the case of hairpin completion of regular and context-free languages. The n² factor is not needed in the case of iterated hairpin completion of context-free languages, but it is reduced to n in the case of iterated hairpin completion of regular languages. We then define the hairpin completion distance between two words and present a cubic time algorithm for computing this distance. A linear time algorithm for deciding whether or not the hairpin completion distance with respect to a given word is connected is also discussed. Finally, we give a short list of open problems which appear attractive to us.