25-EFT.WP.STG.Dynamics v1.0 | Chapter 12 — Data Assimilation and Filtering (KF / UKF / PF on Graphs)

Home ／ Docs-Technical WhitePaper ／ 25-EFT.WP.STG.Dynamics v1.0

Chapter 12 — Data Assimilation and Filtering (KF / UKF / PF on Graphs)

One-Sentence Goal
Provide a unified assimilation framework for linear/nonlinear state estimation on graphs—KF / UKF / PF—that fuses graph operators with observations and closes the loop predict → update → publish with auditable contracts.

I. Scope and Objects

1. Objects
   • Graph dynamics: ( d x / d t ) = f(x, u; L, θ) + w(t); discrete x_{k+1} = Φ_{Δt}(x_k, u_k; L, θ) + w_k.
   • Observation model: y_k = h(x_k; H, ψ) + v_k, with H as sampling / aggregation / path-integral operators.
   • Sensor fusion: multi-source y_k^{(s)}, multi-rate Δt_s, heterogeneous R_s, and cross-scale { R, P } (Ch. 11).
2. Inputs
   Graph & operators { G, A, L }; discrete propagator (e.g., A = exp( − κ Δt L ) or numerical approximations); Q, R or priors; sensor metadata (location, latency, units, RefCond).
3. Outputs
   Estimates x̂_{k|k}, covariances P_{k|k} or particle sets { x^{(i)}, w^{(i)} }; residuals & statistical tests; manifest.stg.filter.
4. Constraints & boundaries
   • unit(x), unit(y), unit(u) required; if nonnegativity/conservation is declared, apply projected or constrained filters.
   • Time semantics: compute on tau_mono, publish on ts (see EFT.WP.Metrology.TimeBase v1.0).

II. Terms and Variables

• State & obs: x_k ∈ R^{|V|}, y_k ∈ R^{m}, control u_k.
• Graph operators: L (Laplacian), A (propagator), κ (diffusivity).
• Noise: w_k ~ N(0, Q), v_k ~ N(0, R) or general; covariance P.
• Observation map: linear H, nonlinear h(•); selection matrix S for subsampling.
• Multiscale maps: R (restriction), P (prolongation).
• Dual-form gap (predict vs assimilate): delta_form_assim.

III. Axioms P712-*

• P712-1 (Parallel dual forms) — At each step k, compute prediction x̂_{k|k−1} and assimilation x̂_{k|k} in parallel; record
  delta_form_assim = || x̂_{k|k} − x̂_{k|k−1} ||_2 and innovation r_k = y_k − h( x̂_{k|k−1} ).
• P712-2 (Explicit measures/domains) — Expectations ( ∫ p(x) • dx ); temporal accumulation ( Σ_{k∈𝕂} • ) or ( ∫_t • dt ).
• P712-3 (PSD invariance) — P_{k|k−1}, P_{k|k} ≽ 0; if numerics break PSD, repair via symmetrization + spectral truncation.
• P712-4 (Unit consistency) — check_dim( y_k − h(x̂) ) = unit(y); check_dim(P) = unit(x)^2.
• P712-5 (Time & latency) — Record offset / skew / J; align during update (see TimeBase / Sync).
• P712-6 (Graph prior alignment) — If the model uses Ch. 7/4 operators, L.hash / A.hash in filtering must match.

IV. Minimal Equations S712-*

• S712-1 (Linear KF on graphs):
  Dynamics x_{k+1} = A x_k + B u_k + w_k, y_k = H x_k + v_k.
  Predict:
• x̂_{k|k−1} = A x̂_{k−1|k−1} + B u_{k−1}
• P_{k|k−1} = A P_{k−1|k−1} A^T + Q

Update:

S_k = H P_{k|k−1} H^T + R

K_k = P_{k|k−1} H^T S_k^{−1}

x̂_{k|k} = x̂_{k|k−1} + K_k ( y_k − H x̂_{k|k−1} )

P_{k|k} = ( I − K_k H ) P_{k|k−1} ( I − K_k H )^T + K_k R K_k^T

If A = exp( − κ Δt L ), approximate via ( I + κ Δt L )^{−1} or split-integration (Ch. 9).

• S712-2 (UKF on graphs):
  Nonlinear x_{k+1} = f(x_k, u_k; L, θ) + w_k, y_k = h(x_k) + v_k.
  Form 2n+1 sigma points χ_i, weights { W_m, W_c }; propagate means/covariances, build cross-covariance with h(χ_i) and compute gain.
  Recommend sparse L x or convolutional kernels for O(|E|) cost.
• S712-3 (PF on graphs):
  Propagate: x_k^{(i)} ~ p( x_k | x_{k−1}^{(i)}, u_{k−1} );
  Weight: w_k^{(i)} ∝ w_{k−1}^{(i)} • p( y_k | x_k^{(i)} );
  Normalize & resample (systematic / residual / multinomial).
  Effective sample size ESS = 1 / ( Σ_i ( w_k^{(i)} )^2 ).
  For high-dimensional graph states, use clustered particles or RBPF: KF for Gaussian submodules, PF for non-Gaussian ones.
• S712-4 (Multi-source / multi-rate fusion):
  For each source s, when k ∈ 𝕂_s arrives, run local update (H_s, R_s) sequentially or in batch:
  K_s = P H_s^T ( H_s P H_s^T + R_s )^{−1}, loop over s, and update
  P ← ( I − K_s H_s ) P ( I − K_s H_s )^T + K_s R_s K_s^T.
• S712-5 (NIS & whiteness tests):
  Normalized innovation squared NIS_k = r_k^T S_k^{−1} r_k; its χ² coverage validates consistency.
  Residual autocorrelation ( Σ_k r_k r_{k−τ}^T ) near zero supports whiteness.
• S712-6 (RTS smoothing & graph-constrained projection):
  RTS: C_k = P_{k|k} A^T P_{k+1|k}^{−1}, x̂_{k|T} = x̂_{k|k} + C_k ( x̂_{k+1|T} − x̂_{k+1|k} ).
  Physics constraints: solve min_z || z − x̂_{k|k} ||_2^2 s.t. z ≥ 0, 1^T z = c (if conservation declared).
• S712-7 (Dual-form gap):
  delta_form_assim = || x̂_{k|k} − x̂_{k|k−1} ||_2; window average
  Δ̄ = ( Σ_{k∈𝕂} delta_form_assim ) / |𝕂|.

V. Metrology Workflow M7-12 (Ready → Model/Estimate → Assimilate → Validate → Persist)

1. Ready
   Align time base & delays; load L/A with hashes; declare unit(*) / RefCond; choose { KF, UKF, PF, RBPF } and multi-source strategy.
2. Model / Estimate
   • Build A/B or f(•) and h(•); init x̂_0, P_0; set Q, R (priors or EM/ML tuned).
   • Cross-scale: if filtering on |V_c|, use R, P down/up maps (Ch. 11).
3. Assimilate
   Predict → update (or propagate → weight → resample); sequential multi-source updates; project to feasible domain as needed.
4. Validate
   • Statistical consistency: NIS coverage, residual whiteness; ESS lower bound; PSD & conditioning of P; delta_form_assim p95.
   • Numerical stability: step and stiffness handling (Ch. 9); on instability, raise alerts and fallback.
5. Persist / Publish
   manifest.stg.filter = { algo, L/A.hash, H.hash, Q/R.meta, x̂, P/ESS, nis: { p_quantile, window }, resid: { acorr }, deltas: { Δ̄, p95 }, constraints, RefCond, units, method.hash }.

VI. Contracts & Assertions C70-12xx

• C70-1201 (NIS coverage): Pr( χ^2_{m,α/2} ≤ NIS_k ≤ χ^2_{m,1−α/2} ) ≥ 1−β (suggest α = 0.05, β = 0.1).
• C70-1202 (Covariance PSD): P_{k|k} ≽ 0 and cond(P_{k|k}) ≤ γ_P (suggest γ_P ≤ 1e8).
• C70-1203 (Residual whiteness): | acorr(τ) | ≤ tol_resid for τ ∈ { 1..τ_max }.
• C70-1204 (Particle degeneracy): ESS / N ≥ ρ_min (suggest ρ_min = 0.5); resample below threshold.
• C70-1205 (Dual-form gate): delta_form_assim_p95 ≤ tol_assim (suggest tol_assim = 5 • ( atol + rtol • || x̂ || )).
• C70-1206 (Units & conservation): check_dim(r_k) = unit(y) passes; if conservation is declared, | 1^T x̂_{k|k} − 1^T x̂_{k|k−1} | ≤ tol_cons.
• C70-1207 (Topology consistency): filtering L/A must match the runtime model version or publication is rejected.

VII. Implementation Bindings I70-12*

• I70-121 kf_predict_update(A, B, Q, H, R, u, y, x̂, P) -> { x̂', P', S, r, K }
• I70-122 ukf_predict_update(f, h, Q, R, u, y, x̂, P, ukf_cfg) -> { x̂', P', S, r }
• I70-123 pf_step(transition, likelihood, u, y, Particles, Resampler) -> { Particles', ESS }
• I70-124 rts_smoother(A, Q, seq{ x̂, P }) -> { x̂_s, P_s }
• I70-125 project_physical(x̂, constraints) -> x̂_proj (nonnegativity / conservation / bounds)
• I70-126 multi_sensor_update(H_list, R_list, y_list, x̂, P, mode) -> { x̂', P' }
• I70-127 adaptive_qr_tuning(resid_stats, method) -> { Q', R' } (EM / innovation matching)
• I70-128 ms_bridge(R, P, x̂_c, P_c, dir) -> { x̂_f / P_f or x̂_c / P_c }
• I70-129 assert_filter_contracts(state, stats, rules) -> report
• I70-12A emit_filter_manifest(results, policy) -> manifest.stg.filter

Invariants: P ≽ 0; non_decreasing(time); traceable RefCond / method / hash; abnormal conditions trigger fallbacks.

VIII. Cross-References

• Graph operators & kernels: Ch. 4 (for A = exp( − κ Δt L ) and convolutions).
• Numerical integration & stability: Ch. 9 (advancers and events for UKF/PF).
• Causality & intervention: Ch. 10 (robust filtering under do(•)).
• Multiscale & coarsening: Ch. 11 (R, P bridges and cross-scale filtering).
• Cleaning & robustness: reuse cleaning rules from the TopologyAtlas and PathCorrection volumes.

IX. Quality & Risk Control

1. SLIs/SLOs: nis_p95, resid_white_rate, ESS_p10, delta_form_assim_p95, latency_p95, runtime_per_step, drop_rate.
2. Fallbacks
   • Consistency failure: increase Q or decrease R (innovation matching), enable covariance inflation.
   • Particle degeneracy: systematic/residual resampling, clustered particles, or RBPF.
   • Numerical instability: switch to stiffness-stable integration or reduce Δt.
   • Observation anomalies: gate by Mahalanobis distance and downweight.
   • Topology drift: online low-rank correction of L or revert to last passing version.
3. Audit: persist NIS traces, residual autocorrelations, ESS curves, delta_form_assim, Q/R changes, and panel snapshots.

Summary
By tightly integrating KF / UKF / PF with graph operators, this chapter defines a closed loop from modeling → assimilation → validation → publication. With C70-12xx contracts, the dual-form indicator delta_form_assim, and manifest.stg.filter.*, assimilation in networked dynamical systems becomes statistically consistent, physically feasible, operationally robust, and auditable.