Source-linked AI summary
Wasserstein Distributionally Robust Kalman Filtering
Soroosh Shafieezadeh-Abadeh, Viet Anh Nguyen, Daniel Kuhn, Peyman Mohajerin Esfahani
TL;DR
The classical Kalman filter depends on an accurate state-space model, while the joint distribution of signals and observations is uncertain. This paper uses Wasserstein ambiguity sets to formulate robust estimation and derives a tractable convex reformulation and Frank-Wolfe algorithm. It also introduces a Wasserstein distributionally robust Kalman filter to hedge against model risk.
Problem
Method
The paper models distributional uncertainty with Wasserstein ambiguity sets and reformulates normal-distribution robust estimation as a tractable convex program, solved with a Frank-Wolfe method.
Source: §2 · pp. 2–3, §1 · p. 2Results
Takeaways & Limitations
The resulting Wasserstein distributionally robust Kalman filter hedges against model risk and can be computed by solving a sequence of robust estimation problems.
Source: §1 · p. 2For Wasserstein ambiguity sets that may contain non-normal distributions, the minimax result holds when estimators are restricted to be affine.
Source: §2 · p. 4
Abstract
from arXiv · showhide
We study a distributionally robust mean square error estimation problem over a nonconvex Wasserstein ambiguity set containing only normal distributions. We show that the optimal estimator and the least favorable distribution form a Nash equilibrium. Despite the non-convex nature of the ambiguity set, we prove that the estimation problem is equivalent to a tractable convex program. We further devise a Frank-Wolfe algorithm for this convex program whose direction-searching subproblem can be solved in a quasi-closed form. Using these ingredients, we introduce a distributionally robust Kalman filter that hedges against model risk.
1 Introduction
The classical Kalman filter depends on an accurate state-space model, making it susceptible to model risk; existing robust approaches address uncertainty in different ways. The paper proposes Wasserstein ambiguity sets for distributionally robust estimation and introduces a Kalman-type filter to hedge against model risk.
1 Introduction
- The classical Kalman filter relies on an accurate state-space model and is therefore susceptible to model risk.The filter is widely used for online tracking and estimating dynamical-system states from indirect observations.Source: §1 · p. 1
- Prior robust filters address uncertain noise statistics or model uncertainty, but some can lose transient performance or become over-conservative.The H∞ filter may diverge absent restrictive positivity conditions, while set-based methods ignore distributional information and other robust filters may be too conservative under small uncertainties.Source: §1 · p. 1
- Wasserstein ambiguity sets around a nominal model are proposed to represent uncertainty about the joint state-output distribution and the level of trust in that model.The paper motivates this choice with the Wasserstein distance’s applications in machine learning and its reported statistical robustness relative to other information divergences.Source: §1 · p. 2
- The paper introduces a distributionally robust mean square estimation problem over a nonconvex Wasserstein ambiguity set containing only normal distributions, and a Kalman filter that hedges against model risk.The optimal estimator and least favorable distribution form a Nash equilibrium; the filter is computed by solving robust estimation problems with the proposed Frank-Wolfe algorithm.Source: §1 · p. 2
2 Robust Estimation with Wasserstein Ambiguity Sets
The section models uncertainty in the joint signal–observation distribution with a Wasserstein ambiguity set around a nominal normal distribution, then minimizes worst-case mean square error. It establishes a minimax solution and a tractable convex reformulation, yielding an affine robust estimator and a least favorable prior whose behavior depends on the ambiguity radius.
2 Robust Estimation with Wasserstein Ambiguity Sets
- The minimax estimator and least favorable prior form a saddle point, so the robust estimator is also Bayesian under that prior.The minimax theorem permits interchanging the infimum and supremum without changing the optimal value.Source: §2 · p. 3
- The Wasserstein minimax problem is equivalent to a finite tractable convex program, despite the ambiguity set being nonconvex.The solution recovers both the optimal estimator and the least favorable prior.Source: §2 · p. 3
- The optimal estimator is affine in the observation, and its associated least favorable prior is normal.The estimator uses the least favorable covariance blocks and means; the prior has covariance S*.Source: §2 · p. 3
- At ρ = 0, the least favorable covariance equals the nominal covariance and the estimator reduces to the nominal Bayesian estimator.The section notes that changing ρ can significantly affect the Wasserstein estimator.Source: §2 · p. 3
- Unlike Wasserstein ambiguity, τ-divergence ambiguity leaves the nominal Bayesian estimator unaffected by ρ.KL divergence is included as a special case of τ-divergences.Source: §2 · p. 4, Figure 1 · p. 4
- The minimax result and convex reformulation also hold for Wasserstein sets containing possibly non-normal distributions, provided estimators are restricted to affine functions.The distribution set consists of distributions with finite second moments around a nominal normal distribution.Source: §2 · p. 4
3 Efficient Frank-Wolfe Algorithm
The section develops a Frank-Wolfe method for the nonlinear SDP, using an efficient direction-finding routine and a step-size rule with convergence guarantees. Its direction subproblem is solved by bisection.
3 Efficient Frank-Wolfe Algorithm
- The Frank-Wolfe method solves the nonlinear SDP (5) directly, avoiding the potentially unreliable general-purpose solvers for large-scale linear SDP reformulations.The method uses linear approximations of the objective and avoids a projection step to recover feasibility.Source: §3 · pp. 4–5
- The paper motivates Frank-Wolfe by showing that the objective function has unit total elasticity, like every linear function.The algorithm starts at S(0) = Σ and iteratively minimizes a linearized objective over the original feasible set.Source: §3 · p. 5
- The algorithm’s direction-finding subproblem is handled by an efficient bisection procedure, with Algorithm 1 returning a feasible ε-suboptimal solution.Repeated matrix inversions are its most expensive operation; diagonalizing D once can accelerate them.Source: §3 · p. 5
- The method uses a step-size rule inspired by and a bounded curvature argument to establish rigorous convergence guarantees.Theorem 3.3 states feasibility and an optimality bound for iterates under its stated assumptions.Source: §3 · p. 5
4 The Wasserstein Distributionally Robust Kalman Filter
The filter recursively constructs a conditional Gaussian nominal model and robustifies each measurement update over a Wasserstein ambiguity set. The radius expresses distrust in the pseudo-nominal estimate, and the update reduces to the classical Kalman update as the radius approaches zero.
4 The Wasserstein Distributionally Robust Kalman Filter
- The filter estimates the state from output history under an unknown Gaussian state-output law near a nominal law determined by the linear state-space model.The state evolves with Gaussian white noise independent of the initial state.Source: §4 · p. 6
- At each time step, it forms a pseudo-nominal conditional Gaussian model, observes the output, and solves a finite convex program for the robust update.The update yields a least-favorable conditional distribution, from which the state estimate and covariance follow.Source: §4 · p. 7
- The Wasserstein radius ρ_t quantifies distrust in the pseudo-nominal a priori estimate and serves as a measure of model uncertainty.The resulting robust update reduces to the classical Kalman update as ρ decreases to zero.Source: §4 · p. 7
5 Numerical Results
Synthetic experiments assess the robust MMSE estimator and Frank-Wolfe algorithm, then compare the Wasserstein robust Kalman filter with classical and KL-robust filters. The reported advantages depend on the uncertainty setting: robust MMSE improves consistently, while the filter’s gains are clearest under large uncertainty.
5.1 Distributionally Robust Minimum Mean Square Error Estimation
- The robust MMSE estimator performs better than the Bayesian MMSE estimator across all experiments, with a more pronounced effect at larger dimensions.Figure 3 depicts the error differences against the ideal MMSE estimator under the true distribution.Source: Figure 3 · p. 8, §5.1 · p. 8
- The first experiment predicts a d-dimensional Gaussian signal-observation vector for d ∈ {10, 50, 100}, using 10^4 simulation runs.The robust estimator uses radius ρ = d and is compared with Bayesian estimators under nominal and true distributions.Source: §5.1 · p. 8
- Execution time grows polynomially due to matrix inversion in the bisection algorithm; Figure 4(c) plots the current solution’s relative duality gap against iteration count, and the stopping threshold is 0.01%.Source: §5.1 · p. 8
5.2 Wasserstein Distributionally Robust Kalman Filtering
- The Wasserstein robust Kalman filter significantly outperforms the classical filter under large uncertainty and, to a lesser extent, the KL robust filter, while showing the best transient behavior.Under small time-invariant uncertainty, both robust filters outperform the classical filter; under small time-varying uncertainty, their performance is similar.Source: Figure 5 · p. 9, §5.2 · p. 9
- The Kalman-filter experiment compares filters over four combinations of time-invariant or time-varying uncertainty and small or large uncertainty magnitude.Reported results use the minimum steady-state error across candidate radii.Source: §5.2 · pp. 8–9
A.1 Proof of Theorem 2.3
The proof establishes the tractable reformulation by bounding the minimax problem from both sides. It restricts estimators to affine functions and uses duality and minimax arguments to show that the bounds coincide.
A.1 Proof of Theorem 2.3
- For each fixed Gaussian distribution, the conditional expectation is affine, so the proof restricts the estimator class to affine functions without loss.This yields a lower bound on the minimax problem, while restricting to affine estimators supplies an upper bound.Source: §A.1 · p. 10
- The proof encodes each normal distribution by its mean and covariance, then reformulates the Wasserstein constraint using duality and auxiliary variables.Strong duality is supported by the positive-definite covariance matrix as a Slater point.Source: §A.1 · pp. 10–11
- Minimax interchanges and analytical inner solutions reduce the reformulation to (A.3), which supplies both bounds and proves equality.The inner maximization over the mean is solved by c⋆ = μ in the final reduction.Source: §A.1 · pp. 10–11
A.2 Proof of Theorem 2.5
The proof reduces the estimation problem to a maximization over covariance matrices by analytically minimizing over the estimator. The resulting least favorable prior is Gaussian, and the corresponding estimator is unique and optimal.
A.2 Proof of Theorem 2.5
- The unique analytic minimizer over G follows from the first-order condition for the unconstrained quadratic problem.The positive lower bound on S ensures the quadratic problem has a unique solution.Source: §A.2 · p. 12
- Substituting G⋆ into (A.6) yields the maximization problem (5), equivalent to nature’s decision problem in (4).The least favorable prior is Q⋆ = Nd(µ, S⋆).Source: §A.2 · p. 12
- The Bayesian estimator is unique because S⋆⪰¯σId makes the objective strictly convex, and it is optimal for the original problem.The proof invokes Theorem 2.3 and [7, Section 5.5.5].Source: §A.2 · p. 12
A.3 Proof of Theorem 3.2
The proof characterizes the covariance optimizer using a scalar root γ⋆. Bisection over a bounded interval yields a feasible, ε-suboptimal solution to the covariance maximization problem.
A.3 Proof of Theorem 3.2
- The bisection interval bounds the unique root γ⋆ of h(γ) = 0, with λ1 the largest eigenvalue of D = ∇f(S).v1 is a corresponding eigenvector.Source: §A.3 · p. 13
- L(γ⋆) is optimal in (7b) when γ⋆Id ≻ D and h(γ⋆) = 0.For γId ≻ D and h(γ) > 0, L(γ) is feasible.Source: §A.3 · p. 13
- Bisection approximates γ⋆ with γ such that L(γ) is feasible and ε-suboptimal in (7b).The search is restricted to [γmin, γmax], which contains γ⋆.Source: §A.3 · p. 13
A.4 Proof of Theorem 3.3
The proof establishes a curvature bound for the convex objective over the feasible set and uses it to obtain the Frank–Wolfe convergence rate. It also gives a closed-form root in a special case.
A.4 Proof of Theorem 3.3
- In the special case considered, γ⋆ has a closed-form solution, so bisection is unnecessary.The general root is otherwise computed approximately by bisection.Source: §A.4 · p. 14
- C−f ≤ 2¯σ4/¯σ3 bounds the curvature of the negative objective over the feasible set.The proof bounds curvature using the gradient’s Lipschitz constant and the feasible-set diameter.Source: §A.4 · pp. 14–15
- The bounded curvature constant permits applying [13, Theorem 1] to obtain the Frank–Wolfe convergence rate.The feasible set is bounded by S ⪯ ¯σId.Source: §A.4 · pp. 13, 15
Appendix B Sequential versus Static Estimation
The sequential filtering approach outperforms a static estimator built from the entire observation history, even when the static method uses the oracle-optimal ambiguity radius. The authors suggest that sequential robustification may limit uncertainty propagation through the dynamics.
Appendix B Sequential versus Static Estimation
- At t = 100, static estimation error is 37.5 dB versus 24.5 dB for sequential estimation, despite the static method’s oracle-optimal radius.For static estimation, the optimal radius is ρ = 0 whenever t ≥ 5; sequential robustification always helps.Source: Appendix B · p. 16
- The authors suggest static uncertainty propagation through the dynamics may make global robust estimation ineffective, while stagewise robustification appears to limit it.This is offered as a possible explanation for the observed sequential advantage.Source: Appendix B · p. 16