A simulation-based estimator for hidden Markov random fields

An estimator for estimating the parameters of a Markov random field X from inaccurate observations is introduced. The author considers first a Markov (Gibbs) random field X={X_i,j} on a lattice L={(i ,j): i=1,2,. . .,n; j=1,2,. . .,m}. The marginal distributions of (X_i,j, X_i+u,j+v) (u,v=-1,0,1) are first estimated from an image. Then, random fields X* are simulated with the probability of X*_i+u,j+v)=b nearly equal to the estimate of P{X_i,j=X _i+u,=b}. A simulation method similar to the Gibbs sampler is used. The parameters of the Markov random field model are estimated from the X*'s with the pseudolikelihood method     

Decomposition of 2-D linear systems into 1-D systems in thefrequency domain

A method is presented for the decomposition of the frequency domain of 2-D linear systems into two equivalent 1-D systems having dynamics in different directions and connected by a feedback system. It is shown that under some assumptions the decomposition problem can be reduced to finding a realizable solution to the matrix polynomial equation X(z₁)P(z₂ )+Q(z₁)Y(z₂ )=D(z₁, z₂). A procedure for finding a realizable solution X(z₁ ), Y(z₂) to the equation is given     

Compound-Poisson software reliability model

The probability density estimation of the number of software failures in the event of clustering or clumping of the software failures is considered. A discrete compound Poisson (CP) prediction model is proposed for the random variable X_rem, which is the remaining number of software failures. The compounding distributions, which are assumed to govern the failure sizes at Poisson arrivals, are respectively taken to be geometric when failures are forgetful and logarithmic-series when failures are contagious. The expected value (μ) of X_rem is calculated as a function of the time-dependent Poisson and compounding distribution based on the failures experienced. Also, the variance/mean parameter for the remaining number of failures, q_rem, is best estimated by q_past from the failures already experienced. Then, one obtains the PDF of the remaining number of failures estimated by CP(μ,q). CP is found to be superior to Poisson where clumping of failures exists. Its predictive validity is comparable to the Musa-Okumoto log-Poisson model in certain cases     

Matrix inequalities applicable to estimating solution sizes ofRiccati and Lyapunov equations

Simultaneous summation upper bounds for the eigenvalues of the matrix product XY are presented, where X, Y ϵ R^nxn, with Y symmetric and X arbitrary. These bounds are a generalization of tr (XY) bounds; the requirements on Y are relaxed, and the bound for tr (XY) is stronger than those shown in the literature     

Explicit expressions for cascade factorization of generalnonminimum phase systems

Explicit expressions for two different cascade factorizations of any detectable left invertible nonminimum phase systems are given. The first one is a well known minimum phase/all-pass factorization by which all nonminimum phase zeros of a transfer function G(s) are collected into an all-pass factor V(s), and G (s) is written G_m(s)V$ where G_ms is considered as a minimum phase image of G(s). The second one is a new cascade factorization by which G(s) is rewritten as G_M( s)U(s) where U(s) collects all `awkward' zeros including all nonminimum phase zeros of G( s). Both G_m(s) and G_M(s) retain the given infinite zero structure of G(s). Further properties of G _m(s), G_M(s), and U (s) are discussed. These factorizations are useful in several applications including loop transfer recovery     

Parallel evaluation of attribute grammars

Examines the generation of parallel evaluators for attribute grammars, targeted to shared-memory MIMD computers. Evaluation-time overhead due to process scheduling and synchronization is reduced by detecting coarse-grain parallelism (as opposed to the naive one-process-per-node approach). As a means to more clearly expose inherent parallelism, it is shown how to automatically transform productions of the form X→Y X into list-productions of the form X→Y⁺. This transformation allows for many simplifications to be applied to the semantic rules, which can expose a significant degree of inherent parallelism, and thus further increase the evaluator's performance. Effectively, this constitutes an extension of the concept of attribute grammars to the level of abstract syntax     

Mixed H2/H∞ control:a convex optimization approach

The problem of finding an internally stabilizing controller that minimizes a mixed H₂/H_∞ performance measure subject to an inequality constraint on the H_∞ norm of another closed-loop transfer function is considered. This problem can be interpreted and motivated as a problem of optimal nominal performance subject to a robust stability constraint. Both the state-feedback and output-feedback problems are considered. It is shown that in the state-feedback case one can come arbitrarily close to the optimal (even over full information controllers) mixed H₂/H_∞ performance measure using constant gain state feedback. Moreover, the state-feedback problem can be converted into a convex optimization problem over a bounded subset of (n×n and n ×q, where n and q are, respectively, the state and input dimensions) real matrices. Using the central H_∞ estimator, it is shown that the output feedback problem can be reduced to a state-feedback problem. In this case, the dimension of the resulting controller does not exceed the dimension of the generalized plant     

An improved covariance assignment theory for discrete systems

For discrete systems, the set of all state covariances X which can be assigned to the closed-loop system via a dynamic controller is characterized explicitly. For any assignable state covariance X , the set of all controllers that assign this X to the closed-loop system is parameterized with an arbitrary orthonormal matrix U of proper dimension     

Linear and nonlinear algorithms for identification in H∞ with error bounds

A linear algorithm and a nonlinear algorithm for the problem of system identification in H_∞ posed by Helmicki et al. (1990) for discrete-time systems are presented. The authors derive some error bounds for the linear algorithm which indicate that it is not robustly convergent. However, the worst-case identification error is shown to grow as log(n), where n is the model order. A robustly convergent nonlinear algorithm is derived, and bounds on the worst-case identification error (in the H_∞ norm) are obtained     

On the number of digital straight line segments

A closed-form expression has been reported in the literature for L_N, the number of digital line segments of length N that correspond to lines of the form y=ax+β, O⩽α, β<1. The authors prove an asymptotic estimate for L_N that might prove useful for many applications, namely, L_N=N ³/π²+O(N² log N). An application to an image registration problem is given     

A new realization theory

A realization theory that is based on the Kalman system theory and motivated by the Fuhrmann realization theory is presented. In the Fuhrmann realization theory, the realization state-space is defined by a natural polynomial module K_Q, which is related to a nonsingular polynomial matrix Q. The module K_Q is formed of all f where Q^-1f is strictly proper. In the realization theory proposed, the realization state-space is defined by a different module M_Q, which is formed of properly truncated, strictly proper formal power series of Q^-1f. The realization theory can be used to prove the dual-realization scheme induced by the Fuhrmann realization theory     

Adaptive structuring of binary search trees using conditionalrotations

Consider a set A={A₁,A₂ ,. . ., A_n} of records, where each record is identified by a unique key. The records are accessed based on a set of access probabilities S=[s₁,s₂ ,. . ., s_N] and are to be arranged lexicographically using a binary search tree (BST). If S is known a priori, it is well known that an optimal BST may be constructed using A and S. The case when S is not known a priori is considered. A new restructuring heuristic is introduced that requires three extra integer memory locations per record. In this scheme, the restructuring is performed only if it decreases the weighted path length (WPL) of the overall resultant tree. An optimized version of the latter method, which requires only one extra integer field per record has, is presented. Initial simulation results comparing this algorithm with various other static and dynamic schemes indicates that this scheme asymptotically produces trees which are an order of magnitude closer to the optimal one than those produced by many of the other BST schemes reported in the literature     

Linear systems with state and control constraints: the theory andapplication of maximal output admissible sets

The initial state of an unforced linear system is output admissible with respect to a constraint set Y if the resulting output function satisfies the pointwise-in-time condition y(t)∈Y, t⩾0. The set of all possible such initial conditions is the maximal output admissible set O_∞. The properties of O_∞ and its characterization are investigated. In the discrete-time case, it is generally possible to represent O_∞ or a close approximation of it, by a finite number of functional inequalities. Practical algorithms for generating the functions are described. In the continuous-time case simple representations of the maximal output admissible set are not available, however, it is shown that the discrete-time results may be used to obtain approximate representations     

The stability of a family of polynomials can be deduced from afinite number 0(k3) of frequency checks

Let φ(s,a)=φ₀(s,a)+ a₁φ₁(s)+a₂ φ₂(s)+ . . .+a_kφ _k(s)=φ₀(s)-q(s, a) be a family of real polynomials in s, with coefficients that depend linearly on parameters a_i which are confined in a k-dimensional hypercube Ω_a . Let φ₀(s) be stable of degree n and the φ_i(s) polynomials (i⩾1) of degree less than n. A Nyquist argument shows that the family φ(s) is stable if and only if the complex number φ₀(jω) lies outside the set of complex points -q(jω,Ω_a) for every real ω. In a previous paper (Automat. Contr. Conf., Atlanta, GA, 1988) the authors have shown that -q(jω,Ω_a ), the so-called `-q locus', is a 2k convex parpolygon. The regularity of this figure simplifies the stability test. In the present paper they again exploit this shape and show that to test for stability only a finite number of frequency checks need to be done; this number is polynomial in k, 0(k³), and these critical frequencies correspond to the real nonnegative roots of some polynomials     

Two new estimation algorithms for linear models with unknown butbounded measurement noise

Attention is given to linear systems described by y=A _&thetas;+e where the measurement error vector e is unknown but bounded. Two algorithms for sequential parameter identification are introduced. Their convergence properties are illustrated and compared with those of existing algorithms. A simulation study is carried out using simulated data to investigate the possible practical use of the algorithms. Their performances are compared with those of other offline algorithms as well as with those of the widely used least-squares estimates     

Strict aperiodic property of polynomials with perturbedcoefficients

Let a family of polynomials be P(s)=t ₀sⁿ+t₁s ⁿ±¹ + . . . + t_n where 0<a_j⩽t_j⩽b _j. V.L. Kharitonov (1978) derived a necessary and sufficient condition for the above equation to have only zeros in the open left-half plane. The present authors derive some similar results for the equation to be strictly aperiodic (distinct real roots)     

Damping ratio of polynomials with perturbed coefficients

Let a family of polynomials be P(s)=t ₀Sⁿ+t₁s ^n-1 . . .+t_n where O<α _j⩽t_j⩽β. Recently, C.B. Soh and C.S. Berger have shown that a necessary and sufficient condition for this equation to have a damping ratio of φ is that the 2ⁿ⁺¹ polynomials in it which have t_k=α_k or t_k=β_k have a damping ratio of φ. The authors derive a more powerful result requiring only eight polynomials to be Hurwitz for the equation to have a damping ratio of φ using Kharitonov's theorem for complex polynomials     

True 3D animation for displaying VLSI modeling data

The authors report on a flexible system that provides visual feedback to VLSI designers with a novel display method. The basic problem is to display simultaneously two or more functions f ₁, f₂, . . ., each of which depends on the two spatial variables x and y. The method is based on results from visual perception experiments, which indicated that the human visual system can view simultaneously two or more images that are separated in depth, even if they are combined (superimposed) over a common spatial domain. Two display modes have been implemented: a gray-level mode and a contour mode in which only the edges separating adjacent regions are displayed in an effort to make things easier for the user. This depth-separation technique allows the viewer to register spatially the x,y distribution of multiple variables in an animation sequence. The technique can be applied to many other situations in which a single-plane episode involves several variables     

Damping margins of polynomials with perturbed coefficients

Considers the polynomial P(s)=t₀ Sⁿ+t₁ S^n-1 +···+t_n where 0<a _j⩽t_j⩽b_j. Recently, V.L. Kharitonov (1978) derived a necessary and sufficient condition for this polynomial to have only zeros in the open left-half plane. Two lemmas are derived to investigate the existence of theorems similar to the theorem of Kharitonov. Using these lemmas, the theorem of Kharitonov is generalized for P(s) to have only zeros within a sector in the complex plane. The aperiodic case is also considered     

Distributed detection with consulting sensors and communicationcost

The problem of distributed detection with consulting sensors in the presence of communication cost associated with any exchange of information (consultation) between sensors is considered. The system considered has two sensors, S1 and S2; S1 is the primary sensor responsible for the final decision u₀ , and S2 is a consulting sensor capable of relaying its decision u₂ to S1 when requested by S 1. The final decision u₀ is either based on the raw data available to S1 only, or, under certain request conditions, also takes into account the decision u₂ of sensor S2. Random and nonrandom request schemes are analyzed and numerical results are presented and compared for Gaussian and slow-fading Rayleigh channels. For each decision-making scheme, an associated optimization problem is formulated whose solution is shown to satisfy certain set design criteria that the authors consider essential for sensor fusion