Identification and estimation using quantized output signal measurements
The control of systems using quantized commands and measurements over the internet is becoming more and more important today. A consequence of this fact is a need for system identification algorithms that are able to operate on coarsely quantized measurements of inputs and outputs.
The difficulty of this system identification problem is dependent on where the qauntization function acts on the measurements, and if the quantizer is known (fix) a priori. In many situations it can be assumed that the quantizer is fix and known, however this is not always the case. One example where the quantizer may not be known is where it is adaptive, e.g. because of in loop automatic gain control. The identification problem and solutions discussed below all assume that the quantization scheme is known and fix.
In case the quantizer acts on the input signal, normal identification algorithms can be applied to solve the problem directly. The quantizer is simply allowed to act on the input of the model, and the new input can be used by conventional identification algorithms.
When the output signal is quantized, the problem becomes more difficult, cf. Figure 1.
Figure 1: Block diagram of a dynamic system with output quantization.
It is immediately clear that inversion is not an option. Hence the problem cannot be reduced to a conventional identification problem, not even in the case with linear dynamics. In the present project the first selected approach is therefore to use an output error identification strategy. A model corresponding to the system of Figure 1 (without the noise) is then created. The output from the dynamic system is simulated using the inputs and the present values of the estimated parameter vector. The simulated output is then passed through the model of the quantizer (which is known), after which a prediction error can be computed. It then remains to derive the parameter update algorithm, for off-line or recursive update. In the present research conventional search algorithms of gradient or Gauss-Newton type have been studied. A fundamental problem then arises in the derivation of the gradient. The problem is due to the fact that the gradient contains a factor which is the derivative of the output nonlinearity. In the case of a quantizer this derivative is identically zero except in the switchpoints where a Dirac pulse occurs - hence the exact derivative is useless for algorithmic use. The solution advocated in 5-8 is to replace the exact derivative of the quantizer by a smooth approximation, as illustrated in Figure 2. The approximation should be such that the gain is higher close to the switchpoints. In 5-8 and in Figure 2 a smooth approximation of the quantizer itself is first created and then differentiated. A sum of normalized, shifted and argument scaled arctan functions have been found to be particularly useful.
Figure 2: A quantizer and a corresponding approximation of the derivative. The approximation is obtained by differentiation of a sum of arctan functions.
Based on the above principles, a number of results have been obtained on
- Algorithms for recursive identification of linear systems of IIR and FIR type, using quantized and noise corrupted measurements of the output signal (5-8).
- Software for recursive identification of linear systems of IIR and FIR type, using quantized and noise corrupted measurements of the output signal (3,4).
- Theoretical results on the convergence properties of some of the algorithms (6, 8). This work is based on previous analysis performed in 9 and 10.
- Application of the results to combustion control (7) and vertical velocity tracking (5) in air traffic control tracking systems.
The algorithms discussed in 5-8 all allow an arbitrary quantization scheme that does not need to be monotone. The software package 3,4 consists of 5 algorithms using different approximations of the true gradient. There are 2 stochastic gradient algorithms that are best suited for FIR systems (although IIR systems can be treated). IIR systems are preferrably identified by one of the three Gauss-Newton algorithms. The software package contains supporting files for plotting and model validation. A manual is included.
The paper 6 proves,
Theorem 1: The stochastic gradient algorithm for recursive identification of FIR dynamics converges globally to a parameter setting with zero output error, provided that certain regularity conditions hold, the model is not underparameterized, the quantizer is monotone and the approximation of the derivative has the correct sign in all amplitude intervals (positive or negative).
The paper 8 proves,
Theorem 2: One of the Gauss-Newton algorithm for recursive identification of IIR dynamics converges locally to the true parameter vector, provided that certain regularity conditions hold, there is signal energy in at least one of the switchpoints and the mean of the output of the nonlinear dynamic block is different from at least one switchpoint.
The analysis uses the associated differential equation approach of L. Ljung.
The first application identifies the mixing dynamics of a compustion engine, using binary lambda-sensor measurements. The second application is needed to obtain accurate enough vertical velocity estimates in the tracking of vertical movement in air traffic control systems. The reason for the need of such high accuracy is the large prediction times used in the automatic collision avoidance systems. Then the coarsely quantized (100 feet) mode C altitude measurement may limit the sensitivity of the collision avoidance system - this being due to the 1000 feet vertical separation that is sometimes used.
As stated above, the normalized algorithm of 6, identifying finite impulse response dynamics using coarsely quantized output measurements, is proved to be convergent w.p.1. to a parameter setting where the input-output prediction error equals zero. Hence, the convergence properties resemble those of the NLMS-algorithm. Numerical results displaying this property are illustrated by Table 1.
Table 1: Convergence of the algorithm for compensation for quantization. The true parameter vector was (1 .000 -0.700 4.000 -2.800)^T and the quantizer had 5 levels. The left part of the table represent 16 initial values, whereas the right part represent the convergence points obtained after processing of 4000 samples.
The normalized algorithm was also shown to be applicable to removal of PCM quantization effects in adaptive echo cancellation loops.
Recently, another approach based on the expectation maximization (EM) algorithm has been developed, see 1 and 2 for details. Notably, that approach allows for systems noise entering before the quantizer. The EM algorithm is, as usual, applied in order to solve the maximum likelihood estimation problem. Hence the approach is significantly more complex than the one applied in 3-10. On the other hand, the EM approach is more general and the accuracy is improved as compared to 3-10.
1. B. I. Godoy, G. C. Goodwin, J. C. Aguero, D. Marelli and T. Wigren, "Identification of FIR systems having quantized output data using a scenario-based EM algorithm", Automatica, vol. 47, no. 9, pp. 1905-1915, 2011.
2. J. -C. Aguero, B. I. Godoy, G. C. Goodwin and T. Wigren, "Scenario-based EM identification for linear systems having quantized output data", to appear in Proceedings of the 15th IFAC Symposium on System Identification, SYSID 2009, Saint-Malo, France, July 6-8, 2009.
3. T. Wigren, "MATLAB software for recursive identification of systems with output quantization - Revision 1", Technical Reports from the department of Information Technology 2007-015, Uppsala University, Uppsala, Sweden, April, 2007.
4. T. Wigren, "MATLAB software for recursive identification of systems with output quantization - Revision 1", available at http://www.it.uu.se/research/publications/reports/2007-015/QRISRev1.zip, Uppsala University, Uppsala, Sweden, April, 2007.
5. E. Sviestins and T. Wigren, "Nonlinear techniques for Mode C climb/descent rate estimation in ATC systems", IEEE Trans. Contr. Sys. Tech. , vol. 9, pp. 163-174, 2001.
6. T. Wigren, Adaptive filtering using quantized output measurements, IEEE Trans. Signal Processing , vol. 46, no. 12, pp. 3423-3426, 1998.
7. T. Wigren and B. Carlsson, On the use of quantized lambda-sensor measurements in recursive identification of air-fuel mixing dynamics, Preprints of the IFAC Workshop on Intelligent Components for Vehicles , Seville, Spain, pp. 77-82, March 23-24, 1998.
8. T. Wigren, Approximate gradients, convergence and positive realness in recursive identification of a class of nonlinear systems, Int. J. Adaptive Contr. Signal Processing, vol. 9, no. 4, pp. 325-354, 1995.
9. T. Wigren, Convergence analysis of recursive identification algorithms based on the nonlinear Wiener model, IEEE Trans. Automat. Contr., vol. AC-39, no. 11, pp. 2191-2206, 1994.
10. T. Wigren, Recursive identification based on the nonlinear Wiener model, Ph.D. thesis, Acta Universitatis Upsaliensis, Uppsala Dissertations from the Faculty of Science 31, Uppsala University, Uppsala, Sweden, December, 1990.