The sample complexity of worst-case identification of FIR linear systems

We consider the problem of identification of linear systems in the presence of measurement noise which is unknown but bounded in magnitude by some δ > 0. We focus on the case of linear systems with a finite impulse response. It is known that the optimal identification error is related (within a factor of 2) to the diameter of a so-called uncertainty set and that the latter diameter is upper-bounded by 2δ, if a sufficiently long identification experiment is performed. We establish that, for any K 1, the minimal length of an identification experiment that is guaranteed to lead to a diameter bounded by 2Kδ behaves like 2^Nf(1/K), when N is large, where N is the length of the impulse response and is a positive function known in closed form. While the framework is entirely deterministic, our results are proved using probabilistic tools.     

Optimal input design for worst-case system identification in l1/l2/l∞

In this paper, we examine optimal sequences that generate worst-case parameters estimation errors in the l₁, l₂ and l_∞ norm context for algorithms identifying linear, time-invariant discrete-time, finite impulse response systems excited by bounded sequences and with l_∞ norm measurement error.     

Closed-loop identification of unstable systems using noncausal FIR models

Noncausal finite impulse response (FIR) models are used for closed-loop identification of unstable multi-input, multi-output plants. These models are shown to approximate the Laurent series inside the annulus between the asymptotically stable pole of the largest modulus and the unstable pole of the smallest modulus. By delaying the measured output relative to the measured input, the identified FIR model is a noncausal approximation of the unstable plant. We present examples to compare the accuracy of the identified model obtained using least squares, instrumental variables methods, and prediction error methods for both infinite impulse response (IIR) and noncausal FIR models under arbitrary noise that is fed back into the loop. Finally, we reconstruct an IIR model of the system from its stable and unstable parts using the eigensystem realisation algorithm.     

Parameter consistency and quadratically constrained errors-in-variables least-squares identification

In this article, we investigate the consistency of parameter estimates obtained from least-squares identification with a quadratic parameter constraint. For generality, we consider infinite impulse-response systems with coloured input and output noise. In the case of finite data, we show that there always exists a possibly indefinite quadratic constraint depending on the noise realisation that results in a constrained optimisation problem that yields the true parameters of the system when a persistency condition is satisfied. When the noise covariance matrix is known to within a scalar multiple, we prove that solutions of the quadratically constrained least-squares (QCLs) estimator with a semidefinite constraint matrix are both unbiased and consistent in the sense that the averaged problem and limiting problem produce, respectively, unbiased and true (with probability 1) estimators. In addition, we provide numerical results that illustrate these properties of the QCLS estimator.     

线性相位FIR数字滤波器设计的随机抽样递推最小二乘算法

本文考虑了基于加权平方误差准则线性相位FIR数字滤波器的设计问题，提出一种随机抽样递推最小二乘（RS－RLS）设计方法．将设计问题看成一个线性系统的辨识问题，辨识参数所需的数据由一随机抽样法产生，辨识算法采用递推最小二乘法上RS-RLS设计法简单易用，设计范例说明这一方法具有很高的设计精度．     

The worst-case execution time tool challenge 2006

The first international worst-case execution time (WCET) Tool Challenge in 2006 used benchmark programs to evaluate academic and commercial WCET tools. It aimed to study the state-of-the-art in WCET analysis. The WCET Tool Challenge comprised two parallel evaluation approaches: an internal evaluation by the respective tool developers and an external test by a neutral person of an independent institute. The latter was conducted by the author of this paper. Focusing on the external test, we describe the rules, benchmarks, participants and discuss the obtained results. This work was supported by the ARTIST2 European Network of Excellence.     

一类有色噪声干扰下的随机时变系统学习辨识

讨论由一类时变ARMAX模型描述的动态系统学习辨识问题,提出用于估计有限区间上重复运行时变系统时变参数的学习算法.文中给出最小二乘学习算法的具体形式及实现步骤,并分析所提出学习算法的收敛性.分析结果表明,当重复持续激励条件成立且满足严格正实条件时,提出的学习算法具有重复一致性,即参数估值完全收敛于真值.文中还将结果推广到一类周期时变系统.通过数值仿真,进一步对所提学习算法的有效性进行了验证.     

Open-loop worst-case identification of nonSchur plants

This paper presents an LMI based algorithm for deterministic worst-case identification of nonSchur plants in an open-loop setting. Contrary to other approaches dealing with this problem, the proposed technique does not require prior knowledge of a stabilizing controller. The main result of the paper shows that, as the information is completed, the identified model converges, in the ?₂-induced topology, to the actual plant. Additional results include upper bounds on the worst-case identification error on the finite horizon. The usefulness of the proposed approach is illustrated with a practical example arising in the context of robust visual tracking.     

分数阶系统频域辨识算法

分数阶微积分提供了一个很好的工具来描述一些复杂的实际系统,比整数阶模型更简洁准确.针对分数阶系统建模问题,阐述了一种同元次分数阶系统频域辨识的极大似然算法.为此首先简要地介绍了同元次分数阶系统的传递函数表达形式,然后在此基础上推导了分数阶系统频域极大似然算法,利用拉格朗日法证明了似然函数和代价函数的等价性,从而将辨识问题归结为一等价的优化问题,并进一步对采用Gauss-Newton优化计算方法进行了讨论.最后通过仿真实例验证了其有效性.     

Fixed-order FIR approximation of linear systems from quantized input and output data

The problem of identifying a fixed-order FIR approximation of linear systems with unknown structure, assuming that both input and output measurements are subjected to quantization, is dealt with in this paper. A fixed-order FIR model providing the best approximation of the input–output relationship is sought by minimizing the worst-case distance between the output of the true system and the modeled output, for all possible values of the input and output data consistent with their quantized measurements. The considered problem is firstly formulated in terms of robust optimization. Then, two different algorithms to compute the optimum of the formulated problem by means of linear programming techniques are presented. The effectiveness of the proposed approach is illustrated by means of a simulation example.     

Auxiliary model-based least-squares identification methods for Hammerstein output-error systems

The difficulty in identification of a Hammerstein (a linear dynamical block following a memoryless nonlinear block) nonlinear output-error model is that the information vector in the identification model contains unknown variables—the noise-free (true) outputs of the system. In this paper, an auxiliary model-based least-squares identification algorithm is developed. The basic idea is to replace the unknown variables by the output of an auxiliary model. Convergence analysis of the algorithm indicates that the parameter estimation error consistently converges to zero under a generalized persistent excitation condition. The simulation results show the effectiveness of the proposed algorithms.     

遗传算法在FIR窗函数设计中的应用

本文将遗传算法引入FIE的窗函数设计中,提出了窗函数可以由一系列离散的介于0－1的仅值来取代的思路。根据预期频率特性的指标要求,我们建立了窗权值的优化模型,并通过遗传算法来求解,所得的优化解将使对应FIE滤波器的频率特性较好地满足预期频率特性的要求。本设计方法简单,工作量小,具有高的灵活性和鲁棒性,数值实验表明了本方法的有效性。     

Approximation of the Feasible Parameter Set in worst-case identification of Hammerstein models

The estimation of the Feasible Parameter Set (FPS) for Hammerstein models in a worst-case setting is considered. A bounding procedure is determined both for polytopic and ellipsoidic uncertainties. It consists in the projection of the FPS of the extended parameter vector onto suitable subspaces and in the solution of convex optimization problems which provide Uncertainties Intervals of the model parameters. The bounds obtained are tighter than in the previous approaches.     

最大误差约束下最小二乘准则FIR滤波器设计

考虑了一类加权最小二乘复系数FIR滤波器的设计问题,要求滤波器通带及止带内频点的频率响应与期望响应误差小于给定的最大误差门限.结合半正定优化理论,经过数学推导,将该设计问题转换为半正定优化问题,然后借助内点方法给出最优滤波器系数.另外,该方法能够检测出给定约束条件的优化问题是否存在可行解,从而可以使设计者能够以自适应的方式调整约束条件.仿真结果表明设计算法是十分有效的,并具有很好的稳健性.     

On identification of FIR systems having quantized output data

In this paper, we present a novel algorithm for estimating the parameters of a linear system when the observed output signal is quantized. This question has relevance to many areas including sensor networks and telecommunications. The algorithms described here have closed form solutions for the SISO case. However, for the MIMO case, a set of pre-computed scenarios is used to reduce the computational complexity of EM type algorithms that are typically deployed for this kind of problem. Comparisons are made with other algorithms that have been previously described in the literature as well as with the implementation of algorithms based on the Quasi-Newton method.     

Fast approximate identification of nonlinear systems

In this paper, a method is presented to extend the classical identification methods for linear systems towards nonlinear modelling of linear systems that suffer from nonlinear distortions. A well chosen, general nonlinear model structure is proposed that is identified in a two-step procedure. First, a best linear approximation is identified using the classical linear identification methods. In the second step, the nonlinear extensions are identified with a linear least-squares method. The proposed model not only includes Wiener and Hammerstein systems, it is also suitable to model nonlinear feedback systems. The stability of the nonlinear model can be easily verified. The method is illustrated on experimental data.     

Convergence analysis of recursive identification algorithms with forgetting factor

A convergence analysis of a modified version of the least-squares recursive identification algorithm with forgetting factor is given. It is shown that the parametric distance converges to a zero mean random variable. It is also shown that, under persistent excitation condition on both system input and output, the condition number of the adaptation gain matrix is bounded. The variance of the parametric distance is bounded by the product of the noise variance times the upper bound of the condition number of the gain matrix. This is done by normalizing the measurement vector entering in the identification algorithm and by using a forgetting factor verifying λ_t ? 1 ? ε; ε >0.     

Modulating function-based system identification for a fractional-order system with a time delay involving measurement noise using least-squares method

This study proposes an identification algorithm for a time-delay fractional-order system with the measurement noise via the modulating function approach. The polynomial function is adopted as the modulating function, and the approach to determine the coefficients of the modulating function is provided. By the property of modulating function, the identified fractional-order equation is converted into an algebraic equation. By the recursive least squares estimation algorithm, the estimation method of coefficients is offered. Supposing that the measurement noise in the output signal is the Gauss white noise, a revised identification algorithm is proposed to compensate the effect of measurement noise. Finally, two examples are given to verify the effectiveness of the proposed method.