Skip to main content

Full text of "DTIC ADA070967: System Modeling and Statistical Data Processing."

See other formats


AD-A070 967 STANFORD UNIV CALIF INFORMATION SYSTEMS LAB F/fi 12/1 

SYSTEM MODELING AND STATISTICAL DATA PROCESSING. (U) 

UNCLASCiFirn KAILATH F44620-74-C-006S 

UNCLASSIFIED AFOSR-TR-79*07S8 ML 











DOC FILE COPY MiA070967 


AEOSR-ia- 7 9-0788 

SYSTEM MODELING AND STATISTICAL 





.TA”PROCESSING 



FINAL REPORT OF RESEARCH ACTIVITIES UNDER AFOSR CONTRACT 
»F44-620-74-C-0068 

FOR THE PERIOD APRIL I, 1974 - MARCH 31, 1979 

The general research area is statistical modeling and signal processing, 
with emphasis on fast methods for signal estimation and detection. How- 
ever, these studies have a mutually fruitful interaction with several 
other problems, especially in Integral equations, scattering theory, 
multivariable systems, and more recently with network theory. 

The scope of our research effort may be gathered from the following 
list of i) journal papers published during the report period, ii) papers 
accepted for publication, iii) papers submitted for review, iv) published 
conference papers and v) conference presentations (without published 
papers. 

In addition to annual reports, a detailed review of work done during 
the first three years was submitted in mid-1977 and will not be reviewed 
here. As before, a good idea of the scope and progress of our continuing 
research effort can be gained from a perusal of papers published, papers 
to appear, and conference papers. In 1977-1978, we had one book and 8 
journal papers published. There were 12 papers in some stage of revision. 

Of these 12, 10 appeared during 1978-1979 and 16 other papers moved into 



this category during this period. One other paper and a Springer-Verlag 


monograph also appeared. The journals in which they appeared are IEEE 


Transactions on Information Theory, on Automatic Control, on Circuits 


and Systems, on Geoscience Electronics. The Annals of Statistics. Sankhya 


SIAM Review, Integral Equations and Operator Theory, and in an Academic 


Press book edited by I. C. Gohberg and M. Kac 


^orad for public release 

olatrlbutlen unllaited. 


were published , 5 at the 1978 IEEE Conference on Decision and Control, 
and one each at an International Symposium in Paris, an American Geo- 
physical Union Chapman Conference in Pittsburgh, The Johns Hopkins 
Information Sciences Conference and an AFOSR Communication Theory Work- 
shop in Provincetwon. Several other talks and seminars were presented, 
without formal written papers, at several conferences and seminars. 

As in earlier years, this work has been well cited in the literature 
as can be seen from Science Citations Index. 

Five Ph.D. theses were completed in the last two years by S. Rung 
(now an Assistant Professor at USC) , A. Vieira (now in Brazil), 

J. Dobbins (now at Bell Laboratories), Sally Wood (now at Telesensor 
Systems), G. Verghese (now an Assistant Professor at MIT). Abstracts 
of these theses are attached, and along with the detailed list of 
publications, should give a better idea of the technical efforts under 


this contract. 


air force office of scikktific research (AFSC) 
notice CF 'Cr.'J’SMITT.AL TO DDC 

This techiU’^l r..;jc.vL J.ci.. been reviewed and is 

Distrlbu'.icn ia 

TMtalcal Ir.lcr.r.ntio'T Officer 



2 



PUBLISHED PAPERS 

P-1 T. Kailath, A. Segall and M. Zakai, "Fubini-Type Theorems for 

Stochastic Integrals," Sankhya . The Indian J. of Stat .. vol. 40, 
Series A, 1978. 

P-2 T. Kailath, A. Vieira and M. Morf, "Inverses of Toeplitz Operators, 
Innovations, and Orthogonal Polynomials," SIAM Review , vol. 20, 
no. 1, pp. 106-119, January 1978. 

P-3 B. D. Anderson and T. Kailath, "Fast Algorithms for the Integral 

Equations of the Inverse Scattering Problem," Integral Equations and 
Operator Theory , vol. 1, no. 1, pp. 132-136, 1978. 

P-4 M. Morf, A. Vieira and T. Kailath, "Covariance Characterization by 

Partial Autocorrelation Matrices," The Annals of Statistics , vol. 6, 
no. 3, pp. 643-648, 1978. 

P-5 M. Morf, A. Vieira, D. T. Lee and T. Kailath, "Recursive Multi- 
channel Maximum Entropy Spectral Estimation," IEEE Trans, on Geo - 
Science Electronics , vol. GE-16, no. 2, pp. 85-94, April 1978. 

P-6 T. Kailath, B. Levy, L. Ljung and M. Morf, "Fast Time- Invariant 
Implementations of Gaussian Signal Detectors," IEEE Trans, on 
Information Thy . , vol. IT-24, no. 4, pp. 469-477, July 1978. 

P-7 B. Friedlander, T. Kailath, M. Morf and T. Kailath, "Extended 
Levinson and Chandrasekhar Equations for General Discrete-Time 
Linear Estimation Problems," IEEE Trans, on Automatic Conttol . vol. 
AC-23, no. 4, pp. 653-659, August 1978. 

P-8 M. Morf, B. Levy and T. Kailath, "Square-Root Algorithms for the 

Continuous -Time Linear Least-Square Estimation Problem," IEEE Trans 
' on Automatic Control , vol. AC-23, no. 5, pp. 907-911, October 1978. 




1 


i 

1 . 

i 



3 


P-9 R. R. Bitmead, S-Y. Kung, B- D. Anderson and T. Kailath, "Greatest 


Common Divisors Via Generalized Sylvester and Bezout Matrices," 

IEEE Trans, on Automatic Control , vol. AC-23, no. 6, pp. 1043-1047, 
December 1978. 

P-10 T. Kailath, L. Ljung and M. Morf, "Generalized Krein-Levinson 
Equations for Efficient Calculation of Fredholm Resolvents of 
Nondisplacement Kernels," Topics in Functional Analysis, Advances 
in Math. Supplementary Studies , vol. 3, pp. 169-184, 1978. 

P-11 G. Verghese and T. Kailath, "A Further Note on Backwards Markovian 
Models," IEEE Trans, on Information Thy ., vol. IT-25, no. 1, pp. 
121-124, January 1979. 

PUBLISHED BOOKS 

T. Kailath, Lectures on Linear Least-Squares Estimation . CISM Courses 
& Lectures No. 140, International Centre for Mechanical Sciences, 

New York: Springer-Verlag, 1978. 



I 

ACCEPTED PAPERS TO APPEAR 

A-1 G. Verghese, P. Van Dooren and T. Kallath, "Properties of the System 
Matrix of a Generalized State-Space System," International J. of 
Control , to appear. 

A-2 G. Verghese and T. Kailath, "Comments on 'On Structural Invariants 
and the Root-Loci of Linear Multivariable Systems' ," International 
J. of Control , to appear. 

A-3 B. D. Anderson and T. Kailath, "Passive Network Synthesis via Dual 
Spectral Factorization," I EEE Trans, on Circuits & Systems , to 
appear. 

A-4 B. Levy, L. Ljung and M. Morf, "The Factorization and Representation ; 

of Operators in the Algebra Generated by Toeplitz Operators," SIAM 1 

J. on Appl. Math . , to appear . 1 

A-5 B. Friedlander, M. Morf, T. Kailath and L. Ljung, "New Inversion ij 

Formulas for Matrices Classified in Terms of their Distance from || 

Toeplitz Matrices," Linear Algebra and Its Applications , to appear. ! 

A-6 B. D. Anderson and T. Kailath, "Forwards and Backwards Models for j| 

Finite-State Markov Processes," J. of Applied Probability , to i 

appear. 

A-7 A. Segall and T. Kailath, "Martingales in Nonlinear Least-Squares 

t 

Estimation Theory," Nonlinear Filtering , ed. by E. Stear, Marcel 3 

; 5 

Dekker Publishing Co., to appear. j| 

A-8 T. Kailath, "Sigma-Fields, Martingales, Stochastic Integrals and 
All That (Almost Surely)," Proc. IEEE , to appear. 


A-9 M. Morf, J. R. Dobbins, B. Friedlander and T. Kailath, "Square-Root 

Algorithms for Parallel Processing in Optimal Estimation," Automatics . 





vol. 15, 1979. 

A-10 T. Kailath, S-Y. Kung and M. Morf, "Displacement Ranks of Matrices 
and Linear Equations," J, of Math. Analysis and Applications , to 
appear. 

A-11 T. Kailath, S-Y. Kung and M. Morf, "Displacement Ranks of a Matrix," 
Bulletin American Math. Society , 1979. 

A-12 S-Y. Kung and T. Kailath, "Fast Algorithms for the Minimal Design 
Problem," Automatlca , to appear. 

A-13 M. Morf, E. Verriest, J. R. Dobbins and T. Kailath, "Square-Root 

Algorithms for Model Sensitivity Analysis," Automatica . to appear. 
A-14 B. Friedlander and T. Kailath, "Scattering Theory and Linear Least 

I 

Squares Estimation, Pt, III: The Estimates," IEEE Trans, on Automatic 
Control, to appear. 

A-15 G. Verghese, B. Levy and T. Kailath, "Generalized State-Space 

Systems," IEEE Trans, on Automatic Control , to appear. 

I 

I A-16 B. Levy, T. Kailath, L. Ljung and M. Morf, "Fast Time- Invariant 

ii 

Implementations for Linear Least-Squares Smoothing Filters," IEEE 
Trans, on Automatic Control , to appear. 

SUBMITTED PAPERS 

S-1 T. Kailath, L. Ljung and M. Morf, "Recursive Input-Output and State- 
Space Solutions for Continuous-Time T.inear Estimation Problems," 
submitted to IEEE Trans, on Automatic Control . 1978. 

S-2 G. Verghese and T. Kailath, "Rational Matrix Structure," submitted 
to IEEE Trans, on Automatic Control, 1979. 




6 




CONFERENCE PAPERS 

C-1 M. Morf, J. Dobbins, J. Newkirk and T. Kailath, "Square-Root Doubling 
for Steady State Riccati Solution: A Viable Method?," Conference 
on Information Sciences & Systems, Johns Hopkins University, 

Baltimore, MD, March 1978. 

C-2 T. Kailath, "Some Alternatives in Recursive Filtering," Chapman 

Conference on Applications of Kalman Filtering Theory and Technique 
to Hydrology. Hydraulics, and Water Resources . Univ. of Pittsburgh, 
Pittsburgh, PA, May 1978. 

C-3 M. Morf and D. Lee, "Recursive Spectral Estimation of Alpha-Stationary 
Processes," Proc. Rome Air Development Center . Spectrum Estimation 
Workshop . Griffiss AFB, New York, pp. 97-108, May 1978. 

C-4 T. Kailath, "Forwards and Backwards Markovian Models for Second- 

Order Processes," Proc. AFOSR Workshop in Communication Theory and 
Applications , pp. 2-3, Provincetown, MA, September 1978. 

C*5 T. Kailath, A. Vieira and M. Morf, "Orthogonal Transformation 
(Square-Root) Implementations of the Generalized Chandrasekhar 
and Generalized Levinson Algorithms," International Symposium on 
Analysis and Optimization of Systems . IRIA, Paris, December 1978. 

C-6 G. Verghese, B. Levy and T. Kailath, "Generalized State-Space 

Systems," Proc. 1978 IEEE Conference on Decision & Control . San 
Diego, CA, pp. 518-520, January 1979. 

C-7 s. Kung and T. Kailath, "Some Notes on Valuation Theory in linear 
Systems," Proc. 1978 IEEE Conference on Decision & Control . San 
Diego, CA, pp. 515-517, January 1979. 




1 m — »Miii 


7 



C-8 B. Levy, T. Kailath, L. LJung and M. Morf, "Fast Time-Invariant 
Implementations for Linear Least-Squares Smoothing Filters," 

Proc. 1978 IEEE Conference on Decision & Control . San Diego, CA, 
pp. 1156-1159, January 1979. 

C-9 P. Van Dooren, G. Verghese and T. Kailath, "Properties of the System 
Matrix of a Generalized State-Space System," Proc. 1978 IEEE Symposium 
on Decision & Control . San Diego, CA, pp. 173-175, January 1979. 

C-10 M. Morf and D. Lee, "Recursive Least Squares Ladder Forms for Fast 
Parameter Tracking," Proc. 1978 IEEE Conference on Decision & 

Control . San Diego, CA, pp. 1362-1367, January 1979. 


i 



Multivariable and Multidimensional Systems: 
Analysis and Design 
June 1977 


ABSTRACT 


S. Kung 


This thesis contains two parts. The first part presents some 
topics in the analysis and design of multivariable (mul ti.- inpat, multi*" 
output) systems. The second part contains results that provide a foun"* 
dation for a comprehensive state-space and algebraic study of systems 
described by two or more independent variables, which are termed multi- 
dimensional systems. 

In the first part of this thesis, we give new algorithms for 

determining the greatest common divisor (GCD) of two polynomial matrices 

as well as solving minimal design and partial realization problems. Our 

• • » 
approach will demonstrate the power of using certain polynomial echelon 

matrix fraction descriptions, v/hich depend closely upon the fundamental 

concepts of column-reduced matrices and minimal bases of vector spaces 

over the rational field. 

The time- invariance of the systems we deal with ensures a 
certain shift- invariance structure in some basic matrices, such as the 
generalized resultant matrix and the Hankel matrix that arise in many 
linear systems problems. Combining these invariance properties with 
the polynomial echelon form, we develop a variety of fast algorithms • 
for GCD extractions, minimal design problems, and minimal partial reali- 


zations. 


In the second part of this thesis, we successfully extend 


! some existing one-dimensional results, such as GCD extractions, coprime- 
ness tests, and matrix fraction descriptions to the two-dimensional case. 


9 


We also discuss some results that appear to be unique to multidimen" 


sional systems, such as the existence and uniqueness of primitive 
factorizations, and the general factorizations of tv/d”dimensional 
polynomial matrices. It appears to be the first time that tv/o dimen-' ' 
sional polynomial matrix theory has been studied to such an extent. 

We also present several new results on two-*di men sional state- 
space representations, including comparisons of various existing models, 
methods for circuit realizations using a minimal number of dynamic 
elements, and a new technique for tvAj-dimensional digital filter hard- 
ware implementations. ; 



\ ^ 


■ -f 


sir 


! 


Si 




i f 


December 1977 


MATRIX ORTHOGOWAL POLYNOMIALS, 

WITK APPLICATIONS TO AUTOREGRESSIVE MODELING AND LADDER FORMS 


August© Cesar Gadelha Vieira, Ph, D, 
Stanford University 


Jn this work we obtain some results related to modeling end filtering OlT 
multivariate time series. A framevrork for the development of such results is 
provided by the theory of orthogonal polynomials on the unit circle. This theory 
and its applications, such as in stochastic and statistical problems, are by now 
well established for the scalar case. In chapter I we give an account of the 
theory of matrix orthogonal polynomials with some of their most useful 
properties. These seem to be less knov/n even though some results in this context 
have already been reported in the literature. This subject has great interest by 
itself. For the sake of generality, we assume an indefinite weighting matrix, 
specializing for the non-negative definite case when needed. 

The orthogonal polynomials obey well known recursions that play a central 
role in oar vrork. These are the same as the equations obtained in the problem of 
fitting an autoregressive model to a given segment of a covariance function. By 
considering a normalized form of these recursions we shovr in chapter XI that a 
covariance function can be uniquely specified by a sequence of "partial 
correlation" or "reflection" matrix coefficients, each of which has singular . 
values of magnitude less than one. This result is used in the following chapters. 


Chapter III explores some connections of the previous chapters with network 
theory. The above mentioned recursions can be regarded as performing a 
coprime factorization of a certain matrix function, such a factorization being 
equivalent to the Darlington synthesis procedure in network theory. This 
interpretation enables us to generalize these recursions to produce 


■ A 


’ 'll 


11 


autore^i'essive-xnovinfi average models of a covariance /unction. Closely related 
to this is the theory of the multiplicative reprasentalion of a J~contraclive 
matriai function as established by Potapov. . 

The autoresressive fitting procedure mentioned above has Jed to a new method 
of spectral estimation based on direct estimation of the reflection coefficients, 
generally known as (Burg’s) maximum entropy method. There have been many 
succesful applications of this technique, e.g. in the analysis of seismic, and 
speech signals. However, satisfactory multivariate (or multichannel) extensions 
of this technique have been obtained only recently, I'n chapter JV we giva one 
such extension, using the result of chapter IJ. 

The reflection coefficients are usually estimated by cross-'correlating (using 

• . 

sample averages) the so-called forv/ard and backviard residuals. This method is 
most suited for batch data processing. In many applications ' on-line 
SrapJementations are desired, e.g. in speech processing. In this case the use of 
instantaneous sample averages, or some slight modification thereof, has been 
proposed in the literature. However, these approximations tend to converge very 
slowly to the batch sample averages. This is partially due to the fact that no 
global error criteria is minimized. As an alternative we present in chapter V a 
nev/ class of ladder forms. The reflection coefficients of these forms are 
recursively computed from the data, such that their impulse response is equal to 
the exact (global) least-squares predictor. These new ladder forms provide 
alternatives that have some advantages over the usual maximum entropy methods ' 
eve 72 when batch processing is used. Experimental results .seem to confirm these • - 
expectations. . ' ■ \ . 


12 



i 




S. Wood 

A System Theoretic Approach to Image Reconstruction 
May 1978. 


ABSTRACT 

The problem of extracting all of the information from each measure- 
ment used for image reconstruction in computerized tomography becomes 
important when only a limited number of measurements are available 
or when the measurements have a significant variance. These conditions 
can occur when dosage is lowered, in limited angle applications, or 
when the object to be reconstructed is moving periodically so that only 
a limited number of synchronized measurements are valid. In such cases 
algorithms which take into account the stochastic nature of the mea- 
surements and include a priori information generally perform much 
better than deterministic methods even though the deterministic algor- 
ithms do perform well in common applications with abundant low noise 
measurements. 

In this thesis the linear minimum variance estimator is applied 
to emission and transmission tomography. Both information filter and 
covariance filter forms are discussed as well as recursive square root 
implementations. The Influence on mean squared error of variations in 
dosage and measurement geometry is examined in terms of singular 
values of the projection matrix. 

Standard deterministic algorithms are analyzed in a stochastic 
context. For each algorithm the implicit assumptions that would make 
it equivalent to the minimum variance estimator are derived. This 
analysis results in the specification of otherwise arbitrary parameters 
in the algorithms. New approximate algorithms based on specific 
statistical assumptions are derived. 


[ 

t 


13 





Symmetries of the measurement acquisition arrangement are used 


to achieve an order of magnitude savings in computation time and 


storage required for implementation of the minimum variance estimator 


Three possible implementation strategies are discussed. The specific 


symmetries required do not exclude the limited angle application 


Simulations of expected squared errors demonstrate a substantial 


Improvement when the minimum variance estimator Is used instead of 


approximate methods in both low and high noise cases. The new approxi 


mate algorltlims give consistently better results than ART in medium 


and high noise cases. Simulated reconstructions of a phantom give 


squared error results consistent with the mean squared error predic 


tions. In addition, features of the phantom which are visible in the 


minimum variance estimator reconstruction cannot be seen in the 


imate method reconstructions 


The minimum variance estimator is shown in this thesis to offer 


substantial improwment in performance over more classical reconstruc 


tlon techniques, particularly when dosage must be lowered or a full set 


of measurements is not available. In cases such as these, compute 


tionally efficient implementations of the minimum variance estimator 


such as those discussed here should prove to be diagnostically sign! 


f leant 


Infinite-Frequency Behaviour in Generalized 
D}maailcal Systems 

December 1978. 


G. Verghese 


ABSTRACT 


The dynamical systems considered in this thesis are systems of 


ordinary, linear, time- invariant differential equations that, starting 


from some Initial time, relate the behaviour of a set of Internal sysU< 


variables to that of control inputs and observation outputs for the 


system. In particular, we are concerned with those dynamical systems 


that, with control inputs fixed at zero, are capable of iigpulslve motions 


at the initial time if given arbitrary initial conditions, motions that 


may be formally treated as infinite-frequency free-response modes. Such 


systems we term generalized dynamical systems . . 


Their behaviour is essentially accounted for by the fact that 


their describing equations imply certain constraints on the associated 


variables that may not be satisfied if arbitrary initial conditions are 


imposed; the impulses are then a consequence of the transition to con- 


sistent variable values. The reason that a framework for treating such 


systems has not emerged prior to our work may now. In view of the preceding 


interpretation, be explained: in the extensive literature on dynamical 


systems it is tacitly assumed, virtually without exception, that the 


systems considered have existed prior to the initial time of analysis; 


the resulting constraints on the initial conditions then guarantee that 



no impulsive behaviour occurs. 

Our framework becomes important for systems formed ^ the initial 
time, as a result of perhaps switching or component failure in other 
systems. It also yields new and interesting results for systems which, 
if formed at the initial time, could exhibit impulsive behaviour; this 
point of view is vital when considering, for example, )»ow properties of 
subsystems are reflected into those of composite systems formed by inter-; 
connecting them. It is conjectured that our theory will, in addition, be 
useful in treating systems that are Idealized limits of other (’sfngularly 
perturbed*) systems that do not impose constraints Cor that impose differ»- 
ent constraints) on the associated variables. Besides such appllcatldns, 
our development leads to ne\7 results on, and insights into the behaviour 
at infinite frequencies of even those dynamical systems Cwhlch we term 
regular dynamical systems) that exhibit n^ impulsive f ree-response modes « 

A tutorial, but yet somewhat novel treatment of the pole-zero 
structure of rational, frequency-domain, transfer-function matrices, at 
finite and infinite frequencies, forms the background for our analysis. 
Pole-zero structure is studied via both general decompositions to diagonal 
matrices and transformations to so-called column- (or row-) reduced 
matrices (with certain new results on rational bases for rational vector 
spaces emerging from our study of these reduced matrices) . 

A description of the detailed structure of the infinite-frequency 
or impulsive modes of an undrlven system is then obtained, apparently for 
the first time. A generalized order that accounts for the degrees of 
freedom associated with all the modes, impulsive and non- impulsive. Is 
defined. The coupling of the impulsive modes to the system input and 


and output is characterized by definitions of controllability and observa- 
bility for these modes. Much of the theory for regular dynamical systems 
is thereby extended to generalized dynamical systems. 

More detailed and extensive results are obtained for the special 
case of generalized state-space systems . which comprise first-order 
differential equations coupled with algebraic constraints, and form the 
simplest interesting example of generalized dynamical systems. For such 
systems a useful class of equivalence transformations is identified, and 
used, for example, to display the unobservable and/or uncontrollable 
impulsive modes. 


Covariance Factorization Techniques for 
Least Squares Estimation 
January 1979 


J« R. Dobbins 


Abstract 

Square root, least squares estimation algorithms are examined from 
the viewpoint that square root arrays are arrays expressing relevant 
problem random variables in terms of basis sets of orthonormal (identity 
covariance) random variables. With this viev/point, projection-theorem 
arguments can be expressed directly in the square root arrays, giving 
simple, geometric derivations of square root algorithms. A unifying 
framework is provided for previously proposed square root algorithms 
(and square-root-free factorization algorithms), and several new square 
root estimation procedures are derived- 

An inversion duality relating covariance and information forms is 
demonstrated to be more v/idely applicable than the standard duality. A 
compact explanation for previously reported techniques of a posteriori 
determination of the effects of neglecting bias parameters in the model 
and of computational reduction when subsets of the estimates are conditionally 
independent is given in terms of the relationship among orthonormal basis 
variables induced by triangular square root arrays. Square root versions 
of all major smoothing algorithms are derived; several of these square 
root versions have not been published previously. 

A new set of square root algorithms is proposed in which a good deal 
of the computation may be performed in parallel by different processors 
with very little inter-processor communication. Even v/hen only a single 
processor is available, the approach underlying these algorithms offers 
computational reductions when covariances are needed at relatively few 
few time points in an interval. This is especially true when the model 


18 



r 


of the observed process has time invariance properties. One specialization 
of particular interest is a square root doubling algorithm for computing 
the steady state solution of time invariant, matrix Riccati equations. 

This algorithm computes square roots of P(t), P{2t), P(^t), ... on 
successive iterations, where P is the matrix Riccati variable. 

Square root techniques for determining the actual error covariance 
of a state estimate based on an incorrect model are extended. The ease 
with which either of tv/o previously proposed techniques may be used with 
either the covariance or the information form of the estimator is enhanced. 
The tv/o techniques are compared, and some guidance is provided as to when 
the use of each is advantageous. Square root error ^nalysi s is extended 
to the smoothing problem. 



cL, 


READ INSTRUCTION'S 
BEFORE COMPLETING FORM 


2. GOVT ACCESSION NO. i- RECIPIENT'S CATALOG NUMBER 


ITLE (and SiiblllU) 


S. TTPE OF REPORT A PERIOD COVERED 


JYSTEM JIODELING AND_STATISTICAL MTA_PROCESSING • 




Thoma s/ Ka ila t h 


9. PERFORMING ORGANIZATION NAME AN^AOORESS 

Information Systems Laboratory -Dept of Elec. Eng, 
Stanford University 
Stanford, CA 94305 



Ml. CONTROLLING OFFICE NAME AND ADDRESS 


31 Mar. 


Air Force Office of Scientific Research/NM B P 

Bolling AFB, Washington, D.C. 20332 2.9 

u. MONITORING AGENCY NAME A ADDRESSfJ/ dlijirtnl from Conlroltlng Ollict) IS. SECURITY CLASS, (ol Ih/i report) 




UNCLASSIFIED 

ISa. DECLASSI FI CATION/ down grading 
schedule 


fisi DISTRIBUTION STATEMENT (o! this Report) 


Approved for public release; distribution unlimited. 


17. DISTRIBUTION ST. 4ENT (of ' • abatract antarad in Block 20, If diffarant from Raport) 


18. SUPPLEMENTARY 


1 19. KEY WORDS (Continua on ravaraa aida if nacaaaary and Idantify by block number) 




0. A^^RACT (Continua on reverse aida If nacaaaary and Identify by block number) 

■”' Square root, least squares estimation algorithms' are examined from the 
viewpoint that square root arrays are arrays expressing relevant problem random 
variables in terms of basis sets of orthonormal (identity covariance) random 
variables. With this viewpoint, projection-theorem arguments can be expressed 
directly in the square root arrays, giving simple, geometric derivations of 
square root algorithms. A unifying framework is provided for previously 
proposed square root algorithms (and square-root-free factorization algorithms), 
and several new square root estimation procedures are derived, (continued) 


DD 


UNCLASSIFIED 














»r'iHITY CLASSIFICATION OF THIS PAGEfUTian Data Entarad) 


2*^ Abstract (continued) 


An inversion duality relating covariance and information forms is demonstral ed 
to be more widely applicable than the standard duality, A compact explanation 
for previously reported techniques of a posteriori determination of the effects 
of neglecting bias parameters in the model and of computational reduction when 
subsets of the estimates are conditionally Independent is given in terms of the 
relationship among orthonormal basis variables induced by triangular square root 
arrays. Square root versions af all major smoothing algorithms are derived; 
several of these square root versions have not been published previously. 


A new set of square root algorithms is proposed in which a good deal 
of the computation may be performed in parallel by different processors 
with very little inter -processor communication. Even when only a single process( 
is available, the approach underlying these algorithms offers computational 
reductions when covariances are needed at relatively few few time points in 
an interval. This is especially true when the model of the observed process 
has time invariance properties. One specialization of particular interest 
is a square root doubling algorithm for computing the steady state solution of 
time Invariant, matrix Riccati equations. This algorithm computes square roots 
of P(t), P(2t), P(4t),... on sucessive iterations, where P is the matrix 
Riccati varible. 

Square root techniques for determining the actual error covariance of 
a state estimate based on an incorrect model are extended. The ease with 
which either of two previously proposed techniques may be used with either 
the covariance or the information form of the estimator is enhanced. The 
two techniques are compared, and some guidance is provided as to when the 
use of each is advantageous. Square root error analysis is extended to the 
smoothing problem.