Linear Estimation

Thomas Kailath
Ali H. Sayed
Babak Hassibi

Published March 2000 by Engineering/Science/Mathematics
Copyright 2000, 890 pp.
ISBN 0-13-022464-2


This textbook is intended for a graduate-level course and assumes familiarity with basic concepts from matrix theory, linear algebra, and linear system theory. Six appendices at the end of the book provide the reader with enough background and review material in all these areas. This original work offers the most comprehensive and up-to-date treatment of the important subject of optimal linear estimation, which is encountered in many areas of engineering such as communications, control, and signal processing, and also in several other fields, e.g., econometrics and statistics. The book not only highlights the most significant contributions to this field during the 20th century, including the works of Wiener and Kalman, but it does so in an original and novel manner that paves the way for further developments in the new millennium. This book contains a large collection of problems that complement the text and are an important part of it, in addition to numerous sections that offer interesting historical accounts and insights. The book also includes several results that appear in print for the first time.


  • Takes a geometric point of view.
  • Emphasis on the numerically favored array forms of many algorithms.
  • Emphasis on equivalence and duality concepts for the solution of several related problems in adaptive filtering, estimation, and control.
  • These features are generally absent in most prior treatments, ostensibly on the grounds that they are too abstract and complicated. It is the authors’ hope that these misconceptions will be dispelled by the presentation herein, and that the fundamental simplicity and power of these ideas will be more widely recognized and exploited. Among other things, these features already yielded new insights and new results for linear and nonlinear problems in areas such as adaptive filtering, quadratic control, and estimation, including the recent Hà theories.


1. Overview.
The Asymptotic Observer. The Optimum Transient Observer. Coming Attractions. The Innovations Process. Steady-State Behavior. Several Related Problems. Complements. Problems.

2. Deterministic Least-Squares Problems.
The Deterministic Least-Squares Criterion. The Classical Solutions. A Geometric Formulation: The Orthogonality Condition. Regularized Least-Squares Problems. An Array Algorithm: The QR Method. Updating Least-Squares Solutions: RLS Algorithms. Downdating Least-Squares Solutions. Some Variations of Least-Squares Problems. Complements. Problems. On Systems of Linear Equations.

3. Stochastic Least-Squares Problems.
The Problem of Stochastic Estimation. Linear Least-Mean-Squares Estimators. A Geometric Formulation. Linear Models. Equivalence to Deterministic Least-Squares. Complements. Problems. Least-Mean-Squares Estimation. Gaussian Random Variables. Optimal Estimation for Gaussian Variables.

4. The Innovations Process.
Estimation of Stochastic Processes. The Innovations Process. Innovations Approach to Deterministic Least-Squares Problems. The Exponentially Correlated Process. Complements. Problems. Linear Spaces, Modules, and Gramians.

5. State-Space Models.
The Exponentially Correlated Process. Going Beyond the Stationary Case. Higher Order Processes and State-Space Models. Wide Sense Markov Processes. Complements. Problems. The Linear Model Induced by State-Space Models.

6. Innovations for Stationary Processes.
Innovations via Spectral Factorization. Signals and Systems. Stationary Random Processes. Canonical Spectral Factorization. Scalar Rational z-Spectra. Vector-Valued Stationary Processes. Complements. Problems. Continuous Time-Systems and Processes.

7. Wiener Theory for Scalar Processes.
Continuous-Time Wiener Smoothing. The Continuous-Time Wiener-Hopf Equation. Discrete-Time Problems. The Discrete Time Wiener-Hopf Technique. Causal Parts via Partial Fractions. Important Special Cases and Examples. Innovations Approach to the Wiener Filter. Vector Processes. Extensions of Wiener Filtering. Complements. Problems. The Continuous-Time Wiener-Hopf Technique.

8. Wiener-Kalman Theory in the Vector Case.
Time-Invariant State-Space Models. An Equivalence Class for Input Gramians. Canonical Spectral Factorization. Factorization Given Covariance Data. Predicted and Smoothed Estimators of the State. Extensions to Time-Variant Models. Complements. Problems. The Popov Function. System Theory Approach to Rational Spectral Factorization. The KYP and Bounded Real Lemmas. Vector Spectral Factorization in Continuous-Time.

9. The Kalman Filter.
The Standard State-Space Model. The Kalman Filter Recursions for the Innovations. Recursions for Predicted and Filtered State Estimators. Triangular Factorizations of Ry and Ry^-1. An Important Special Assumption: Ri >> 0. Covariance-Based Filters. Approximate Nonlinear Filtering. Backwards Kalman Recursions. Complements. Problems. Factorization of Ry Using the MGS Procedure. Factorization via Gramian Equivalence Classes.

10. Smoothed Estimators.
General Smoothing Formulas. Exploiting State-Space Structure. The Rauch-Tung-Striebel (RTS) Recursions. Two-Filter Formulas. The Hamiltonian Equations (Ri >> 0). Variational Origin of Hamiltonian Equations. Applications of Equivalence. Complements. Problems.

11. Fast Algorithms.
The Fast (CKMS) Algorithms. Two Important Cases. Structured Time-Variant Systems. CKMS Recursions given Covariance Data. Relation to Displacement Rank. Complements. Problems.

12. Array Algorithms.
Review and Notations. Potter’s Explicit Algorithm for Scalar Measurement Update. Several Array Algorithms. Numerical Examples. Derivations of the Array Algorithms. A Geometric Explanation of the Arrays. Paige’s Form of the Array Algorithm. Array Algorithms for the Information Forms. Array Algorithms for Smoothing. Complements. Problems. The UD Algorithm. The Use of Schur and Condensed Forms. Paige’s Array Algorithm.

13. Fast Array Algorithms.
A Special Case: P0 = 0. A General Fast Array Algorithm. From Explicit Equations to Array Algorithms. Structured Time-Variant Systems. Complements. Problems. Combining Displacement and State-Space Structures.

14. Asymptotic Behavior.
Introduction. Solutions of the DARE. Summary of the Convergence Proofs. Riccati Solutions for Different Initial Conditions. Convergence Results. The Case of Stable Systems. The Case of S…Ö0. Exponential Convergence of the Fast Recursions. Complements. Problems.

15. Duality and Equivalence in Estimation and Control.
Dual Bases. Application to Linear Models. Duality and Equivalence Relationships. Duality Under Causality Constraints. Measurement Constraints and a Separation Principle. Duality in the Frequency Domain. Complementary State-Space Models. Complements. Problems.

16. Continuous-Time State-Space Estimation.
Continuous-Time Models. The Continuous-Time Kalman Filter Equations. Some Examples. Smoothed Estimators. Fast Algorithms for Time-Invariant Models. Asymptotic Behavior. Steady-State Filter. Complements. Problems. Backwards Markovian Models.

17. A Scattering Theory Approach.
A Generalized Transmission-Line Model. Backward Evolution. The Star Product. Various Riccati Formulas. Homogeneous Media: Time-Invariant Models. Discrete-Time Scattering Formulation. Further Work. Complements. Problems. A Complementary State-Space Model.

A. Useful Matrix Results.
Some Matrix Identities. Kronecker Products. The Reduced and Full QR Decompositions. The Singular Value Decomposition and Applications. Basis Rotations. Complex Gradients and Hessians. Further Reading.

B. Unitary and J-Unitary Transformations.
Householder Transformations. Circular or Givens Rotations. Fast Givens Transformations. J-Unitary Householder Transformations. Hyperbolic Givens Rotations. Some Alternative Implementations.

C. Controllability and Observability.
Linear State-Space Models. State-Transition Matrices. Controllabilty and Stabilizabilty. Observabilty and Detectabilty. Minimal Realizations.

D. Lyapunov Equations.
Discrete-Time Lyapunov Equations. Continuous-Time Lyapunov Equations. Internal Stability.

E. Algebraic Riccati Equations.
Overview of DARE. A Linear Matrix Inequality. Existence of Solutions to the DARE. Properties of the Maximal Solution. Main Result. Further Remarks. The Invariant Subspace Method. The Dual DARE. The CARE. Complements.

F. Displacement Structure.
Motivation. Two Fundamental Properties. A Generalized Schur Algorithm. The Classical Schur Algorithm. Combining Displacement and State-Space Structures.