Bias phenomenon and compensation in multiple target tracking algorithms

Bias phenomenon in multiple target tracking has been observed for a long time. This paper is devoted to a study of the bias resulting from the miscorrelation in data association. One result of this paper is a necessary condition for miscorrelation to cause bias. Relying on the necessary condition and a model for data association process, techniques are developed to give general directions for where and how to compensate the bias related to miscorrelation in general tracking algorithms. Case studies on the bias phenomenon in two tracking algorithms, i.e., global nearest neighborhood (GNN) and joint probabilistic data association (JPDA), are launched as a practice of the ideas and results presented in this paper. The outcome of the examples illustrates and strongly supports our results. A discussion of several statistical issues is given in the end of this paper, in which the behavior for the bias in GNN and JPDA is studied.     

A multi-space data association algorithm for target tracking systems

In this paper, a multi-space data association algorithm based on the wavelet transform is proposed. In addition to carrying out the traditional hard logic data association in measurement space, the new algorithm updates the state of the target in the pattern space. Such a function significantly reduces the complicated environment misassociation effects on the data association. Simulation results show that the performance of the multi-spaced data association is much better than the existing data association algorithms in complicated clutter environments, such as the nearest-neighbor standard filter (NNSF), the probabilistic data association (PDA) and the joint probabilistic data association (JPDA). The computation of the multiple-space data association is much less than the aforementioned other existing data associations, and this new data association does not need any priori information of the environment. In complicated clutter environments, compared with the other data association, the new data association proposed in this paper is very robust, reliable and stable.     

Multiresolutional decomposition and modeling with an application to joint probabilistic data association

A multiresolutional approach for measurement decomposition and system modeling is presented in this paper. The decomposition is performed in both spatial and time domains and provides an excellent platform for developing computationally efficient algorithms. Using multiresolutional decomposition and modeling, a multiresolutional joint probabilistic data association (MR-JPDA) algorithm is developed for multiple target tracking. Monte Carlo simulations demonstrate that the computation of the MRJPDA algorithm is much less than the traditional joint probabilistic data association (JPDA) algorithm with a comparable performance.     

Constructions of general polynomial lattice rules based on the weighted star discrepancy

In this paper we study construction algorithms for polynomial lattice rules modulo arbitrary polynomials. Polynomial lattice rules are a special class of digital nets which yield well distributed point sets in the unit cube for numerical integration.Niederreiter obtained an existence result for polynomial lattice rules modulo arbitrary polynomials for which the underlying point set has a small star discrepancy and recently Dick, Leobacher and Pillichshammer introduced construction algorithms for polynomial lattice rules modulo an irreducible polynomial for which the underlying point set has a small (weighted) star discrepancy.In this work we provide construction algorithms for polynomial lattice rules modulo arbitrary polynomials, thereby generalizing the previously obtained results. More precisely we use a component-by-component algorithm and a Korobov-type algorithm. We show how the search space of the Korobov-type algorithm can be reduced without sacrificing the convergence rate, hence this algorithm is particularly fast. Our findings are based on a detailed analysis of quantities closely related to the (weighted) star discrepancy.     

Structure Algorithms for Partially Ordered Isotonic Regression

Abstract

An algorithm for isotonic regression is called a structure algorithm if it searches for a “solution partition”—that is, a class of sets on each of which the isotonic regression is a constant. We discuss structure algorithms for partially ordered isotonic regression. In this article we provide a new class of structure algorithms called the isotonic block class (IBC) type algorithms. One of these is called the isotonic block class with recursion method (IBCR) algorithm, which works for partially ordered isotonic regression. It is a generalization of the pooled adjacent violators algorithm and is simpler than the min-max algorithm. We also give a polynomial time algorithm—the isotonic block class with stratification (IBCS) algorithm for matrix-ordered isotonic regression. We demonstrate the efficiency of our IBCR algorithm by using simulation to estimate the relative frequencies of the numbers of level sets of isotonic regressions on certain two-dimensional grids with the matrix order.     

Fast Algorithms for Nonparametric Curve Estimation

Abstract

Naive implementations of local polynomial fits and kernel estimators require almost O(n ²) operations. In this article two fast O(n) algorithms for nonparametric local polynomial fitting are presented. They are based on updating normal equations. Numerical stability is guaranteed by controlling ill-conditioned situations for small bandwidths and data-tuned restarting of the updating procedure. Restarting at every output point results in a moderately fast but highly stable O(n ^7/5) algorithm. Applicability of algorithms is evaluated for estimation of regression curves and their derivatives. The idea is also applied to kernel estimators of regression curves and densities.     

A bias corrected nonparametric regression estimator

In this article, we propose a new method of bias reduction in nonparametric regression estimation. The proposed new estimator has asymptotic bias order h⁴, where h is a smoothing parameter, in contrast to the usual bias order h² for the local linear regression. In addition, the proposed estimator has the same order of the asymptotic variance as the local linear regression. Our proposed method is closely related to the bias reduction method for kernel density estimation proposed by Chung and Lindsay (2011). However, our method is not a direct extension of their density estimate, but a totally new one based on the bias cancelation result of their proof.     

A Unified Rounding Error Bound for Polynomial Evaluation

We present a unified rounding error bound for polynomial evaluation. The bound presented here takes the same general form for the evaluation of a polynomial written in any polynomial basis when the evaluation algorithm can be expressed as a linear recurrence or a first-order linear matrix recurrence relation. Examples of these situations are: Horner's algorithm in the evaluation of power series, Clenshaw's and Forsythe's algorithms in the evaluation of orthogonal polynomial series, de-Casteljau's algorithm for Bernstein polynomial series, the modification of Clenshaw's algorithms in the evaluation of Szeg polynomial series, and so on.     

Design an interactive virtual physics environment with uncertainties control to support motion tracking

The development of robot or character motion tracking algorithms is inherently a challenging task. This is more than ever true when the latest trends in motion tracking are considered. Some researchers can deal with kinematic and dynamic constraints induced by the mechanical structure. Another class of researchers fulfills various types of optimality conditions, yet others include means of dealing with uncertainties about the robot or character and its environment. In order to deal with the complexity of developing motion tracking algorithms, it is proposed in this paper to design an interactive virtual physics environment with uncertainties for motion tracking based on sliding mode control. The advantages of doing so are outlined and a virtual environment presented which is well suited to support motion tracking development. The environment makes full use of multi-body system dynamics and a robust sliding mode controller independent of model as simulation kernel. So the environment is capable of simulating setups which fulfill the requirements posed by state-of-the-art motion tracking algorithm development. The demonstration results verified the validity of the environment.     

Feedforward Design and Optimality Aspects for the Control of Mechatronic Systems

This paper considers the tracking controller design for a mechatronic handling system. The presented approach is based on Port-Hamiltonian systems and it achieves good tracking as well as good disturbance rejection based on a polynomial approach. A PBC controller stabilizes the trajectory and the feedforward part has to fulfill the given limitations and the time optimality. This approach avoids the solution of a boundary value problem and a real-time integration of the internal dynamics. (© 2011 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

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.     

Asymptotic Properties of Backfitting Estimators

When additive models with more than two covariates are fitted with the backfitting algorithm proposed by Buja et al. [2], the lack of explicit expressions for the estimators makes study of their theoretical properties cumbersome. Recursion provides a convenient way to extend existing theoretical results for bivariate additive models to models of arbitrary dimension. In the case of local polynomial regression smoothers, recursive asymptotic bias and variance expressions for the backfitting estimators are derived. The estimators are shown to achieve the same rate of convergence as those of univariate local polynomial regression. In the case of independence between the covariates, non-recursive bias and variance expressions, as well as the asymptotically optimal values for the bandwidth parameters, are provided.     

On the Bias of the Generalized Regression Estimator in Survey Sampling

It is well known that the generalized regression (GREG) estimator of the finite population total is asymptotically unbiased. Consequently, bias is negligible when the sample size is large. But the magnitude of the bias is not known, if we are estimating small areas or operating with small samples. Furthermore, beside the sample size, the bias depends on the auxiliary variables, on their relation to the study variable and on the sampling design. In small samples it is important to know sources of the bias and in some cases to use a bias-corrected regression estimator. The aim of the present paper is to derive approximate bias expressions of the GREG estimator under different population models and different sampling designs to study the magnitude of the bias.      

Recursive Estimation of Regression Functions by Local Polynomial Fitting

The recursive estimation of the regression function m(x) = E(Y/X = x) and its derivatives is studied under dependence conditions. The examined method of nonparametric estimation is a recursive version of the estimator based on locally weighted polynomial fitting, that in recent articles has proved to be an attractive technique and has advantages over other popular estimation techniques. For strongly mixing processes, expressions for the bias and variance of these estimators are given and asymptotic normality is established. Finally, a simulation study illustrates the proposed estimation method.     

Pivoting in Extended Rings for Computing Approximate Gr?bner Bases

It is well known that in the computation of Gr?bner bases arbitrarily small perturbations in the coefficients of polynomials may lead to a completely different staircase, even if the solutions of the polynomial system change continuously. This phenomenon is called artificial discontinuity in Kondratyev’s Ph.D. thesis. We show how such phenomenon may be detected and even “repaired” by using a new variable to rename the leading term each time we detect a “problem”. We call such strategy the TSV (Term Substitutions with Variables) strategy. For a zero-dimensional polynomial ideal, any monomial basis (containing 1) of the quotient ring can be found with the TSV strategy. Hence we can use TSV strategy to relax term order while keeping the framework of Gr?bner basis method so that we can use existing efficient algorithms (for instance the F ₅ algorithm) to compute an approximate Gr?bner basis. Our main algorithms, named TSVn and TSVh, can be used to repair artificial e{\epsilon}-discontinuities. Experiments show that these algorithms are effective for some nontrivial problems.     

Multivariate Locally Weighted Polynomial Fitting and Partial Derivative Estimation

Nonparametric regression estimator based on locally weighted least squares fitting has been studied by Fan and Ruppert and Wand. The latter paper also studies, in the univariate case, nonparametric derivative estimators given by a locally weighted polynomial fitting. Compared with traditional kernel estimators, these estimators are often of simpler form and possess some better properties. In this paper, we develop current work on locally weighted regression and generalize locally weighted polynomial fitting to the estimation of partial derivatives in a multivariate regression context. Specifically, for both the regression and partial derivative estimators we prove joint asymptotic normality and derive explicit asymptotic expansions for their conditional bias and conditional convariance matrix (given observations of predictor variables) in each of the two important cases of local linear fit and local quadratic fit.     

Construction of a fundamental series of solutions of a pencil of matrices

Solution of spectral problems for a singular polynomial pencil of matrices D () of degree s1 and sizem×n is considered. Two algorithms for constructing polynomials solutions of pencils D () are considered: the first is a modification of an algorithm proposed earlier by one of the authors for determining polynomial solutions of a linear pencil; the second algorithm is based on other ideas and consists of two steps. At the first step a finite sequence of auxiliary pencils is constructed for each of which a basis of polynomial solutions of degree zero is found. At the second step the basis so constructed are rearranged into polynomial solutions of the original polynomial pencil D(). Both algorithms make it possible to find solutions of the original pencil in order of increasing degrees. For constructing a fundamental series of solutions of the pencil D() two new algorithms are proposed which work independently with either of the algorithms mentioned above for constructing polynomial solutions by rearranging them into linearly independent solutions of the pencil.Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova AN SSSR, Vol. 139, pp. 74–93, 1984.     

Tackling the jump number of interval orders

Although the jump number problem for partially ordered sets in NP-complete in general, there are some special classes of posets for which polynomial time algorithms are known.Here we prove that for the class of interval orders the problem remains NP-complete. Moreover we describe another 3/2-approximation algrithm (two others have been developed already by Felsner and Syslo, respectively) by using a polynomial time subgraph packing algorithm.     

Lower complexity bounds for interpolation algorithms

We introduce and discuss a new computational model for the Hermite-Lagrange interpolation with nonlinear classes of polynomial interpolants. We distinguish between an interpolation problem and an algorithm that solves it. Our model includes also coalescence phenomena and captures a large variety of known Hermite-Lagrange interpolation problems and algorithms. Like in traditional Hermite-Lagrange interpolation, our model is based on the execution of arithmetic operations (including divisions) in the field where the data (nodes and values) are interpreted and arithmetic operations are counted at unit cost. This leads us to a new view of rational functions and maps defined on arbitrary constructible subsets of complex affine spaces. For this purpose we have to develop new tools in algebraic geometry which themselves are mainly based on Zariski’s Main Theorem and the theory of places (or equivalently: valuations). We finish this paper by exhibiting two examples of Lagrange interpolation problems with nonlinear classes of interpolants, which do not admit efficient interpolation algorithms (one of these interpolation problems requires even an exponential quantity of arithmetic operations in terms of the number of the given nodes in order to represent some of the interpolants).In other words, classic Lagrange interpolation algorithms are asymptotically optimal for the solution of these selected interpolation problems and nothing is gained by allowing interpolation algorithms and classes of interpolants to be nonlinear. We show also that classic Lagrange interpolation algorithms are almost optimal for generic nodes and values. This generic data cannot be substantially compressed by using nonlinear techniques.We finish this paper highlighting the close connection of our complexity results in Hermite-Lagrange interpolation with a modern trend in software engineering: architecture tradeoff analysis methods (ATAM).     

工件加工可拒绝的无界批量分批排序问题的几点探讨

本文对两个加工可拒绝的无界批量分批排序问题1|B≥n,rej|∑ωjTj+TP和1|B≥n,rej|∑ωj+TP进行了研究,对这两个问题分别给出了伪多项式时间算法和(FPTAS)近似算法.目前为止它们都是比较好的精确算法和近似算法.