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.
