Correcting MM estimates for “fat” data sets

Regression MM estimates require the estimation of the error scale, and the determination of a constant that controls the efficiency. These two steps are based on the asymptotic results that are derived assuming that the number of predictors p remains fixed while the number of observations n tends to infinity, which means assuming that the ratio p/n is “small”. However, many high-dimensional data sets have a “large” value of p/n (say, ≥0.2). It is shown that the standard asymptotic results do not hold if p/n is large; namely that (a) the estimated scale underestimates the true error scale, and (b) that even if the scale is correctly estimated, the actual efficiency can be much lower than the nominal one. To overcome these drawbacks simple corrections for the scale and for the efficiency controlling constant are proposed, and it is demonstrated that these corrections improve on the estimate’s performance under both normal and contaminated data.     

A new approach for multistep numerical methods in several frequencies for perturbed oscillators

This article presents a new multi-step numerical method based on φ-function series and designed to integrate forced oscillators with precision. The new algorithm retains the good properties of the MDF_pPC methods while presenting the advantages of greater precision and that of integrating the non-perturbed problem without any discretization error. In addition, this new method permits a single formulation to be obtained from the MDF_pPC schemes independently of the parity of the number of steps, which facilitates the design of a computational algorithm thus permitting improved implementation in a computer.The construction of a new method for accurately integrating the homogenous problem is necessary if a method is sought which would be comparable to the methods based on Scheifele G-function series, very often used when problems of satellite orbital dynamics need to be resolved without discretization error.Greater precision compared to the MDF_pPC methods and other known integrators is demonstrated by overcoming stiff and highly oscillatory problems with the new method and comparing approximations obtained with those calculated by means of other integrators.     

A general mixing strategy for the ECB-Mix-ECB mode of operation

EME is an important mode of operation of a block cipher. It converts an n-bit block cipher into a strong pseudo-random permutation which works on longer length strings. In this short note, we generalize the mixing layer of EME. The generalization is done using a linear map ψ from Fn² to itself, where n is the block size of the underlying block cipher. A possible instantiation of ψ is using word oriented LFSRs. For n=128, this implementation of ψ results in the mixing layer being processed about twice as fast as that in the original EME mode of operation.     

Local likelihood regression in generalized linear single-index models with applications to microarray data

Searching for an effective dimension reduction space is an important problem in regression, especially for high-dimensional data such as microarray data. A major characteristic of microarray data consists in the small number of observations n and a very large number of genes p. This “large p, small n” paradigm makes the discriminant analysis for classification difficult. In order to offset this dimensionality problem a solution consists in reducing the dimension. Supervised classification is understood as a regression problem with a small number of observations and a large number of covariates. A new approach for dimension reduction is proposed. This is based on a semi-parametric approach which uses local likelihood estimates for single-index generalized linear models. The asymptotic properties of this procedure are considered and its asymptotic performances are illustrated by simulations. Applications of this method when applied to binary and multiclass classification of the three real data sets Colon, Leukemia and SRBCT are presented.     

A parallel algorithm for constructing reduced visibility graph and its FPGA implementation

A central geometric structure in applications such as robotic path planning and hidden line elimination in computer graphics is the visibility graph. A new parallel algorithm to construct the reduced visibility graph in a convex polygonal environment is presented in this paper. The computational complexity is O(p²log(n/p)) where p is the number of objects and n is the total number of vertices. A key feature of the algorithm is that it supports easy mapping to hardware. The algorithm has been simulated (and verified) using C. Results of hardware implementation show that the design operates at high speed requiring only small space. In particular, the hardware implementation operates at approximately 53 MHz and accommodates the reduced visibility graph of an environment with 80 vertices in one XCV3200E device.     

Computing the update of the repeated median regression line in linear time

The repeated median line estimator is a highly robust method for fitting a regression line to a set of n data points in the plane. In this paper, we consider the problem of updating the estimate after a point is removed from or added to the data set. This problem occurs, e.g., in statistical online monitoring, where the computational effort is often critical. We present a deterministic algorithm for the update working in O(n) time and O(n²) space.     

A robust conjugate-gradient algorithm which minimizes L-functions

A new conjugate-gradient algorithm which minimizes a function of n variables is given. The algorithm performs n orthogonal searches in each stage and hence has the property that it is robust, i.e. it will not easily fail on functions which have a large number of variables (n ? 10) nor on functions which have ‘ridge-like’ properties. A general class of functions called L-functions, which includes the class of quadratic functions as a special case, is defined, and it is shown that the algorithm has the property that it will converge to the minimum of an L-function in n (or less) 1-dimensional minimizations and (n ? 1) (or less) 1-dimensional pseudo-minimizations. Numerical experiments are included for systems of the second to the fortieth order, and based on these experiments, (assuming that the gradients are calculated numerically), the new algorithm appears to be more robust than Powell's [10], Fletcher-Powell's [11], and Jacobson-Oksman's [14] methods, faster than Rosenbrock's [9] method, and especially effective on high dimensional problems.     

Canonical D. C. programming techniques for solving a convex program with an additional constraint of multiplicative type

We consider a nonconvex programming problem of minimizing a linear functioncx over a convex setX?? ⁿ with an additional constraint ofmultiplicative type \(\prod _{i = 1}^p \psi _i (x) \leqslant 1\) , where the functionsψ _i are convex and positive onX. The main idea of our approach is to transform this problem, by usingp additional variables, into acanonical d.c. programming problem with the special structure that thereverse convex constraint involved does only depend on the newly introduced variables. This special structure suggests modifying certain techniques in d.c. programming in a way that the operations handling the nonconvexity are actually performed in the space of the additional variables. The resulting algorithm works very well whenp is small (in comparison withn).     

Robust performance assessment of feedback control systems

The proper measure of closed-loop performance variation in the presence of model-plant mismatch is discussed in this paper. A generalized closed-loop error transfer function, which is a special representation of the dual Youla parameter and has a close relationship with the pointwise ν-gap metric, is proposed as the suitable means of representing closed-loop performance variation in case of plant perturbation, and the closed-loop performance variation measure is accordingly defined as its maximum singular value frequency by frequency. It is shown that this measure is essential and informative in characterizing closed-loop performance variation. This measure is also shown to be readily applicable to on-line closed-loop performance assessment or monitoring, even without the explicit model of the plant. Its variant, defined as the η-function, which features the relative performance variation as well as generalized stability margin variation with respect to the nominal plant, is also discussed.     

Randomized parallel list ranking for distributed memory multiprocessors

We present a randomized parallel list ranking algorithm for distributed memory multiprocessors, using a BSP type model. We first describe a simple version which requires, with high probability, log(3p)+log ln(n)=Õ(logp+log logn) communication rounds (h-relations withh=Õ(n/p)) andÕ(n/p)) local computation. We then outline an improved version that requires high probability, onlyr?(4k+6) log(2/3p)+8=Õ(k logp) communication rounds wherek=min{i?0 |ln(i+1)n?(2/3p)²ⁱ⁺¹}. Notekn) is an extremely small number. Forn andp?4, the value ofk is at most 2. Hence, for a given number of processors,p, the number of communication rounds required is, for all practical purposes, independent ofn. Forn?1, 500,000 and 4?p?2048, the number of communication rounds in our algorithm is bounded, with high probability, by 78, but the actual number of communication rounds observed so far is 25 in the worst case. Forn?10010100 and 4?p?2048, the number of communication rounds in our algorithm is bounded, with high probability, by 118; and we conjecture that the actual number of communication rounds required will not exceed 50. Our algorithm has a considerably smaller member of communication rounds than the list ranking algorithm used in Reid-Miller’s empirical study of parallel list ranking on the Cray C-90.⁽¹⁾ To our knowledge, Reid-Miller’s algorithm⁽¹⁾ was the fastest list ranking implementation so far. Therefore, we expect that our result will have considerable practical relevance.     

Noise Level Estimation in High-Dimensional Linear Models

We consider the problem of estimating the noise level σ² in a Gaussian linear model Y = Xβ+σξ, where ξ ∈ ?ⁿ is a standard discrete white Gaussian noise and β ∈ ?^p an unknown nuisance vector. It is assumed that X is a known ill-conditioned n × p matrix with n ≥ p and with large dimension p. In this situation the vector β is estimated with the help of spectral regularization of the maximum likelihood estimate, and the noise level estimate is computed with the help of adaptive (i.e., data-driven) normalization of the quadratic prediction error. For this estimate, we compute its concentration rate around the pseudo-estimate ||Y ? Xβ||²/n.     

A smoothing principle for the Huber and other location M-estimators

A smoothing principle for M-estimators is proposed. The smoothing depends on the sample size so that the resulting smoothed M-estimator coincides with the initial M-estimator when n→∞. The smoothing principle is motivated by an analysis of the requirements in the proof of the Cramér-Rao bound. The principle can be applied to every M-estimator. A simulation study is carried out where smoothed Huber, ML-, and Bisquare M-estimators are compared with their non-smoothed counterparts and with Pitman estimators on data generated from several distributions with and without estimated scale. This leads to encouraging results for the smoothed estimators, and particularly the smoothed Huber estimator, as they improve upon the initial M-estimators particularly in the tail areas of the distributions of the estimators. The results are backed up by small sample asymptotics.     

Robust estimation in very small samples

In experimental science measurements are typically repeated only a few times, yielding a sample size n of the order of 3 to 8. One then wants to summarize the measurements by a central value and measure their variability, i.e. estimate location and scale. These estimates should preferably be robust against outliers, as reflected by their small-sample breakdown value. The estimator's stylized empirical influence function should be smooth, monotone increasing for location, and decreasing–increasing for scale. It turns out that location can be estimated robustly for n3, whereas for scale n4 is needed. Several well-known robust estimators are studied for small n, yielding some surprising results. For instance, the Hodges–Lehmann estimator equals the average when n=4. Also location M-estimators with auxiliary scale are studied, addressing issues like the difference between one-step and fully iterated M-estimators. Simultaneous M-estimators of location and scale (‘Huber's Proposal 2’) are considered as well, and it turns out that their lack of robustness is already noticeable for such small samples. Recommendations are given as to which estimators to use.     

Estimation of the dimension of chaotic dynamical systems using neural networks and robust location estimate

In this paper, we propose a new algorithm for the estimation of the dimension of chaotic dynamical systems using neural networks and robust location estimate.The basic idea is that a member of a time series can be optimally expressed as a deterministic function of the d past series values, where d is the dimension of the system. Moreover the neural networks’ learning ability is improved rapidly when the appropriate amount of information is provided to a neural structure which is as complex as needed.To estimate the dimension of a dynamical system, neural networks are trained to learn the component of the attractor expressed by a reconstructed vector in a suitable phase space whose embedding dimension m, has been estimated using the method of mutual information.     

Linear identification of ARMA processes

A new method for estimating the parameters of an ARMA process is presented. The method consists of three linear least-squares estimations. In the first an autoregressive model is fitted to the observation sequence, yielding an estimate of the values of the driving white noise sequence. Linear least squares is then used to fit an ARMA model to the observation and estimated white noise sequences. This model is used to filter the observation and estimated white noise sequences. Finally an ARMA model is fitted to the filtered sequences. It is shown that the resultant estimator is ‘p-consistent’ (the asymptotic bias tends to zero as the degree p of the autoregressive model tends to infinity) and is ‘p-efficient’ (the asymptotic efficiency approaches the theoretical maximum as p tends to infinity).     

Studies on the distribution of the shortest linear recurring sequences

The distribution of the shortest linear recurrence (SLR) sequences in the Z/(p) field and over the Z/(p^e) ring is studied. It is found that the length of the shortest linear recurrent (SLRL) is always equal to n/2, if n is even and n/2 + 1 if n is odd in the Z/(p) field, respectively. On the other hand, over the Z/(p^e) ring, the number of sequences with length n can also be calculated. The recurring distribution regulation of the shortest linear recurring sequences is also found. To solve the problem of calculating the SLRL, a new simple representation of the Berlekamp-Massey algorithm is developed as well.     

A combined synthetic and np scheme for detecting increases in fraction nonconforming

The applications of attribute control charts cover a wide variety of manufacturing processes in which quality characteristics cannot be measured on a continuous numerical scale or even a quantitative scale. The np control chart is an attribute chart used to monitor the fraction nonconforming p of a process. This chart is effective for detecting large process shifts in p. The attribute synthetic chart is also proposed to detect p shifts. It utilizes the information about the time interval or the Conforming Run Length (CRL) between two nonconforming samples. During the implementation of a synthetic chart, a sample is classified as nonconforming if the number d of nonconforming units falls beyond a warning limit. Unlike the np chart, the synthetic chart is more powerful to detect small and moderate p shifts. This article proposes a new scheme, the Syn-np chart, which comprises a synthetic chart and an np chart. Since the Syn-np chart has both the strength of the synthetic chart for quickly detecting small p shifts and the advantage of the np chart of being sensitive to large p shifts, it has a better and more uniform overall performance. Specifically, it is more effective than the np chart and synthetic chart by 73% and 31%, respectively, in terms of Weighted Average of Average Time to Signal (WAATS) over a wide range of p shifts under different conditions.     

Estimating the probability of misclassification and variate selection

This paper considers the problem of estimating the probability of misclassifying normal variates using the usual discriminant function when the parameters are unknown. The probability of misclassification is estimated, by Monte Carlo simulation, as a function of n₁ and n₂ (sample sizes), p (number of variates) and α (measure of separation between the two populations). The probability of misclassification is used to determine, for a given situation, the best number and subset of variates for various sample sizes. An example using real data is given.     

Complexity classes of provable recursive functions

Complexity measures and provable recursive functions (p-functions) are combined to define a p-measure as a measure for which Blum's axioms can be proved in a given axiomatic system. For p-measures, it is shown that the complexity class of a p-function contains only p-functions and that all p-functions form a single complexity class. Various other classes and a variation of a complexity measure, all suggested by the notion of provability, are also investigated. Classical results in complexity theory remain true when relativized to p-functions.     

On the average depth of asymmetric LC-tries

Andersson and Nilsson have already shown that the average depth Dn of random LC-tries is only Θ(log^∗n) when the keys are produced by a symmetric memoryless process, and that Dn=O(loglogn) when the process is asymmetric. In this paper we refine the second estimate by showing that asymptotically (with n→∞): , where n is the number of keys inserted in a trie, η=−log(1−h/h−∞), h=−plogp−qlogq is the entropy of a binary memoryless source with probabilities p, q=1−p (p≠q), and h−∞=−logmin(p,q).