LIMITING BEHAVIOR OF RECURSIVE M-ESTIMATORS IN MULTIVARIATE LINEAR REGRESSION MODELS AND THEIR ASYMPTOTIC EFFICIENCIES

Recursive algorithms are very useful for computing M-estimators of regression coefficients and scatter parameters. In this article, it is shown that for a nondecreasing ul （t）, under some mild conditions the recursive M-estimators of regression coefficients and scatter parameters are strongly consistent and the recursive M-estimator of the regression coefficients is also asymptotically normal distributed. Furthermore, optimal recursive M-estimators, asymptotic efficiencies of recursive M-estimators and asymptotic relative efficiencies between recursive M-estimators of regression coefficients are studied.     

Graeffe's, Chebyshev-like, and Cardinal's Processes for Splitting a Polynomial into Factors

Numerical splitting of a real or complex univariate polynomial into factors is the basic step of the divide-and-conquer algorithms for approximating complex polynomial zeros. Such algorithms are optimal (up to polylogarithmic factors) and are quite promising for practical computations. In this paper, we develop some new techniques, which enable us to improve numerical analysis, performance, and computational cost bounds of the known splitting algorithms. In particular, we study a Chebyshev-like modification of Graeffe's lifting iteration (which is a basic block of the splitting algorithms, as well as of several other known algorithms for approximating polynomial zeros), analyze its numerical performance, compare it with Graeffe's, prove some results on numerical stability of both lifting processes (that is, Graeffe's and Chebyshev-like), study their incorporation into polynomial root-finding algorithms, and propose some improvements of Cardinal's recent effective technique for numerical splitting of a polynomial into factors. Our improvement relies, in particular, on a modification of the matrix sign iteration, based on the analysis of some conformal mappings of the complex plane and of techniques of recursive lifting/recursive descending. The latter analysis reveals some otherwise hidden correlations among Graeffe's, Chebyshev-like, and Cardinal's iterative processes, and we exploit these correlations in order to arrive at our improvement of Cardinal's algorithm. Our work may also be of some independent interest for the study of applications of conformal maps of the complex plane to polynomial root-finding and of numerical properties of the fundamental techniques for polynomial root-finding such as Graeffe's and Chebyshev-like iterations.     

Recursive computational formulas of the least squares criterion functions for scalar system identification

The paper discusses recursive computation problems of the criterion functions of several least squares type parameter estimation methods for linear regression models, including the well-known recursive least squares (RLS) algorithm, the weighted RLS algorithm, the forgetting factor RLS algorithm and the finite-data-window RLS algorithm without or with a forgetting factor. The recursive computation formulas of the criterion functions are derived by using the recursive parameter estimation equations. The proposed recursive computation formulas can be extended to the estimation algorithms of the pseudo-linear regression models for equation error systems and output error systems. Finally, the simulation example is provided.     

Singular integral transforms and fast numerical algorithms

Fast algorithms for the accurate evaluation of some singular integral operators that arise in the context of solving certain partial differential equations within the unit circle in the complex plane are presented. These algorithms are generalizations and extensions of a fast algorithm of Daripa [11]. They are based on some recursive relations in Fourier space and the FFT (Fast Fourier Transform), and have theoretical computational complexity of the order O(N) per point, where N² is the total number of grid points. An application of these algorithms to quasiconformal mappings of doubly connected domains onto annuli is presented in a follow-up paper.     

RECURSIVE SYSTEM IDENTIFICATION

Most of existing methods in system identification with possible exception of those for linear systems are off-line in nature, and hence are nonrecursive. This paper demonstrates the recent progress in recursive system identification. The recursive identification algorithms are presented not only for linear systems （multivariate ARMAX systems） but also for nonlinear systems such as the Hammerstein and Wiener systems, and the nonlinear ARX systems. The estimates generated by the algorithms are online updated and converge a.s. to the true values as time tends to infinity.     

一类广义Ball曲线的改进

Said将Ball基由三阶延伸到奇数阶。本文在任意阶上讨论广义Ball曲线性质及其求值的新一种递归算法。     

Approximate queueing models for capacitated multi-stage inventory systems under base-stock control

A queueing analysis is presented for base-stock controlled multi-stage production-inventory systems with capacity constraints. The exact queueing model is approximated by replacing some state-dependent conditional probabilities (that are used to express the transition rates) by constants. Two recursive algorithms (each with several variants) are developed for analysis of the steady-state performance. It is analytically shown that one of these algorithms is equivalent to the existing approximations given in the literature. The system studied here is more general than the systems studied in the literature. The numerical investigation for three-stage systems shows that the proposed approximations work well to estimate the relevant performance measures.     

两类新的广义Ball曲线曲面的求值算法及其应用

本文研究两类新的广义Ball曲线曲面的求值算法及其应用.其一是把Bezier曲线曲面的求值转换到这两类曲线曲面的求值,大大加快了计算速度.其二是给出Bezier曲线与这两类广义Ball曲线的统一表示,并利用这种表示给出它们之间相互转换的递归算法.     

Recognition of logically related regions based heap abstraction

This paper presents a novel set of algorithms for heap abstraction, identifying logically related regions of the heap. The targeted regions include objects that are part of the same component structure (recursive data structure). The result of the technique outlined in this paper has the form of a compact normal form (an abstract model) that boosts the efficiency of the static analysis via speeding its convergence. The result of heap abstraction, together with some properties of data structures, can be used to enable program optimizations like static deallocation, pool allocation, region-based garbage collection, and object co-location.More precisely, this paper proposes algorithms for abstracting heap components with the layout of a singly linked list, a binary tree, a cycle, and a directed acyclic graph. The termination and correctness of these algorithms are studied in the paper. Towards presenting the algorithms the paper also presents concrete and abstract models for heap representations.     

New inversion formulas for matrices classified in terms of their distance from Toeplitz matrices

The problem of solving linear equations, or equivalently of inverting matrices, arises in many fields. Efficient recursive algorithms for finding the inverses of Toeplitz or displacement-type matrices have been known for some time. By introducting a way of characterizing matrices in terms of their “distance” from being Toeplitz, a natural extension of these algorithms is obtained. Several new inversion formulas for the representation of the inverse of non-Toeplitz matrices are also presented.     

Look-ahead Levinson and Schur algorithms for non-Hermitian Toeplitz systems

Summary. We present generalizations of the nonsymmetric Levinson and Schur algorithms for non-Hermitian Toeplitz matrices with some singular or ill-conditioned leading principal submatrices. The underlying recurrences allow us to go from any pair of successive well-conditioned leading principal submatrices to any such pair of larger order. If the look-ahead step size between these pairs is bounded, our generalized Levinson and Schur recurrences require $ operations, and the Schur recurrences can be combined with recursive doubling so that an $ algorithm results. The overhead (in operations and storage) of look-ahead steps is very small. There are various options for applying these algorithms to solving linear systems with Toeplitz matrix. Received July 26, 1993     

On Some Techniques for Streaming Data: A Case Study of Internet Packet Headers

We consider the implications of streaming data for data analysis and data mining. Streaming data are becoming widely available from a variety of sources. In our case we consider the implications arising from Internet traffic data. By implication, streaming data are unlikely to be time homogeneous so that standard statistical and data mining procedures do not necessarily apply. Because it is essentially impossible to store streaming data, we consider recursive algorithms, algorithms which are adaptive and discount the past and also algorithms that create finite pseudo-samples. We also suggest some evolutionary graphics procedures that are suitable for streaming data. We begin our discussion with a discussion of Internet traffic in order to give the reader some sense of the time and data scale and visual resolution needed for such problems.     

Data-driven recursive least squares methods for non-affined nonlinear discrete-time systems

Aiming at identifying nonlinear systems, one of the most challenging problems in system identification, a class of data-driven recursive least squares algorithms are presented in this work. First, a full form dynamic linearization based linear data model for nonlinear systems is derived. Consequently, a full form dynamic linearization-based data-driven recursive least squares identification method for estimating the unknown parameter of the obtained linear data model is proposed along with convergence analysis and prediction of the outputs subject to stochastic noises. Furthermore, a partial form dynamic linearization-based data-driven recursive least squares identification algorithm is also developed as a special case of the full form dynamic linearization based algorithm. The proposed two identification algorithms for the nonlinear nonaffine discrete-time systems are flexible in applications without relying on any explicit mechanism model information of the systems. Additionally, the number of the parameters in the obtained linear data model can be tuned flexibly to reduce computation complexity. The validity of the two identification algorithms is verified by rigorous theoretical analysis and simulation studies.     

Recursive prediction error identification of fractional order models

This paper deals with time domain identification of fractional order systems. A new identification technique is developed providing recursive parameters estimation of fractional order models. The identification model is defined by a generalized ARX structure obtained by discretization of a continuous fractional order differential equation. The parameters are then estimated using the recursive least squares and the recursive instrumental variable algorithms extended to fractional order cases. Finally, the quality of the proposed technique is illustrated and compared through the identification of simulated fractional order systems.     

UNIFYING REPRESENTATION OF BEZIERCURVE AND GENERALIZED BALL CURVES

Abstract. This paper presents two new families of the generalized Ball curves which include theI~zier curve, the generalized Ball curves defined by Wang and Said independently and some in-termediate curves. The relative degree elevation and reduction schemes, recursive algorithmsand the Bernstein-Bezier representation are also given.     

Solvable classes of discrete dynamic programming

As finite state models to represent a discrete optimization problem given in the form of an r-ddp (recursive discrete decision process), three subclasses of r-msdp (recursive monotone sequential decision process) are introduced in this paper. They all have a feature that the functional equations of dynamic programming hold and there exists an algorithm (in the sense of the theory of computation) to obtain the set of optimal policies. (In this sense, we may call them solvable classes of discrete dynamic programming.) Besides the algorithms for obtaining optimal policies, two types of representations are extensively studied for each class of r-msdp's. Other related decision problems are also discussed. It turns out that some of them are solvable while the rest of them are unsolvable.     

Fourier expansion based recursive algorithms for periodic Riccati and Lyapunov matrix differential equations

Combining Fourier series expansion with recursive matrix formulas, new reliable algorithms to compute the periodic, non-negative, definite stabilizing solutions of the periodic Riccati and Lyapunov matrix differential equations are proposed in this paper. First, periodic coefficients are expanded in terms of Fourier series to solve the time-varying periodic Riccati differential equation, and the state transition matrix of the associated Hamiltonian system is evaluated precisely with sine and cosine series. By introducing the Riccati transformation method, recursive matrix formulas are derived to solve the periodic Riccati differential equation, which is composed of four blocks of the state transition matrix. Second, two numerical sub-methods for solving Lyapunov differential equations with time-varying periodic coefficients are proposed, both based on Fourier series expansion and the recursive matrix formulas. The former algorithm is a dimension expanding method, and the latter one uses the solutions of the homogeneous periodic Riccati differential equations. Finally, the efficiency and reliability of the proposed algorithms are demonstrated by four numerical examples.     

一类双指标递归关系的求解方法

递归关系不仅在数学中有广泛应用,而且在计算机算法设计与分析中也有广泛应用.在讨论两DNA序列间可能出现的比对数目时,得到比对数目满足的递归关系.对这种递归关系进行了推广,得到一类含四个参数的双指标递归关系模型.采用母函数方法,给出了这类递归关系模型的显式解表达式.     

A recursive exact algorithm for weighted two-dimensional cutting

Gilmore and Gomory's algorithm is one of the better actually known exact algorithms for solving unconstrained guillotine two-dimensional cutting problems. Herz's algorithm is more effective, but only for the unweighted case. We propose a new exact algorithm adequate for both weighted and unweighted cases, which is more powerful than both algorithms. The algorithm uses dynamic programming procedures and one-dimensional knapsack problem to obtain efficient lower and upper bounds and important optimality criteria which permit a significant branching cut in a recursive tree-search procedure. Recursivity, computational power, adequateness to parallel implementations, and generalization for solving constrained two-dimensional cutting problems, are some important features of the new algorithm.     

Marking algorithms

Algorithms for traversing and marking the nodes of a directed graph have applications in many fields, for instance search methods in artificial intelligence and garbage collection schemes. In this paper, a general nonrecursive algorithm for the purpose is formulated and proved, and some if its properties are investigated. A second general nonrecursive algorithm is also discussed. Then two implementations of the general algorithms with valuable properties are described. Finally a recursive version is given.