Asymptotic minimax properties of M-estimators of scale

We ask whether or not the saddlepoint property holds, for robust M-estimation of scale, in gross-errors and Kolmogorov neighbourhoods of certain distributions. This is of interest since the saddlepoint property implies the minimax property — that the supremum of the asymptotic variance of an M-estimator is minimized by the maximum likelihood estimator for that member of the distributional class with minimum Fisher information. Our findings are exclusively negative — the saddlepoint property fails in all cases investigated.     

Asymptotic properties of sample quantiles from a finite population

In this paper we consider the problem of estimating quantiles of a finite population of size N on the basis of a finite sample of size n selected without replacement. We prove the asymptotic normality of the sample quantile and show that the scaled variance of the sample quantile converges to the asymptotic variance under a slight moment condition. We also consider the performance of the bootstrap in this case, and find that the usual (Efron’s) bootstrap method fails to be consistent, but a suitably modified version of the bootstrapped quantile converges to the same asymptotic distribution as the sample quantile. Consistency of the modified bootstrap variance estimate is also proved under the same moment conditions.     

The rank of sparse random matrices over finite fields

Let M be a random (n×n)-matrix over GF[q] such that for each entry M_ij in M and for each nonzero field element α the probability Pr[M_ij=α] is p/(q−1), where p=(log n−c)/n and c is an arbitrary but fixed positive constant. The probability for a matrix entry to be zero is 1−p. It is shown that the expected rank of M is n−𝒪(1). Furthermore, there is a constant A such that the probability that the rank is less than n−k is less than A/q^k. It is also shown that if c grows depending on n and is unbounded as n goes to infinity, then the expected difference between the rank of M and n is unbounded. © 1997 John Wiley & Sons, Inc. Random Struct. Alg., 10 , 407–419, 1997     

Two-scale sparse finite element approximations

To reduce computational cost,we study some two-scale finite element approximations on sparse grids for elliptic partial differential equations of second order in a general setting.Over any tensor product domain ?R~d with d = 2,3,we construct the two-scale finite element approximations for both boundary value and eigenvalue problems by using a Boolean sum of some existing finite element approximations on a coarse grid and some univariate fine grids and hence they are cheaper approximations.As applications,we obtain some new efficient finite element discretizations for the two classes of problem:The new two-scale finite element approximation on a sparse grid not only has the less degrees of freedom but also achieves a good accuracy of approximation.     

The finite sample breakdown point of PCS

The Projection Congruent Subset (PCS) is a new method for finding multivariate outliers. PCS returns an outlyingness index which can be used to construct affine equivariant estimates of multivariate location and scatter. In this note, we derive the finite sample breakdown point of these estimators.     

Mixed finite elements on sparse grids

Summary. This paper generalizes the idea of approximation on sparse grids to discrete differential forms that include )- and -conforming mixed finite element spaces as special cases. We elaborate on the construction of the spaces, introduce suitable nodal interpolation operators on sparse grids and establish their approximation properties. We discuss how nodal interpolation operators can be approximated. The stability of -conforming finite elements on sparse grids, when used to approximate second order elliptic problems in mixed formulation, is investigated both theoretically and in numerical experiments. Received November 2, 2000 / Revised version received October 23, 2001 / Published online January 30, 2002 This work was supported by DFG. This paper is dedicated to Ch. Zenger on the occasion of his 60th birthday.     

A sparse finite element method with high accuracy Part I

Summary. In this paper, we develop and analyze a new finite element method called the sparse finite element method for second order elliptic problems. This method involves much fewer degrees of freedom than the standard finite element method. We show nevertheless that such a sparse finite element method still possesses the superconvergence and other high accuracy properties same as those of the standard finite element method. The main technique in our analysis is the use of some integral identities. Received October 1, 1995 / Revised version received August 23, 1999 / Published online February 5, 2001     

The bias of k-step M-estimators

It is well-known that k-step M-estimators can yield a high efficiency without losing the breakdown point of the initial estimator. In this note we derive their bias curves. In the location framework the bias increases only slightly with k, but in the scale case the bias curves change considerably.     

Parametric estimation with a class of M-estimators

Consider a class of M-estimators indexed by a criterion function ψ. When the function ψ is taken to be in a class of functions $ \mathcal{F} $ \mathcal{F} , a family of processes indexed by the class $ \mathcal{F} $ \mathcal{F} is obtained and called M-processes. Pooling the M-estimators in such class may be used to define new kind of estimators. In order to get the asymptotic properties of these pooled estimators, the convergence in probability of the corresponding M-process is studied uniformly on $ \mathcal{F} $ \mathcal{F} together with their weak convergence towards a Gaussian process. An application to location estimation is presented and discussed.     

On solving sparse algebraic equations over finite fields

A system of algebraic equations over a finite field is called sparse if each equation depends on a small number of variables. In this paper new deterministic algorithms for solving such equations are presented. The mathematical expectation of their running time is estimated. These estimates are at present the best theoretical bounds on the complexity of solving average instances of the above problem. In characteristic 2 the estimates are significantly lower the worst case bounds provided by SAT solvers.     

Basis-exchange properties of sparse paving matroids

It has been conjectured that, asymptotically, almost all matroids are sparse paving matroids. We provide evidence for five long-standing, basis-exchange conjectures by proving them for this large class of matroids.     

Multilevel algorithms for finite difference discretizations on sparse grids

We propose some algorithms to solve the system of linear equations arising from the finite difference discretization on sparse grids. For this, we will use the multilevel structure of the sparse grid space or its full grid subspaces, respectively.     

Optimal control of a finite dam with a sample path constraint

In this paper, we discuss the 2-stage output procedure of a finite dam under the condition that water must be released by a fixed time. From this standpoint, the reservoir model we consider is subject to a sample path constraint and has a more general cost function than the earlier contributions. We analytically derive explicit formulas for the long-run average and the expected total discounted costs for an infinite time span and numerically calculate the optimal control policy. Finally, the optimal policy is compared with one by Zuckerman [1] and the effect of the fixed release time is discussed further.     

Numerical comparison of preconditionings for large sparse finite element problems

A numerical study of the efficiency of the modified conjugate gradients (MCG) is performed using different preconditioning schemes. The MCG behavior is evaluated in connection with the solution of large linear sets of symmetric positive definite (p.d.) equations, arising from the finite element (f.e.) integration of partial differential equations of parabolic and elliptic type and the analysis of the leftmost eingenspectrum of the corresponding matrices. A simple incomplete Cholesky factorization ICCG(O) having the same sparsity pattern as the original problem is compared with a more complex technique ICAJ (Ψ) where the triangular factor is allowed to progressively fill in depending on a rejection parameter Ψ. The performance of the preconditioning algorithms is explored on finite element equations whose size N ranges between 150 and 2300. The results show that an optimal Ψ_opt may be found which minimizes the overall CPU time for the solution of both the linear system and the eigenproblem. The comparison indicates that ICAJ (Ψ_opt) is not significantly more efficient than ICCG(O), which therefore appears to be a simple, robust, and reliable method for the preconditioning of large sparse finite element models.     

Symmetrised M-estimators of multivariate scatter

In this paper we introduce a family of symmetrised M-estimators of multivariate scatter. These are defined to be M-estimators only computed on pairwise differences of the observed multivariate data. Symmetrised Huber's M-estimator and Dümbgen's estimator serve as our examples. The influence functions of the symmetrised M-functionals are derived and the limiting distributions of the estimators are discussed in the multivariate elliptical case to consider the robustness and efficiency properties of estimators. The symmetrised M-estimators have the important independence property; they can therefore be used to find the independent components in the independent component analysis (ICA).     

Groups with given properties of finite subgroups

Suppose that in every finite even order subgroup F of a periodic group G, the equality [u, x]² = 1 holds for any involution u of F and for an arbitrary element x of F. Then the subgroup I generated by all involutions in G is locally finite and is a 2-group. In addition, the normal closure of every subgroup of order 2 in G is commutative.     

Asymptotic linear expansion of regularized M-estimators

Annals of the Institute of Statistical Mathematics - Parametric high-dimensional regression requires regularization terms to get interpretable models. The respective estimators correspond to...     

Distribution-free consistency of kernel non-parametric M-estimators

We prove that in the case of independent and identically distributed random vectors (X_i,Y_i) a class of kernel type M-estimators is universally and strongly consistent for conditional M-functionals. The term universal means that the strong consistency holds for all joint probability distributions of (X,Y). The conditional M-functional minimizes (2.2) for almost every x. In the case M(y)=|y| the conditional M-functional coincides with the L₁-functional and with the conditional median.