Complexity of Reducing the Delay between Two Nodes by Node-based and Edge-based Upgrading Strategies

For a pair of nodes s, t in an undirected graph G = (V, A) and a given level U of allowable delay, we would like to modify the network by node-based or edge-based upgrading strategies to make the delay between s and t not greater than U. In this paper, we present some NP-hard results for the delay improvement problems.     

Asymptotics for Kernel Estimation of Slicing Average Third-Moment Estimation

To estimate central dimension-reduction space in multivariate nonparametric rcgression, Sliced Inverse Regression （SIR）, Sliced Average Variance Estimation （SAVE） and Slicing Average Third-moment Estimation （SAT） have been developed, Since slicing estimation has very different asymptotic behavior for SIR, and SAVE, the relevant study has been madc case by case, when the kernel estimators of SIH and SAVE share similar asymptotic properties. In this paper, we also investigate kernel estimation of SAT. We. prove the asymptotic normality, and show that, compared with tile existing results, the kernel Slnoothing for SIR, SAVE and SAT has very similar asymptotic behavior,     

Triangular Cm interpolation by rational functions

Two general local C^m triangular interpolation schemes by rational functions from C^m data are proposed for any nonnegative integer m. The schemes can have either 2m+1 order algebraic precision if the required data are given on vertices and edges, or m+E[m/2]+1 or m+1 order algebraic precision if the data are given only at vertices. The orders of the interpolation error are estimated. Examples that show the correctness and effectiveness of the scheme are presented. Supported partially by NSFC under Project 1967108 and Croucher Foundation of Hong Kong; Supported also by FRG of Hong Kong Paptist University.     

Maximum variance of order statistics

Yang (1982,Bull. Inst. Math. Acad. Sinica,10(2), 197–204) proved that the variance of the sample median cannot exceed the population variance. In this paper, the upper bound for the variance of order statistics is derived, and it is shown that this is attained by Bernoulli variates only. The proof is based on Hoeffding's identity for the covariance.     

Bayes estimation of number of signals

Bayes estimation of the number of signals, q, based on a binomial prior distribution is studied. It is found that the Bayes estimate depends on the eigenvalues of the sample covariance matrix S for white-noise case and the eigenvalues of the matrix S ₂ (S ₁+A)^–1 for the colored-noise case, where S ₁ is the sample covariance matrix of observations consisting only noise, S ₂ the sample covariance matrix of observations consisting both noise and signals and A is some positive definite matrix. Posterior distributions for both the cases are derived by expanding zonal polynomial in terms of monomial symmetric functions and using some of the important formulae of James (1964, Ann. Math. Statist., 35, 475–501).     

Some Properties of A Lack-of-Fit Test for a Linear Errors in Variables Model

The relationship between the linear errors-in-variables model and the corresponding ordinary linear model in statistical inference is studied. It is shown that normality of the distribution of covariate is a necessary and sufficient condition for the equivalence. Therefore, testing for lack-of-fit in linear errors-in-variables model can be converted into testing for it in the corresponding ordinary linear model under normality assumption. A test of score type is constructed and the limiting chi-squared distribution is derived under the null hypothesis.Furthermore, we discuss the power of the test and the choice of the weight function involved in the test statistic.     

The superconvergence of Newton–Cotes rules for the Hadamard finite-part integral on an interval

We study the general (composite) Newton–Cotes rules for the computation of Hadamard finite-part integral with the second-order singularity and focus on their pointwise superconvergence phenomenon, i.e., when the singular point coincides with some a priori known point, the convergence rate is higher than what is globally possible. We show that the superconvergence rate of the (composite) Newton–Cotes rules occurs at the zeros of a special function and prove the existence of the superconvergence points. Several numerical examples are provided to validate the theoretical analysis. The work of J. Wu was partially supported by the National Natural Science Foundation of China (No. 10671025) and a grant from the Research Grants Council of the Hong Kong Special Administrative Region, China (No. CityU 102507). The work of W. Sun was supported in part by a grant from the Research Grants Council of the Hong Kong Special Administrative Region, China (No. City U 102507) and the National Natural Science Foundation of China (No. 10671077).     

Empirical likelihood for partial linear models

In this paper the empirical likelihood method due to Owen (1988,Biometrika,75, 237–249) is applied to partial linear random models. A nonparametric version of Wilks' theorem is derived. The theorem is then used to construct confidence regions of the parameter vector in the partial linear models, which has correct asymptotic coverage. A simulation study is conducted to compare the empirical likelihood and normal approximation based method. Research supported by NNSF of China and a grant to the first author for his excellent Ph.D. dissertation work in China. Research supported by Hong Kong RGC CERG No. HKUST6162/97P.     

Searching for extensible Korobov rules

Extensible lattice sequences have been proposed and studied in [F.J. Hickernell, H.S. Hong, Computing multivariate normal probabilities using rank-1 lattice sequences, in: G.H. Golub, S.H. Lui, F.T. Luk, R.J. Plemmons (Eds.), Proceedings of the Workshop on Scientific Computing (Hong Kong), Singapore, Springer, Berlin, 1997, pp. 209–215; F.J. Hickernell, H.S. Hong, P. L’Ecuyer, C. Lemieux, Extensible lattice sequences for quasi-Monte Carlo quadrature, SIAM J. Sci. Comput. 22 (2001) 1117–1138; F.J. Hickernell, H.Niederreiter, The existence of good extensible rank-1 lattices, J. Complexity 19 (2003) 286–300]. For the special case of extensible Korobov sequences, parameters can be found in [F.J. Hickernell, H.S. Hong, P. L’Ecuyer, C.Lemieux, Extensible lattice sequences for quasi-Monte Carlo quadrature, SIAM J. Sci. Comput. 22 (2001) 1117–1138]. The searches made to obtain these parameters were based on quality measures that look at several projections of the lattice. Because it is often the case in practice that low-dimensional projections are very important, it is of interest to find parameters for these sequences based on measures that look more closely at these projections. In this paper, we prove the existence of “good” extensible Korobov rules with respect to a quality measure that considers two-dimensional projections. We also report results of experiments made on different problems where the newly obtained parameters compare favorably with those given in [F.J. Hickernell, H.S. Hong, P. L’Ecuyer, C. Lemieux, Extensible lattice sequences for quasi-Monte Carlo quadrature, SIAM J. Sci. Comput. 22 (2001) 1117–1138].     

Asymptotic theorems for estimating the distribution function under random truncation

Representation theorem and local asymptotic minimax theorem are derived for nonparametric estimators of the distribution function on the basis of randomly truncated data. The convolution-type representation theorem asserts that the limiting process of any regular estimator of the distribution function is at least as dispersed as the limiting process of the product-limit estimator. The theorems are similar to those results for the complete data case due to Beran (1977, Ann. Statist., 5, 400–404) and for the censored data case due to Wellner (1982, Ann. Statist., 10, 595–602). Both likelihood and functional approaches are considered and the proofs rely on the method of Begun et al. (1983, Ann. Statist., 11, 432–452) with slight modifications.Division of Biostatistics, School of Public Health, Columbia Univ.     

The complexity of recognizing linear systems with certain integrality properties

Let A be a 0 − 1 matrix with precisely two 1’s in each column and let 1 be the all-one vector. We show that the problems of deciding whether the linear system (1) defines an integral polyhedron, (2) is totally dual integral (TDI), and (3) box-totally dual integral (box-TDI) are all co-NP-complete, thereby confirming the conjecture on NP-hardness of recognizing TDI systems made by Edmonds and Giles in 1984. Supported in part by NSA grant H98230-05-1-0081 and NSF grants DMS-0556091 and ITR-0326387. Supported in part by the Research Grants Council of Hong Kong and Seed Funding for Basic Research of HKU.     

Weighted Kaplan-Meier Tests for Umbrella Alternatives

The problem of testing for umbrella alternatives in a one-way layout with right-censored survival data is considered. Testing procedures based on the two-sample weighted Kaplan-Meier statistics suggested by Pepe and Fleming (1989, Biometrics, 45, 497–507; 1991, J. Roy. Statist. Soc. Ser. B, 53, 341–352) are suggested for both cases when the peak of the umbrella is known or unknown. The asymptotic relative efficiency of the weighted Kaplan-Meier test and the weighted logrank test proposed by Chen and Wolfe (2000, Statist. Sinica, 10, 595–612) is computed for the umbrella peak-known setting where the piecewise exponential survival distributions have the proportional or crossing hazards, or the related hazards differ at early or late times. Moreover, the results of a Monte Carlo study are presented to investigate the level and power performances of the umbrella tests. Finally, application of the proposed procedures to an appropriated data set is illustrated.     

Auxiliary space preconditioning in H 0(curl; Ω)

We adapt the principle of auxiliary space preconditioning as presented in [J. Xu, The auxiliary space method and optimal multigrid preconditioning techniques for unstructured grids, Computing, 56 (1996), pp. 215–235.] to H (curl; ω)-elliptic variational problems discretized by means of edge elements. The focus is on theoretical analysis within the abstract framework of subspace correction. Employing a Helmholtz-type splitting of edge element vector fields we can establish asymptotic h-uniform optimality of the preconditioner defined by our auxiliary space method. This author was fully supported by Hong Kong RGC grant (Project No. 403403) This author acknowledges the support from a Direct Grant of CUHK during his visit at The Chinese University of Hong Kong.     

Principal Component Analysis from the Multivariate Familial Correlation Matrix

This paper considers principal component analysis (PCA) in familial models, where the number of siblings can differ among families. S. Konishi and C. R. Rao (1992, Biometrika79, 631–641) used the unified estimator of S. Konishi and C. G. Khatri (1990, Ann. Inst. Statist. Math.42, 561–580) to develop a PCA derived from the covariance matrix. However, because of the lack of invariance to componentwise change of scale, an analysis based on the correlation matrix is often preferred. The asymptotic distribution of the estimated eigenvalues and eigenvectors of the correlation matrix are derived under elliptical sampling. A Monte Carlo simulation shows the usefulness of the asymptotic expressions for samples as small as N=25 families.     

On the admissibility of an estimator of a normal mean vector under a linex loss function

For ap-variate normal mean with known variances, the model proposed by Zellner (1986,J. Amer. Statist. Assoc.,81, 446–451) is discussed in a slightly different framework. A generalized Bayes estimate is derived from a three-stage Bayes point of view under the asymmetric loss function, and the admissibility of such estimators is proved.     

A proof of independent Bartlett correctability of nested likelihood ratio tests

It is well known that likelihood ratio statistic is Bartlett correctable. We consider decomposition of a likelihood ratio statistic into 1 degree of freedom components based on sequence of nested hypotheses. We give a proof of the fact that the component likelihood ratio statistics are distributed mutually independently up to the order O(1/n) and each component is independently Bartlett correctable. This was implicit in Lawley (1956, Biometrika, 43, 295–303) and proved in Bickel and Ghosh (1990, Ann. Statist., 18, 1070–1090) using a Bayes method. We present a more direct frequentist proof.     

A Dynamic Programming Algorithm for the κ-Haplotyping Problem

The Minimum Fragments Removal （MFR） problem is one of the haplotyping problems： given a set of fragments, remove the minimum number of fragments so that the resulting fragments can be partitioned into k classes of non-conflicting subsets. In this paper, we formulate the κ-MFR problem as an integer linear programming problem, and develop a dynamic programming approach to solve the κ-MFR problem for both the gapless and gap eases.     

On the approximation of continuous time threshold ARMA processes

Threshold autoregressive (AR) and autoregressive moving average (ARMA) processes with continuous time parameter have been discussed in several recent papers by Brockwellet al. (1991,Statist. Sinica,1, 401–410), Tong and Yeung (1991,Statist. Sinica,1, 411–430), Brockwell and Hyndman (1992,International Journal Forecasting,8, 157–173) and Brockwell (1994,J. Statist. Plann. Inference,39, 291–304). A threshold ARMA process with boundary width 2>0 is easy to define in terms of the unique strong solution of a stochastic differential equation whose coefficients are piecewise linear and Lipschitz. The positive boundary-width is a convenient mathematical device to smooth out the coefficient changes at the boundary and hence to ensure the existence and uniqueness of the strong solution of the stochastic differential equation from which the process is derived. In this paper we give a direct definition of a threshold ARMA processes with =0 in the important case when only the autoregressive coefficients change with the level of the process. (This of course includes all threshold AR processes with constant scale parameter.) The idea is to express the distributions of the process in terms of the weak solution of a certain stochastic differential equation. It is shown that the joint distributions of this solution with =0 are the weak limits as 0 of the distributions of the solution with >0. The sense in which the approximating sequence of processes used by Brockwell and Hyndman (1992,International Journal Forecasting,8, 157–173) converges to this weak solution is also investigated. Some numerical examples illustrate the value of the latter approximation in comparison with the more direct representation of the process obtained from the Cameron-Martin-Girsanov formula. It is used in particular to fit continuous-time threshold models to the sunspot and Canadian lynx series.Research partially supported by National Science Foundation Research Grants DMS 9105745 and 9243648.     

Bogolyubov averaging and normalization procedures in nonlinear mechanics. IV

In this paper, we apply the theory developed in parts I-III [Ukr. Math. Zh.,46, No. 9, 1171–1188; No. 11, 1509–1526; No. 12, 1627–1646 (1994)] to some classes of problems. We consider linear systems in zero approximation and investigate the problem of invariance of integral manifolds under perturbations. Unlike nonlinear systems, linear ones have centralized systems, which are always decomposable. Moreover, restrictions connected with the impossibility of diagonalization of the coefficient matrix in zero approximation are removed. In conclusion, we apply the method of local asymptotic decomposition to some mechanical problems.Published in Ukrainskii Matematicheskii Zhurnal, Vol. 47, No. 8, pp. 1044–1068, August, 1995.This research was partially supported by the International Science Foundation, grant No. UB2000.