The final sections of Chapter 4 of Luenberger's Optimization by Vector Space Methods (Wiley, 1969) derive the discrete-time Kalman filter (§4.7 Theorem 1, attributed to Kalman 1960) purely from Hilbert space geometry: the optimal estimate of a linearly evolving random state is an orthogonal projection onto the span of past measurements, and the projection updates recursively as measurements arrive. This derivation — no Gaussian assumptions, no density calculations — is a canonical application of the projection theorem formalized in Mission I and the estimation theory of Mission II.
Following §4.2 and §4.7 of the source, all random variables have zero mean and finite second moments, and are treated as elements of a Hilbert space of random variables: an abstract real inner product space in which the inner product of two random variables is their correlation, . Random -vectors are families ; two random variables are uncorrelated iff they are orthogonal in ; the covariance matrix of a zero-mean random vector is the Gram matrix . A white process satisfies .
The dynamic model (§4.7) consists of a state process and measurements
with known matrices , , white noises with covariances , ( positive definite), mutually uncorrelated and uncorrelated with the initial state . The estimate is the projection of each component of onto the subspace spanned by the components of .
The goal is §4.7 Theorem 1: the estimates generated by the recursion
started from and , are the linear minimum-variance estimates: each lies in the span of past measurement components, its error is orthogonal to all past measurements, and its error covariance is .
Milestones: orthogonality of the innovation to the past-data subspace, and the single-step updating formula (§4.6 Example 1) — given a prior projection with error covariance and new data , the updated projection is with error covariance .
The Kalman filter is among the most used algorithms in engineering — navigation, tracking, control, time-series analysis — and this mission gives it a machine-checked correctness statement at the natural level of generality: linear minimum-variance optimality over arbitrary zero-mean second-order processes, with no Gaussian hypothesis. Mathlib currently has no Kalman filter and no linear filtering theory. The abstract Hilbert-space formulation also makes the development directly reusable: the update milestone is a general two-stage projection lemma independent of the dynamic model.
The recursion couples two invariants that must be established simultaneously by induction: the geometric one (the error is orthogonal to the growing measurement subspace, and the estimate lies in it) and the algebraic one (the error Gram matrix equals ). Whiteness enters precisely through the index inequalities — and are orthogonal to everything generated by — and an off-by-one in these ranges silently breaks the induction. Invertibility of must be derived, not assumed: is positive semidefinite as a Gram matrix and is positive definite. The naive approach of expanding all projections over a concrete probability space adds measure-theoretic overhead the abstract formulation avoids entirely.
The Hilbert space of random variables is an abstract H : Type with [NormedAddCommGroup H] [InnerProductSpace ℝ H]; zero means are implicit in this representation (§4.7 assumes all variables zero-mean), so expectations never appear — only inner products. Matrix-vector actions on random vectors are written componentwise as ∑ j, A i j • x j. Processes are indexed by ℕ, with x̂(0 | -1) rendered as xh 0 = 0 and covariances as explicit Gram identities. Whiteness and uncorrelatedness are hypotheses on inner products with if k = l then _ else 0. The span of past data at time is Submodule.span ℝ {a | ∃ l < k, ∃ j, a = v l j}. The recursion defining xh and P is supplied as hypotheses, so the goal asserts exactly the optimality and covariance claims of the source theorem. Statements deliberately avoid Mathlib's orthogonalProjection; the projection property is asserted by membership plus orthogonality, which characterizes it uniquely.
namespace VectorSpaceOpt
theorem kalman_recursion {H : Type} [NormedAddCommGroup H]
[InnerProductSpace ℝ H] {n m : ℕ}
(Φ : ℕ → Matrix (Fin n) (Fin n) ℝ) (M : ℕ → Matrix (Fin m) (Fin n) ℝ)
(Q : ℕ → Matrix (Fin n) (Fin n) ℝ) (R : ℕ → Matrix (Fin m) (Fin m) ℝ)
(hR : ∀ k, (R k).PosDef)
(x u : ℕ → Fin n → H) (w v : ℕ → Fin m → H)
(hdyn : ∀ k i, x (k + 1) i = ∑ j, Φ k i j • x k j + u k i)
(hmeas : ∀ k i, v k i = ∑ j, M k i j • x k j + w k i)
(hQcov : ∀ k l i j, ⟪u k i, u l j⟫ = if k = l then Q k i j else 0)
(hRcov : ∀ k l i j, ⟪w k i, w l j⟫ = if k = l then R k i j else 0)
(huw : ∀ k l i j, ⟪u k i, w l j⟫ = 0)
(hux0 : ∀ k i j, ⟪u k i, x 0 j⟫ = 0)
(hwx0 : ∀ k i j, ⟪w k i, x 0 j⟫ = 0)
(P : ℕ → Matrix (Fin n) (Fin n) ℝ) (xh : ℕ → Fin n → H)
(hP0 : ∀ i j, P 0 i j = ⟪x 0 i, x 0 j⟫)
(hxh0 : ∀ i, xh 0 i = 0)
(hrec : ∀ k i, xh (k + 1) i =
∑ j, (Φ k * P k * (M k)ᵀ * (M k * P k * (M k)ᵀ + R k)⁻¹) i j •
(v k j - ∑ l, M k j l • xh k l) +
∑ j, Φ k i j • xh k j)
(hPrec : ∀ k, P (k + 1) =
Φ k * P k * (1 - (M k)ᵀ * (M k * P k * (M k)ᵀ + R k)⁻¹ * M k * P k) *
(Φ k)ᵀ + Q k) :
(∀ k i, xh k i ∈ Submodule.span ℝ {a : H | ∃ l < k, ∃ j, a = v l j}) ∧
(∀ k, ∀ l < k, ∀ i j, ⟪x k i - xh k i, v l j⟫ = 0) ∧
(∀ k i j, ⟪x k i - xh k i, x k j - xh k j⟫ = P k i j) := by sorry
end VectorSpaceOptWork in the Hilbert space of zero-mean random variables, , in which uncorrelated means orthogonal.
Consider the -dimensional dynamic model: a state evolving linearly with noise, observed through a linear measurement with noise,
with , known matrices. The process noises are white — and with each positive definite — mutually uncorrelated and uncorrelated with the initial state .
Write for the estimate of given the measurements up to time . Starting from and , generate estimates and matrices by the recursions
Then for every :
By the projection theorem, claims 1 and 2 say exactly that is the linear minimum-variance estimate of given the past data — so the recursion computes the optimal estimate, and tracks its error covariance. This is the discrete-time Kalman filter, obtained here with no Gaussian assumption anywhere: only second-order statistics enter, and optimality is among linear estimates.
Formalization Note. The two recursions are supplied as hypotheses defining and , so the conclusions assert precisely the optimality and covariance claims. Being the optimal estimate is expressed as span membership plus orthogonality of the error rather than through a projection operator. Zero means are implicit in the Hilbert-space-of-random-variables representation, so expectations appear only as inner products.
No open leaves. Every sub-goal is proved or awaiting decomposition.