Quasiseparable structures of companion pencils under the QZ-algorithm

Abstract Matrix methods based on the QR eigenvalue algorithm applied to a companion matrix are customary for polynomial root-finding. These methods take advantage of recent results showing that the quasiseparable structure of the input matrix is maintained under the iterative process. The property enables the QR-iteration for a companion matrix to be performed in linear time using a linear memory space. In this note we show the invariance of the quasiseparable structure in the case where the algorithm we deal with is now the QZ-algorithm acting on companion pencils instead of companion matrices.     

Structure-specified IIR filter and control design using real structured genetic algorithm

This paper develops an innovative optimization method, real structured genetic algorithm (RSGA), which combines the advantages of traditional real genetic algorithm (RGA) with structured genetic algorithm (SGA), and applies it for digital filter and control design optimization problems. For infinite impulse response (IIR) filter designs, the proposed approach fulfills all types of filters by minimizing the order of the filter and the absolute error of both passband and stopband. Both system structure and parametric variables are simultaneously optimized via the proposed chromosome scheme. The approach has also been extended to deal with robust control design problems. The approach offers an effective method for designing an optimal controller with robust stability. Simulation and experimental results conveys the excellence of the proposed algorithm over traditional approaches in convergence speed, performance, cost effectiveness, and attains simpler structure.     

A spatially structured genetic algorithm for multi-robot localization

In this paper the multi-robot localization problem is addressed. A new framework based on a spatially structured genetic algorithm is proposed. Collaboration among robots is considered and is limited to the exchange of sensor data. Additionally, the relative distance and orientation among robots are assumed to be available. The proposed framework (MR-SSGA) takes advantage of the cooperation so that the perceptual capability of each robot is extended. Cooperation can be set-up at any time when robots meet, it is fully decoupled and does not require robots to stop. Several simulations have been performed, either considering cooperation activated or not, in order to emphasize the effectiveness of the collaboration strategy.     

A deterministic algorithm for isolating real roots of a real polynomial

We describe a bisection algorithm for root isolation of polynomials with real coefficients. It is assumed that the coefficients can be approximated with arbitrary precision; exact computation in the field of coefficients is not required. We refer to such coefficients as bitstream coefficients. The algorithm is simpler, deterministic and has better asymptotic complexity than the randomized algorithm of Eigenwillig et al. (2005). We also discuss a partial extension to multiple roots.     

A probabilistic framework for problems with real structured uncertainty in systems and control

The objective of this paper is twofold. First, the problem of generation of real random matrix samples with uniform distribution in structured (spectral) norm bounded sets is studied. This includes an analysis of the distribution of the singular values of uniformly distributed real matrices, and an efficient (i.e. polynomial-time) algorithm for their generation. Second, it is shown how the developed techniques may be used to solve in a probabilistic setting several hard problems involving systems subject to real structured uncertainty.     

实参数摄动下结构奇异值计算的新方法

基于结构奇异值(μ)方法的鲁棒稳定性分析与综合设计的关键在于μ的准确计算,而MATLAB鲁棒工具箱中计算实参数摄动的μ的上下界差别太大.本文提出了具体针对实参数对角摄动下的μ的上界和数值准确值计算的新方法.利用实数摄动条件.通过奇异性约束展开的方法将实参数摄动的A计算问题转化为无约束的单目标全局优化问题,然后采用遗传算...     

A real time displacement estimation algorithm for ultrasound elastography

Motion tracking algorithms to derive the local displacement distribution inside soft tissue from ultrasonic radio frequency (RF) signals are critical for ultrasound-based techniques, especially for ultrasound elastography. Normally, there is a trade-off between precision and computational cost. In this study, we present a framework combined with block matching algorithm (BMA) and phase shift method with prior estimation (PSPE). BMA is first applied to the RF signals, the axial and lateral displacements obtained are then used as a prior estimates of the PS method to calculate a more precision axial displacements. The performance of the algorithm is evaluated with synthetic ultrasound RF data, and it is found that both SNRe and CNRe of our method are significantly higher than those of phase-shift as a prior estimation (PSPE) method. Elasticity phantom and clinical data are also used to verify the usefulness of our algorithm, respectively. The results show that our method is robust to image the complex tissue motions.     

A canonical form for regular pencils of matrices

We construct a new canonical form for regular pencils of matrices, which is built with so-called generalized companion blocks. It is shown that every regular pencil is strictly equivalent to such a canonical form.     

Randomized algorithms for probabilistic robustness with real andcomplex structured uncertainty

There has been a growing interest in developing randomized algorithms for probabilistic robustness of uncertain control systems. Unlike classical worst case methods, these algorithms provide probabilistic estimates assessing, for instance, if a certain design specification is met with a given probability. One of the advantages of this approach is that the robustness margins can be often increased by a considerable amount, at the expense of a small risk. In this sense, randomized algorithms may be used by the control engineer together with standard worst case methods to obtain additional useful information. The applicability of these probabilistic methods to robust control is presently limited by the fact that the sample generation is feasible only in very special cases which include systems affected by real parametric uncertainty bounded in rectangles or spheres. Sampling in more general uncertainty sets is generally performed through overbounding, at the expense of an exponential rejection rate. In the paper, randomized algorithms for stability and performance of linear time invariant uncertain systems described by a general M-Δ configuration are studied. In particular, efficient polynomial-time algorithms for uncertainty structures Δ consisting of an arbitrary number of full complex blocks and uncertain parameters are developed     

Polynomial methods for the structured singular value with real parameters

We consider the structured singular value problem with real parametric uncertainty only. Using techniques from algebraic geometry, we propose two algorithms that in principle can yield the precise value of the structured singular value at a fixed frequency. Their ability to do so depends upon their ability to find all common roots to a system of polynomial equations. The first algorithm is applicable to problems with two real parameters each of multiplicity two. The second algorithm is applicable to problems with n distinct real parameters. These algorithms have proved useful in applications to aerospace control law analysis.     

A real time algorithm for people tracking using contextual reasoning

In this paper we present a real-time tracking algorithm that is able to deal with complex occlusions involving a plurality of moving objects simultaneously. The rationale is grounded on a suitable representation and exploitation of the recent history of each single moving object being tracked. The object history is encoded using a state, and the transitions among the states are described through a Finite State Automata (FSA). In presence of complex situations the tracking is properly solved by making the FSA’s of the involved objects interact with each other. This is the way for basing the tracking decisions not only on the information present in the current frame, but also on conditions that have been observed more stably over a longer time span. The object history can be used to reliably discern the occurrence of the most common problems affecting object detection, making this method particularly robust in complex scenarios. An experimental evaluation of the proposed approach has been made on two publicly available datasets, the ISSIA Soccer Dataset and the PETS 2010 database.     

一种基于TLD的顾客进店实时检测算法

结合人脸检测算法和跟踪学习检测算法(Tracking Learning Detection,TLD)完成多个人脸的检测跟踪,用来实现对汽车4S店顾客的实时进店检测。由于采集图像序列帧率低,导致帧间人脸姿态变化大,容易出现目标丢失现象。本文采用Kalman滤波和最邻近数据关联方法,提出一种改进的基于TLD的顾客进店实时检测算法,有效改善了目标短暂丢失现象,增强了算法的鲁棒性。实验证明,该算法具有抵抗光线变化、小范围形变和短暂遮挡的优点,能够解决复杂环境中的实际问题。     

Robust stability with structured real parameter perturbations

This paper considers the problem of robust stabilization of a linear time-invariant system subject to variations of a real parameter vector. For a given controller the radius of the largest stability hypersphere in this parameter space is calculated. This radius is a measure of the stability margin of the closed-loop system. The results developed are applicable to all systems where the closed-loop characteristic polynomial coefficients are linear functions of the parameters of interest. In particular, this always occurs for single-input (multioutput) or single-output (multiinput) systems where the transfer function coefficients are linear or affine functions of the parameters. Many problems with transfer function coefficients which are nonlinear functions of physical parameters can be cast into this mathematical framework by suitable weighting and redefinition of functions of physical parameters as new parameters. The largest stability hyperellipsoid for the case of weighted perturbations and a stability polytope in parameter space are also determined. Based on these calculations a design procedure is proposed to robustify a given stabilizing controller. This algorithm iteratively enlarges the stability hypersphere or hyperellipsoid in parameter space and can be used to design a controller Io stabilize a plant subject to given ranges of parameter excursions. These results are illustrated by an example.     

A particle swarm inspired cuckoo search algorithm for real parameter optimization

The cuckoo search algorithm (CS) is a simple and effective global optimization algorithm. It has been successfully applied to solve a wide range of real-world optimization problems. In this paper, inspired by the particle swarm optimization (PSO), the proposed algorithm uses the best individuals among the entire population to enhance the convergence rate of the standard cuckoo search algorithm. While the PSO directly uses the global best solution of the population to determine new positions for the particles at the each iteration, agents of the CS do not directly use this information but the global best solution in the CS is stored at the each iteration. The global best solutions are used to add into the Information flow between the nest helps increase global and local search abilities of the new approach. Therefore, in the first component, the neighborhood information is added into the new population to enhance the diversity of the algorithm. In the second component, two new search strategies are used to balance the exploitation and exploration of the algorithm through a random probability rule. In other aspect, our algorithm has a very simple structure and thus is easy to implement. To verify the performance of PSCS, 30 benchmark functions chosen from literature are employed. The results show that the proposed PSCS algorithm clearly outperforms the basic CS and PSO algorithm. Compared with some evolution algorithms (CLPSO, CMA-ES, GL-25, DE, OXDE, ABC, GOABC, FA, FPA, CoDE, BA, BSA, BDS and SDS) from literature, experimental results indicate that the proposed algorithm performs better than, or at least comparable to state-of-the-art approaches from literature when considering the quality of the solution obtained. In the last part, experiments have been conducted on two real-world optimization problems including the spread spectrum radar poly-phase code design problem and the chaotic system. Simulation results demonstrate that the proposed algorithm is very effective.     

信息物理系统中基于保护阈值的实时调度算法研究

信息物理融合系统CPS是一种融合计算、通信与控制的新型复杂实时分布式系统,系统中计算过程和物理过程在开放环境下持续交互、深度融合。为了对物理世界的信息作出实时反馈,系统一般会采用抢占式调度的方法,保障关键任务能够在截止期前完成。但是,分布式环境中抢占式调度方式容易导致频繁的任务切换,影响系统的实时性。提出了基于保护阈值的调度算法,通过建立保护阈值模型,最大化低优先级任务的执行时间,减少任务切换次数。通过实验验证,算法有效地减少了任务切换次数,提高了CPS系统的实时性能。     

The real structured singular value is hardly approximable

This paper investigates the problem of approximating the real structured singular value (real μ). A negative result is provided which shows that the problem of checking if μ=0 is NP-hard. This result is much more negative than the known NP-hard result for the problem of checking if μ<1. One implication of our result is that μ is hardly approximable in the following sense: there does not exist an algorithm, polynomial in the size n of the μ problem, which can produce an upper bound μ¯ for μ with the guarantee that μ⩽μ¯⩽K(n)μ for any K(n)>0 (even exponential functions of n), unless NP=P. A similar statement holds for the lower bound of μ. Our result strengthens a recent result by Toker, which demonstrates that obtaining a sublinear approximation for μ is NP-hard     

The parallel QZ decomposition method for solving linear equations

The QR orthogonal decomposition method is well established for solving linear systems and both sequential and parallel implementations have been proposed. In this paper, the QZ orthogonal decomposition method is proposed in which 2 elements are eliminated simultaneously. Consequently, the theoretical analyses presented show that the QZ method is faster than the QR method which is confirmed by the numerical results.