betaFeedback

WorksMathematics

Set-based State Estimation for Unknown Dynamical Systems from Noisy Output Data with Probabilistic Guarantees

Abstract

We develop a methodology for set-based state estimation from noisy input-output trajectories, without a predefined model structure for the unknown state dynamics or access to training state measurements. We derive a bound on the state set diameter that depends on the sensor map and leverage it as a surrogate to formulate a tractable linear program balancing state set tightness against output trajectory coverage. Combining this certificate with deterministic or probabilistically certified measurement noise sets and leveraging the results from scenario optimization with relaxation, we provide joint a posteriori probabilistic guarantees for state inclusion and state set diameter. Numerical simulations corroborate our developed theoretical guarantees.

Introduction

State estimation aims to reconstruct the unmeasured states of dynamical systems from available input and output measurements. Conventional approaches rely on model knowledge and include observer design Luenberger [14]; Bernard et al. [4], probabilistic filtering Arulampalam et al. [3]; Särkkä and Svensson [21], and set-based estimation, which characterizes uncertainty through admissible state sets Bertsekas and Rhodes [5]; Milanese and Vicino [15]. Despite advances in zonotopic set representations and stochastic/set-membership filtering Scott et al. [22]; Rego et al. [19]; de Paula et al. [7]; Combastel [6], a fundamental challenge remains: ensuring inclusion of the true state, either deterministically under given uncertainty bounds or with high probability if data-driven methods are employed, while maintaining sufficiently tight estimated sets. Achieving both objectives is particularly challenging when the dynamics are unknown and only noisy input-output data are available.

A promising method for set-based estimation with unknown dynamics is data-driven reachability analysis, which constructs reachable set over-approximations in the state space from input-state data Alanwar et al. [1]; Zhang et al. [24] or performs set-based state estimation from noisy input-output data Alanwar et al. [2]. However, these guarantees require structural assumptions on the dynamics, such as linearity or predefined nonlinear terms, together with known noise bounds. Such reachability analysis methods additionally require training using full state measurements. Probabilistic methods quantify the reliability of data-driven reachable sets through scenario optimization Devonport and Arcak [8]; Dietrich et al. [10]; Rickard et al. [20]; Pantazis and Chong [17], Christoffel functions Devonport et al. [9], and ellipsoidal approximations Park et al. [18]. Other approaches provide probabilistic guarantees based on the holdout method Dietrich et al. [11] or conformal inference Tebjou et al. [23]; Hashemi et al. [13]; Nath et al. [16]. Without a predefined model structure for the unknown state dynamics, or training state measurements, constructing tight state sets only from noisy input-output trajectories remains challenging. Specifically, the states remain unmeasured during training, and output coverage alone does not certify both state inclusion and a tight state set size. In this paper, we address this challenge assuming a known linear sensing map and either deterministic noise bounds or a specified noise distribution with possibly unbounded support. Our contributions are as follows:

  1. We develop a methodology that learns rectangular output sets as functions of the input history from sampled input-output trajectories. We derive a bound on the diameter of the corresponding state sets and use its parameter-dependent term as a surrogate in a linear program designed to learn the output sets, which directly balances state set tightness against output trajectory coverage. We then construct the state sets by taking the inverse image of the learned output sets, simultaneously accounting for deterministic or probabilistic measurement noise bounds. Unlike Pantazis and Chong [17], the formulation requires no state trajectories for training.

  1. We establish a posteriori probabilistic guarantees that the estimated state sets simultaneously contain the true states and satisfy the learned diameter bounds over the entire horizon. Specifically, since output inclusion alone does not ensure satisfaction of the learned diameter thresholds, we include both conditions in the appropriateness criterion and establish the consistency required to apply the results of Garatti and Campi [12], thus avoiding the need to impose a nondegeneracy assumption. The resulting distribution-free certificate depends on the complexity of the learned solution. Combining this certificate with deterministic or probabilistically certified measurement noise sets, we provide explicit bounds on the probability of violating either state inclusion or the state set diameter bounds. Learning and certification use the same input-output trajectories, without the need of a separate calibration set.

Notation: A⊕B:={a+b:a∈A,b∈B}A \oplus B := \{a+b : a \in A, b \in B\}, −B:={−b:b∈B}-B := \{-b : b \in B\}, and h−1(B):={x∈X:h(x)∈B}h^{-1}(B) := \{x \in\mathcal{X} : h(x) \in B\}, diam⁡(B):=sup⁡x,z∈B∥x−z∥2\operatorname{diam}(B) := \sup_{x,z \in B} \lVert x-z\rVert_2 for nonempty BB. The nullspace of CC is ker⁡C:={q∈Rnx:Cq=0}\ker C := \{q \in\mathbb{R}^{n_x} : Cq = 0\}. For i=1,…,nyi=1,\ldots,n_y, let ei∈Rnye_i \in\mathbb{R}^{n_y} denote the ii-th standard basis vector, whose ii-th entry is one and all other entries are zero. Let T:={0,…,T}\mathcal{T} := \{0,\ldots,T\} and T−:={0,…,T−1}\mathcal{T}_{-} := \{0,\ldots,T-1\} denote the time horizon index sets and consider the sensor index set S:={1,…,S}\mathcal{S} := \{1,\ldots,S\}. The operator col⁡\operatorname{col} denotes the vertical concatenation of elements in a vector. For a sequence z(k)∈Rdz(k) \in\mathbb{R}^{d} and integers a≤ba \le b, define za:b:=col⁡(z(a),…,z(b))∈R(b−a+1)dz_{a:b} := \operatorname{col}(z(a),\ldots,z(b)) \in\mathbb{R}^{(b-a+1)d}, where the indices run in increasing order from aa to bb. We finally define the nonnegative integers as Z≥0\mathbb{Z}_{\ge0}. The indicator 1A\mathbf{1}_A equals one if condition AA holds and zero otherwise.

Problem Formulation

Consider the system with the following state and output dynamics:

x(k+1)=f(x(k),u(k),w(k)),k∈T−(1)x(k+1)=f(x(k),u(k),w(k)), \qquad k \in\mathcal{T}_{-} \tag*{(1)}
y(s)(k)=hs(x(k))+v(s)(k),s∈S, k∈T.(2)y^{(s)}(k)=h_s(x(k))+v^{(s)}(k), \qquad s \in\mathcal{S},\ k \in\mathcal{T}. \tag*{(2)}

The state x(k)∈X⊆Rnxx(k) \in\mathcal{X} \subseteq\mathbb{R}^{n_x} evolves according to the unknown dynamics f:X×U×W→Xf:\mathcal{X}\times\mathcal{U}\times\mathcal{W}\to\mathcal{X}, where u(k)∈U⊆Rnuu(k) \in\mathcal{U} \subseteq\mathbb{R}^{n_u} is the known input and w(k)∈W⊆Rnww(k) \in\mathcal{W} \subseteq\mathbb{R}^{n_w} is the unknown process disturbance. In our setting, neither the state trajectory x0:Tx_{0:T} nor the disturbance w0:T−1w_{0:T-1} are accessible. The state domain X\mathcal{X} is known, and can possibly be the entire Rnx\mathbb{R}^{n_x}, whereas W\mathcal{W} need not be known. Note that neither set is assumed to be bounded. For each sensor s∈Ss \in\mathcal{S}, the sensor map is hs:X→Rnsh_s:\mathcal{X}\to\mathbb{R}^{n_s}, and the measured output y(s)(k)∈Rnsy^{(s)}(k) \in\mathbb{R}^{n_s} satisfies (2) where v(s)(k)∈Rnsv^{(s)}(k) \in\mathbb{R}^{n_s} denotes the measurement noise for sensor ss. For each k∈Tk \in\mathcal{T}, we thus define the concatenated output, measurement noise, and sensing map by y(k):=col⁡(y(1)(k),…,y(S)(k))y(k) := \operatorname{col}(y^{(1)}(k), \ldots, y^{(S)}(k)), v(k):=col⁡(v(1)(k),…,v(S)(k))v(k) := \operatorname{col}(v^{(1)}(k), \ldots, v^{(S)}(k)), h(x):=col⁡(h1(x),…,hS(x))h(x) := \operatorname{col}(h_1(x), \ldots, h_S(x)), respectively, where ny:=∑s=1Snsn_y := \sum_{s=1}^{S} n_s. Thus, we have that y(k),v(k)∈Rnyy(k),v(k) \in\mathbb{R}^{n_y} and h:X→Rnyh:\mathcal{X}\to\mathbb{R}^{n_y}, and the sensor dynamics can be written in the compact form y(k)=h(x(k))+v(k)y(k)=h(x(k))+v(k). We now impose the following assumption:

Assumption 1 For every sensor s∈Ss \in\mathcal{S}, the sensor map is given by the linear transformation hs(x)=Csxh_s(x)=C_sx, where the matrix Cs∈Rns×nxC_s \in\mathbb{R}^{n_s\times n_x} is known.

Let C:=col⁡(C1,…,CS)∈Rny×nxC := \operatorname{col}(C_1,\ldots,C_S) \in\mathbb{R}^{n_y\times n_x} denote the concatenated sensor matrix, so that h(x)=Cxh(x)=Cx. Writing u:=u0:T−1u := u_{0:T-1} and y:=y0:Ty := y_{0:T}, we collect the input and corresponding output trajectory into a single vector ζ=(u,y)\zeta=(u,y), which we refer to as a trajectory sample or simply sample. A collection of such samples is called a multi-sample. We now impose the following assumption:

Assumption 2 The trajectories in the multi-sample DN=(ζ(1),…,ζ(N))D_N=(\zeta^{(1)},\ldots,\zeta^{(N)}) are independent and identically distributed according to a possibly unknown probability distribution P0\mathbb{P}_0. A new trajectory pair ζ=(u,y)\zeta=(u,y) is also independent from the multi-sample DND_N and follows the same probability distribution P0\mathbb{P}_0, i.e., it holds that (ζ(1),…,ζ(N),ζ)∼∏i=1N+1P0(\zeta^{(1)},\ldots,\zeta^{(N)},\zeta)\sim\prod_{i=1}^{N+1}\mathbb{P}_0.

Assumption 2 permits dependence across time, sensors, inputs, and outputs within each trajectory. We further impose the following measurability assumption.

Assumption 3 The sets X\mathcal{X}, U\mathcal{U}, and W\mathcal{W} are Borel subsets of their respective Euclidean spaces. The dynamics f:X×U×W→Xf:\mathcal{X}\times\mathcal{U}\times\mathcal{W}\to\mathcal{X} and sensor maps hs:X→Rnsh_s:\mathcal{X}\to\mathbb{R}^{n_s}, s∈Ss\in\mathcal{S}, are Borel measurable. Furthermore, we consider Borel measurable feedback control policies of the form u(k)=πk(y0:k,u0:k−1)u(k)=\pi_k(y_{0:k},u_{0:k-1}), with k∈T−k\in\mathcal{T}_{-} and u0:−1=∅u_{0:-1}=\varnothing.

Assumption 2 holds for both open-loop and feedback experiments under identical training and deployment conditions. Let E=(x0,w0:T−1,v0:T)∼PEE=(x_0,w_{0:T-1},v_{0:T})\sim\mathbb{P}_E and suppose the dynamics, sensor maps, horizon, uncertainty distribution, and input mechanism are fixed across experiments. Under Assumption 3, either mechanism induces a measurable trajectory map Φ\Phi such that ζ=Φ(E)\zeta=\Phi(E). Hence, i.i.d. uncertainty realizations induce i.i.d. input-output trajectories with distribution P0(A)=PE(Φ−1(A))\mathbb{P}_0(A)=\mathbb{P}_E(\Phi^{-1}(A)) for every Borel set AA in the input-output trajectory space.

For the measurement noise, we assume either known deterministic bounds or a specified distribution Pv\mathbb{P}_v that the noise trajectory v0:Tv_{0:T} follows. Note that Pv\mathbb{P}_v is the marginal distribution of v0:Tv_{0:T} under the probability distribution PE\mathbb{P}_E. In the latter case, we generate NvN_v independent synthetic trajectories from Pv\mathbb{P}_v, collected in the multi-sample Dv=(v0:T(1),…,v0:T(Nv))D_v=(v_{0:T}^{(1)},\ldots,v_{0:T}^{(N_v)}), to construct the noise sets Vk(Dv)\mathcal{V}_k(D_v). The distribution of DvD_v is given by the cartesian product PDv:=∏i=1NvPv\mathbb{P}_{D_v}:=\prod_{i=1}^{N_v}\mathbb{P}_v. Thus, separate noise measurements during system operation are not required. Let us now define the probability of exclusion for a new yet unseen noise measurement Vv(Dv):=Pv{v0:T:∃k∈T, v(k)∉Vk(Dv)}\mathbb{V}_v(D_v):=\mathbb{P}_v\{v_{0:T}:\exists k\in\mathcal{T},\ v(k)\notin\mathcal{V}_k(D_v)\}. We then impose the following assumption:

Assumption 4 For any k∈Tk\in\mathcal{T}, the mapping Dv↦Vk(Dv)D_v\mapsto\mathcal{V}_k(D_v) is measurable and the returned set Vk(Dv)\mathcal{V}_k(D_v) is nonempty and compact. For a confidence parameter βv∈[0,1)\beta_v\in[0,1), there exists a violation level ϵv(Dv,βv)∈[0,1]\epsilon_v(D_v,\beta_v)\in[0,1] such that PDv{Dv:Vv(Dv)≤ϵv(Dv,βv)}≥1−βv\mathbb{P}_{D_v}\{D_v:\mathbb{V}_v(D_v)\leq\epsilon_v(D_v,\beta_v)\}\geq1-\beta_v.

For known deterministic noise bounds, it holds by construction that Dv=∅D_v=\varnothing and ϵv=βv=0\epsilon_v=\beta_v=0. For example, using the synthetic trajectories v0:T(j)v_{0:T}^{(j)}, let M:=max⁡jmax⁡k∥v(j)(k)∥∞M:=\max_j\max_k\|v^{(j)}(k)\|_\infty and Vk(Dv):=\mathcal{V}_k(D_v):= {v∈Rny:∥v∥∞≤M}\{v \in\mathbb{R}^{n_y}: \|v\|_{\infty} \le M\}. If Z:=max⁡k∈T∥v(k)∥∞Z := \max_{k \in\mathcal{T}} \|v(k)\|_{\infty} has a continuous distribution FZF_Z, then it holds that Vv(Dv)=1−FZ(M)V_v(D_v) = 1 - F_Z(M). We then define Zj:=max⁡k∈T∥v(j)(k)∥∞Z_j := \max_{k \in\mathcal{T}} \|v^{(j)}(k)\|_{\infty} such that M=max⁡1≤j≤NvZjM = \max_{1 \le j \le N_v} Z_j. For ϵ∈(0,1)\epsilon\in(0,1), define the quantile qϵ:=inf⁡{z∈R:FZ(z)≥1−ϵ}q_{\epsilon} := \inf\{z \in\mathbb{R}: F_Z(z) \ge1 - \epsilon\}. Continuity of FZF_Z then gives P{Zj<qϵ}=1−ϵ\mathbb{P}\{Z_j < q_{\epsilon}\} = 1 - \epsilon. Moreover, Vv(Dv)>ϵV_v(D_v) > \epsilon is equivalent to M<qϵM < q_{\epsilon}, meaning that every sampled maximum ZjZ_j lies below qϵq_{\epsilon}. Assuming independence of the events,

PDv{Vv(Dv)>ϵ}=PDv{Zj<qϵ for all j=1,…,Nv}=∏j=1NvP{Zj<qϵ}=(1−ϵ)Nv.\mathbb{P}_{D_v}\{V_v(D_v) > \epsilon\} = \mathbb{P}_{D_v}\{Z_j < q_{\epsilon}\text{ for all }j = 1,\ldots,N_v\} = \prod_{j=1}^{N_v}\mathbb{P}\{Z_j < q_{\epsilon}\} = (1-\epsilon)^{N_v}.

Choosing ϵv(Dv,βv)=1−βv1/Nv\epsilon_v(D_v,\beta_v) = 1-\beta_v^{1/N_v} gives PDv{Vv(Dv)≤ϵv(Dv,βv)}=1−(1−ϵv(Dv,βv))Nv=1−βv\mathbb{P}_{D_v}\{V_v(D_v) \le\epsilon_v(D_v,\beta_v)\} = 1-(1-\epsilon_v(D_v,\beta_v))^{N_v} = 1-\beta_v, which establishes Assumption 4.

Characterizing the estimated set of states under unknown dynamics

For each time k∈Tk \in\mathcal{T}, let Y^k(u;θ)⊆Rny\widehat{\mathcal{Y}}_k(u;\theta) \subseteq\mathbb{R}^{n_y} denote an estimated output set depending on the input history u0:k−1u_{0:k-1} and parameterized by the parameters θ∈Θ\theta\in\Theta. Using the measurement noise sets Vk(Dv)\mathcal{V}_k(D_v) introduced in Section 2, we construct the estimated state set:

X^k(u;θ,Dv):=h−1(Y^k(u;θ)⊕(−Vk(Dv)))={x∈X:∃v∈Vk(Dv), Cx+v∈Y^k(u;θ)}.(3)\widehat{\mathcal{X}}_k(u;\theta,D_v) := h^{-1}\left(\widehat{\mathcal{Y}}_k(u;\theta) \oplus(-\mathcal{V}_k(D_v))\right) = \{x \in\mathcal{X}: \exists v \in\mathcal{V}_k(D_v),\ Cx+v \in\widehat{\mathcal{Y}}_k(u;\theta)\}. \tag*{(3)}

The set X^k(u;θ,Dv)\widehat{\mathcal{X}}_k(u;\theta,D_v) contains states consistent with the estimated output set and admissible measurement noise. We consider output and noise sets which can be written as a Cartesian product of sets over sensors, i.e., Y^k=∏s∈SY^k,s\widehat{\mathcal{Y}}_k = \prod_{s \in\mathcal{S}}\widehat{\mathcal{Y}}_{k,s} and Vk=∏s∈SVk,s\mathcal{V}_k = \prod_{s \in\mathcal{S}}\mathcal{V}_{k,s}, which yields the state set:

X^k(u;θ,Dv)=⋂s∈S{x∈X:∃vs∈Vk,s(Dv), Csx+vs∈Y^k,s(u;θ)},(4)\widehat{\mathcal{X}}_k(u;\theta,D_v) = \bigcap_{s \in\mathcal{S}}\{x \in\mathcal{X}: \exists v_s \in\mathcal{V}_{k,s}(D_v),\ C_sx+v_s \in\widehat{\mathcal{Y}}_{k,s}(u;\theta)\}, \tag*{(4)}

where the noise vector vv in (3) denotes the compact form v=col⁡(v1,…,vS)∈Vkv = \operatorname{col}(v_1,\ldots,v_S) \in\mathcal{V}_k. The Cartesian product structure of these sets does not require statistical independence across sensors. Let ϕk:Uk→Rqk\phi_k:\mathcal{U}^k \to\mathbb{R}^{q_k} and ψk:Uk→R≥0rk\psi_k:\mathcal{U}^k \to\mathbb{R}_{\ge0}^{r_k} be feature maps used to parameterize the center and half-width of the estimated output boxes as follows:

ck(u;θ):=Akϕk(u0:k−1)+bk,ak(u;θ):=ak0+Γkψk(u0:k−1),Y^k(u;θ):={z∈Rny:∣zi−ck,i(u;θ)∣≤ak,i(u;θ), i=1,…,ny}.(5)\begin{aligned} c_k(u;\theta) &:= A_k\phi_k(u_{0:k-1}) + b_k,\qquad a_k(u;\theta) := a_k^0 + \Gamma_k\psi_k(u_{0:k-1}),\\ \widehat{\mathcal{Y}}_k(u;\theta) &:= \{z \in\mathbb{R}^{n_y}: |z_i-c_{k,i}(u;\theta)| \le a_{k,i}(u;\theta),\ i=1,\ldots,n_y\}. \tag*{(5)} \end{aligned}

Here, ck,i(u;θ)c_{k,i}(u;\theta) and ak,i(u;θ)a_{k,i}(u;\theta) denote the ii-th components of ck(u;θ)c_k(u;\theta) and ak(u;θ)a_k(u;\theta), respectively. The feature maps ϕk\phi_k and ψk\psi_k are assumed to be Borel measurable. The parameter vector θ\theta collects (Ak,bk,ak0,Γk)k∈T(A_k,b_k,a_k^0,\Gamma_k)_{k\in\mathcal{T}}, where Ak∈Rny×qkA_k \in\mathbb{R}^{n_y \times q_k}, bk,ak0∈Rnyb_k,a_k^0 \in\mathbb{R}^{n_y}, and Γk∈Rny×rk\Gamma_k \in\mathbb{R}^{n_y \times r_k}. The admissible parameter domain is Θ:={θ:ak0≥0, Γk≥0, ∀k∈T}\Theta:= \{\theta:a_k^0 \ge0,\ \Gamma_k \ge0,\ \forall k \in\mathcal{T}\}. Since ψk≥0\psi_k \ge0, the half-widths remain nonnegative. These linear constraints define a deterministic convex parameter domain. For inputs u(t)∈Rnuu(t) \in\mathbb{R}^{n_u}, a simple choice for the feature maps is ϕk(u0:k−1)=col⁡(u(0),…,u(k−1))\phi_k(u_{0:k-1}) = \operatorname{col}(u(0),\ldots,u(k-1)), and ψk(u0:k−1)=col⁡(∣u(0)∣,…,∣u(k−1)∣)\psi_k(u_{0:k-1}) = \operatorname{col}(|u(0)|,\ldots,|u(k-1)|). For k≥1k \ge1, the feature dimensions are qk=rk=knuq_k=r_k=kn_u. At k=0k=0, we set q0=r0=1q_0=r_0=1 and ϕ0(∅)=ψ0(∅)=0\phi_0(\varnothing)=\psi_0(\varnothing)=0, so that c0=b0c_0=b_0 and a0=a00a_0=a_0^0.

We now characterize the challenge induced by the sensing map. Specifically, for a state x∈Xx \in\mathcal{X}, let us define the measurement equivalent class as FC(x):={z∈X:Cz=Cx}={x+q:q∈Rnx, Cq=0, x+q∈X}\mathcal{F}_C(x) := \{z \in\mathcal{X}: Cz=Cx\} = \{x+q:q \in\mathbb{R}^{n_x},\ Cq=0,\ x+q \in\mathcal{X}\}. Note that states xˉ∈FC(x)\bar{x} \in\mathcal{F}_C(x) produce identical noiseless measurements and therefore cannot be distinguished using the sensing map alone. The following result characterizes the consequences of this challenge for set-based state estimation.

Proposition 1. Let X^k(u;θ,Dv)\widehat{\mathcal{X}}_k(u;\theta,D_v) be the estimated state set. Then, for every x∈X^k(u;θ,Dv)x \in\widehat{\mathcal{X}}_k(u;\theta,D_v), it holds that FC(x)⊆X^k(u;θ,Dv)\mathcal{F}_C(x) \subseteq\widehat{\mathcal{X}}_k(u;\theta,D_v). If, in particular, it holds that X=Rnx\mathcal{X} = \mathbb{R}^{n_x}, ker⁡C≠{0}\ker C \ne\{0\}, and X^k(u;θ,Dv)≠∅\widehat{\mathcal{X}}_k(u;\theta,D_v) \ne\varnothing, then diam⁡(X^k(u;θ,Dv))=+∞\operatorname{diam}(\widehat{\mathcal{X}}_k(u;\theta,D_v)) = +\infty.

Proof. Let x∈X^k(u;θ,Dv)x \in\widehat{\mathcal{X}}_k(u;\theta,D_v), which implies that there exists v∈Vk(Dv)v \in\mathcal{V}_k(D_v) such that Cx+v∈Y^k(u;θ)Cx+v \in\widehat{\mathcal{Y}}_k(u;\theta). For any z∈FC(x)z \in\mathcal{F}_C(x), it holds that Cz=CxCz=Cx, and thus Cz+v∈Y^k(u;θ)Cz+v \in\widehat{\mathcal{Y}}_k(u;\theta), which in turn implies that z∈X^k(u;θ,Dv)z \in\widehat{\mathcal{X}}_k(u;\theta,D_v). If X=Rnx\mathcal{X} = \mathbb{R}^{n_x} and ker⁡C≠{0}\ker C \ne\{0\}, let us choose q∈ker⁡C∖{0}q \in\ker C \setminus\{0\}. Then for every t∈Rt \in\mathbb{R}, it holds that C(x+tq)=CxC(x+tq)=Cx, so that x+tq∈X^k(u;θ,Dv)x+tq \in\widehat{\mathcal{X}}_k(u;\theta,D_v), i.e., X^k(u;θ,Dv)\widehat{\mathcal{X}}_k(u;\theta,D_v) is unbounded.

Due to Proposition 1, we impose the following assumption:

Assumption 5. The rank of CC is equal to the dimension of the state vector, i.e., rank⁡(C)=nx\operatorname{rank}(C)=n_x.

Assumption 5 ensures that distinct states produce distinct noiseless outputs. Combined with bounded output and measurement noise sets it guarantees finite state set diameter bounds without knowing a model of the state dynamics in (1). Let C†=(CTC)−1CTC^{\dagger}=(C^{\mathsf{T}}C)^{-1}C^{\mathsf{T}}, such that C†C=IC^{\dagger}C=I holds. For a nonempty bounded Vk\mathcal{V}_k, let us define ωi:=∥C†ei∥2\omega_i:=\lVert C^{\dagger}e_i\rVert_2 and bv,k:=sup⁡v1,v2∈Vk∥C†(v1−v2)∥2b_{v,k}:=\sup_{v_1,v_2\in\mathcal{V}_k}\lVert C^{\dagger}(v_1-v_2)\rVert_2.

Proposition 2. For any input uu and θ∈Θ\theta\in\Theta such that X^k(u;θ,Dv)\widehat{\mathcal{X}}_k(u;\theta,D_v) is nonempty, it holds that

diam⁡(X^k(u;θ,Dv))≤2∑i=1nyωiak,i(u;θ)+bv,k(Dv).\operatorname{diam}(\widehat{\mathcal{X}}_k(u;\theta,D_v)) \le2\sum_{i=1}^{n_y}\omega_i a_{k,i}(u;\theta)+b_{v,k}(D_v).

Proof. Let x1,x2∈X^k(u;θ,Dv)x_1,x_2 \in\widehat{\mathcal{X}}_k(u;\theta,D_v). By construction, there exist z1,z2∈Y^k(u;θ)z_1,z_2 \in\widehat{\mathcal{Y}}_k(u;\theta) and v1,v2∈Vk(Dv)v_1,v_2 \in\mathcal{V}_k(D_v) such that Cxℓ=zℓ−vℓCx_\ell=z_\ell-v_\ell for ℓ=1,2\ell=1,2. Since C†C=IC^{\dagger}C=I,

∥x1−x2∥2≤∑i=1ny∥C†ei∥2∣z1,i−z2,i∣+∥C†(v1−v2)∥2≤2∑i=1nyωiak,i(u;θ)+bv,k(Dv).\lVert x_1-x_2\rVert_2 \le\sum_{i=1}^{n_y}\lVert C^{\dagger}e_i\rVert_2\lvert z_{1,i}-z_{2,i}\rvert+\lVert C^{\dagger}(v_1-v_2)\rVert_2 \le2\sum_{i=1}^{n_y}\omega_i a_{k,i}(u;\theta)+b_{v,k}(D_v).

The last inequality follows from ∣z1,i−z2,i∣≤2ak,i(u;θ)\lvert z_{1,i}-z_{2,i}\rvert\le2a_{k,i}(u;\theta). Taking the supremum over all pairs x1,x2x_1,x_2 concludes the proof.

Proposition 2 establishes an upper bound on the diameter of the state set as a function of the half-widths of the estimated output set and the geometry of the sensor matrix CC. The coefficients ωi=∥C†ei∥2\omega_i=\lVert C^{\dagger}e_i\rVert_2 quantify the contribution of uncertainty in each output coordinate to the state set diameter. We have now established the core ingredients for quantifying the estimated state sets under unknown dynamics, which we will use to provide probabilistic guarantees that these sets contain the true state of the system in (1).

Set-based State Estimation via Scenario Optimization with Relaxation

Proposition 2 establishes an upper bound on the diameter of the estimated state sets in terms of the size of the output set and the sensor matrix CC. To obtain a computationally tractable learning formulation, we introduce the diameter surrogate dk(u;θ):=2∑i=1nyωiak,i(u;θ)d_k(u;\theta):=2\sum_{i=1}^{n_y}\omega_i a_{k,i}(u;\theta). Since bv,k(Dv)b_{v,k}(D_v) is independent of the learning parameters θ\theta, we minimize dk(u;θ)d_k(u;\theta) to reduce the parameter-dependent upper bound on the estimated state set diameter. Let yi(k)∈Ry_i(k) \in\mathbb{R} denote the ii-th component of the concatenated output y(k)∈Rnyy(k) \in\mathbb{R}^{n_y} for i=1,…,nyi=1,\ldots,n_y. To quantify output set violations at the trajectory level, we define the uncertain function g(ζ,θ):=max⁡k∈T, 1≤i≤ny{∣yi(k)−ck,i(u;θ)∣−ak,i(u;θ)}g(\zeta,\theta) := \max_{k\in\mathcal{T},\,1\le i\le n_y}\{|y_i(k)-c_{k,i}(u;\theta)|-a_{k,i}(u;\theta)\}. Note that the constraint g(ζ,θ)≤0g(\zeta,\theta)\le0 is equivalent to output inclusion at every time step. To accommodate trajectories that may violate the estimated output sets, we introduce a nonnegative relaxation variable ξj\xi_j for each training trajectory. Denoting the sample index set N:={1,…,N}\mathcal{N}:=\{1,\ldots,N\}, for a fixed penalty ρ>0\rho>0, we solve the scenario program

min⁡θ∈Θ, ξ≥0∑k∈Tmax⁡j∈Ndk(u(j);θ)+ρ∑j∈Nξj,subject tog(ζ(j),θ)≤ξj,j∈N.\begin{aligned} \min_{\theta\in\Theta,\,\xi\ge0}\quad&\sum_{k\in\mathcal{T}}\max_{j\in\mathcal{N}}d_k(u^{(j)};\theta)+\rho\sum_{j\in\mathcal{N}}\xi_j,\\ \text{subject to}\quad&g(\zeta^{(j)},\theta)\le\xi_j,\quad j\in\mathcal{N}. \end{aligned}

The cost balances the worst-case diameter surrogate over the samples ζ(j)\zeta^{(j)}, with j∈Nj\in\mathcal{N}, at each time k∈Tk\in\mathcal{T} against output relaxation for each trajectory. Introducing the epigraphic variables τ=(τk)k∈T∈R≥0T+1\tau=(\tau_k)_{k\in\mathcal{T}}\in\mathbb{R}_{\ge0}^{T+1} we obtain the following epigraphic reformulation which is a linear program (LP) due to the geometry of the output set.

min⁡θ∈Θ, τ≥0, ξ≥0∑k∈Tτk+ρ∑j∈Nξj,subject to∣yi(j)(k)−ck,i(u(j);θ)∣≤ak,i(u(j);θ)+ξj,dk(u(j);θ)≤τk,j∈N, k∈T, i=1,…,ny.(6)\begin{aligned} \min_{\theta\in\Theta,\,\tau\ge0,\,\xi\ge0}\quad&\sum_{k\in\mathcal{T}}\tau_k+\rho\sum_{j\in\mathcal{N}}\xi_j,\\ \text{subject to}\quad&|y_i^{(j)}(k)-c_{k,i}(u^{(j)};\theta)|\le a_{k,i}(u^{(j)};\theta)+\xi_j,\\ &d_k(u^{(j)};\theta)\le\tau_k,\quad j\in\mathcal{N},\ k\in\mathcal{T},\ i=1,\ldots,n_y. \tag*{(6)} \end{aligned}

Note that the epigraph constraints on dkd_k are hard constraints, while constraints corresponding to the inclusion of output trajectories are relaxed through the variables ξj\xi_j. For fixed training inputs, (6) is linear in the decision variables and feasible for every finite multi-sample DND_N. To obtain a unique optimizer, we select the minimum-norm solution among all optimizers of (6), by minimizing ∥(θ,τ,ξ)∥22\|(\theta,\tau,\xi)\|_2^2 over the optimal set of (6). The corresponding optimal epigraph cost and relaxation variables then satisfy τN,k∗=max⁡j∈Ndk(u(j);θN∗)\tau^*_{N,k}=\max_{j\in\mathcal{N}}d_k(u^{(j)};\theta^*_N), ξN,j∗=max⁡(g(ζ(j),θN∗),0)\xi^*_{N,j}=\max(g(\zeta^{(j)},\theta^*_N),0), respectively. For every k∈Tk\in\mathcal{T}, the estimated state set is obtained by evaluating (3) for θ=θN∗\theta=\theta^*_N, namely,

X^k(u;θN∗,Dν):={x∈X:∃v∈Vk(Dν), Cx+v∈Y^k(u;θN∗)}.(7)\widehat{\mathcal{X}}_k(u;\theta^*_N,D_\nu):=\{x\in\mathcal{X}:\exists v\in\mathcal{V}_k(D_\nu),\ Cx+v\in\widehat{\mathcal{Y}}_k(u;\theta^*_N)\}. \tag*{(7)}

In particular, for box-shaped noise sets Vk(Dν)={v:∣v∣≤νk(Dν)}\mathcal{V}_k(D_\nu)=\{v:|v|\le\nu_k(D_\nu)\}, this reduces to X^k(u;θN∗,Dν)={x∈X:∣Cx−ck(u;θN∗)∣≤ak(u;θN∗)+νk(Dν)}\widehat{\mathcal{X}}_k(u;\theta^*_N,D_\nu)=\{x\in\mathcal{X}:|Cx-c_k(u;\theta^*_N)|\le a_k(u;\theta^*_N)+\nu_k(D_\nu)\}. Here, absolute values and inequalities are understood componentwise.

Probabilistic Certificates for Set-based State Estimation

We first seek distribution-free probabilistic guarantees that a new trajectory satisfies both output inclusion and the learned diameter thresholds. We achieve this using the scenario optimization framework of Garatti and Campi [12]. First, we show that their Theorem 4 applies to problem (6) by verifying the consistency conditions in their Property 1. Let Ξ:=UT×R(T+1)ny\Xi:=\mathcal{U}^{T}\times\mathbb{R}^{(T+1)n_y} be the space of input-output trajectories and define the decision domain Z:=Θ×R≥0T+1×Z≥0\mathcal{Z}:=\Theta\times\mathbb{R}_{\ge0}^{T+1}\times\mathbb{Z}_{\ge0}.

Definition 3 (Adapted from Garatti and Campi [12]) For a fixed penalty ρ>0\rho>0, consider for each m≥1m\ge1 an ordered multi-sample Sm=(ζ(1),…,ζ(m))∈Ξm\mathcal{S}_m=(\zeta^{(1)},\ldots,\zeta^{(m)})\in\Xi^m. Let (θm∗,τm∗,ξm∗)(\theta^*_m,\tau^*_m,\xi^*_m) be the minimum-norm optimizer of (6) when only these mm samples are used. Let rm:=∑j=1m1{g(ζ(j),θm∗)>0}r_m:=\sum_{j=1}^m\mathbf{1}_{\{g(\zeta^{(j)},\theta^*_m)>0\}} denote

the number of sampled trajectories that violate output inclusion. The decision map Mm:Ξm→ZM_m : \Xi^m \to\mathcal{Z} is defined by

Mm(ζm):=(θm⋆,τm⋆,rm).(8)M_m(\zeta_m) := (\theta_m^\star, \tau_m^\star, r_m). \tag*{(8)}

For the empty multi-sample, define M0(∅):=(0,0,0)M_0(\varnothing) := (0,0,0), corresponding to the minimum-norm solution of (6) with no sample constraints and an empty slack vector. For each trajectory ζ=(u,y)∈Ξ\zeta=(u,y)\in\Xi, the appropriateness set is given by

Aζ:={(θ,τ,r)∈Z:g(ζ,θ)≤0, dk(u;θ)≤τk for every k∈T}.(9)A_\zeta:= \{(\theta,\tau,r)\in\mathcal{Z}:g(\zeta,\theta)\leq0,\ d_k(u;\theta)\leq\tau_k\ \text{for every }k\in\mathcal{T}\}. \tag*{(9)}

The coordinate rr represents the number of training trajectories that violate output inclusion. A decision z∈Zz\in\mathcal{Z} is appropriate for ζ\zeta if z∈Aζz\in A_\zeta. □

Evaluating Mm(ζm)M_m(\zeta_m) means solving (6) on these mm trajectories and returning the learned parameters, diameter surrogate thresholds, and number of training trajectories which violate the output set. A decision belongs to AζA_\zeta if output inclusion holds without relaxation and all diameter surrogate thresholds are satisfied. For a subset I⊆NI\subseteq\mathcal{N}, let DID_I be the sublist of DND_N indexed by II, in increasing order, and write zI:=(θI⋆,τI⋆,rI):=M∣I∣(DI)z_I := (\theta_I^\star,\tau_I^\star,r_I):=M_{|I|}(D_I). Thus, rIr_I counts the trajectories in DID_I that violate output inclusion, and zN:=(θN⋆,τN⋆,rN)=MN(DN)z_N := (\theta_N^\star,\tau_N^\star,r_N)=M_N(D_N).

Lemma 4 For every m≥0m\geq0, n≥1n\geq1, and ζm+n∈Ξm+n\zeta_{m+n}\in\Xi^{m+n}, write zm:=Mm(ζm)z_m:=M_m(\zeta_m) and zm+n:=Mm+n(ζm+n)z_{m+n}:=M_{m+n}(\zeta_{m+n}), where ζm\zeta_m contains the first mm trajectories. The maps satisfy the three conditions of Garatti and Campi, [12]: (i) Mm(ζ(π(1)),…,ζ(π(m)))=zmM_m(\zeta^{(\pi(1))},\ldots,\zeta^{(\pi(m))})=z_m for every permutation π\pi of {1,…,m}\{1,\ldots,m\}, (ii) zm∈⋂j=m+1m+nAζ(j)z_m\in\bigcap_{j=m+1}^{m+n}A_{\zeta^{(j)}} implies that zm+n=zmz_{m+n}=z_m and (iii) zm∉⋂j=m+1m+nAζ(j)z_m\notin\bigcap_{j=m+1}^{m+n}A_{\zeta^{(j)}} implies that zm+n≠zmz_{m+n}\ne z_m.

Proof (i) Permuting samples does not change the value of the map leaving the decision unchanged. (ii) Let Jℓ⋆J_\ell^\star denote the optimal value of (6) with ℓ\ell trajectories. Since every added trajectory is appropriate, (θm⋆,τm⋆,ξm⋆,0n)(\theta_m^\star,\tau_m^\star,\xi_m^\star,0_n) is feasible with m+nm+n trajectories, i.e., Jm+n⋆≤Jm⋆J_{m+n}^\star\leq J_m^\star. Conversely, any feasible (θ,τ,ξ)(\theta,\tau,\xi) for these m+nm+n trajectories yields a feasible (θ,τ,ξ1:m)(\theta,\tau,\xi_{1:m}) for the original problem. Its objective is therefore at least Jm⋆+ρ∑j=m+1m+nξj≥Jm⋆J_m^\star+\rho\sum_{j=m+1}^{m+n}\xi_j\geq J_m^\star, which implies that Jm+n⋆=Jm⋆J_{m+n}^\star=J_m^\star. Since ρ>0\rho>0, every optimizer has zero added slacks and restricts to an original optimizer. Appending zeros preserves the norm, so the minimum-norm rule selects (θm⋆,τm⋆,ξm⋆,0n)(\theta_m^\star,\tau_m^\star,\xi_m^\star,0_n). The added trajectories contribute no violations, i.e., zm+n=zmz_{m+n}=z_m. (iii) If an added diameter constraint fails at (θm⋆,τm⋆)(\theta_m^\star,\tau_m^\star), this pair becomes infeasible and must change, otherwise, some added trajectory has g(ζ(j),θm⋆)>0g(\zeta^{(j)},\theta_m^\star)>0. If the selected pair stays unchanged, then rm+n=rm+∑j=m+1m+n1{g(ζ(j),θm⋆)>0}>rmr_{m+n}=r_m+\sum_{j=m+1}^{m+n}\mathbf{1}_{\{g(\zeta^{(j)},\theta_m^\star)>0\}}>r_m. Thus it holds that zm+n≠zmz_{m+n}\ne z_m. ■

Output coverage and size certification

Let us define the complexity SN:=min⁡{∣I∣:I+⊆I⊆N,θI⋆=θN⋆,τI⋆=τN⋆}S_N:=\min\{|I|:I_+\subseteq I\subseteq\mathcal{N},\theta_I^\star=\theta_N^\star,\tau_I^\star=\tau_N^\star\}, where I+:={j∈N:g(ζ(j),θN⋆)>0}I_+:=\{j\in\mathcal{N}:g(\zeta^{(j)},\theta_N^\star)>0\}. The requirement I+⊆II_+\subseteq I ensures that whenever the selected parameters and diameter thresholds are reconstructed, the count of violations from the original scenario program with all trajectories in place is also preserved. Thus, the subset II reconstructs the decision zN=MN(DN)z_N=M_N(D_N), obtained when all samples are considered. For a new input/output trajectory ζ=(u,y)\zeta=(u,y) from P0\mathbb{P}_0, we define the following probabilities:

V~(DN):=P0{ζ:g(ζ,θN⋆)>0 or ∃k∈T:dk(u;θN⋆)>τN,k⋆},\widetilde{V}(D_N) := \mathbb{P}_0\left\{\zeta:g(\zeta,\theta_N^\star)>0\ \text{or}\ \exists k\in\mathcal{T}:d_k(u;\theta_N^\star)>\tau_{N,k}^\star\right\},
Vy(DN):=P0{ζ:g(ζ,θN⋆)>0}.V_y(D_N) := \mathbb{P}_0\left\{\zeta:g(\zeta,\theta_N^\star)>0\right\}.

The function Vy(DN)V_y(D_N) is the probability that for some time k∈Tk\in\mathcal{T}, a new yet unseen output measurement does not belong in the estimated output set Y^k(u;θN⋆)\widehat{\mathcal{Y}}_k(u;\theta_N^\star). The function V~(DN)\widetilde{V}(D_N) is the probability that either output inclusion fails or the diameter surrogate exceeds the threshold obtained by the scenario program in (6), at some time step for a new yet unseen realization ζ=(u,y)∼P0\zeta=(u,y)\sim\mathbb{P}_0. Consequently, it holds that Vy(DN)≤V~(DN)V_y(D_N)\leq\widetilde{V}(D_N). For β∈(0,1)\beta\in(0,1) and q∈{0,…,N−1}q\in\{0,\ldots,N-1\}, let tqt_q be the unique root in (0,1)(0,1) of the following polynomial in tt:

(Nq)tN−q−βN∑m=qN−1(mq)tm−q=0.(10)\binom{N}{q}t^{N-q}-\frac{\beta}{N}\sum_{m=q}^{N-1}\binom{m}{q}t^{m-q}=0. \tag*{(10)}

Let P0N:=∏i∈NP0\mathbb{P}_0^N:=\prod_{i\in\mathbb{N}}\mathbb{P}_0 denote the distribution of DND_N. The following result then holds:

Proposition 5 Suppose Assumption 2 holds and the maps Mm:Ξm→ZM_m:\Xi^m\to\mathcal{Z} are Borel measurable for every m≥0m\geq0. Let sNs_N be the complexity defined above. For β∈(0,1)\beta\in(0,1), define ϵN(q,β):=1−tq\epsilon_N(q,\beta):=1-t_q for q∈{0,…,N−1}q\in\{0,\ldots,N-1\}, where tq∈(0,1)t_q\in(0,1) is the unique root of (10), and set ϵN(N,β):=1\epsilon_N(N,\beta):=1. Then, it holds that

P0N{DN:V~(DN)≤ϵN(sN,β)}≥1−β.(11)\mathbb{P}_0^N\left\{D_N:\widetilde{V}(D_N)\leq\epsilon_N(s_N,\beta)\right\}\geq1-\beta. \tag*{(11)}

Proof. By Lemma 4, the maps MmM_m satisfy (Garatti and Campi, [12]). The result follows from (Garatti and Campi, [12]).

Since ϵN(q,β)\epsilon_N(q,\beta) is nondecreasing in qq (Garatti and Campi, [12]), any measurable, integer-valued upper bound s^N\widehat{s}_N satisfying sN≤s^N≤Ns_N\leq\widehat{s}_N\leq N yields a valid certificate. Such a bound can be obtained by sequentially removing trajectories outside I+I_+, retaining a removal only if resolving (6) with the same penalty and tie-break rule preserves (θN⋆,τN⋆)(\theta_N^\star,\tau_N^\star). The cardinality of the remaining subset then provides s^N\widehat{s}_N.

Probabilistic Guarantees for State Inclusion and Set Tightness

We remind the reader that the variable E=(x0,w0:T−1,v0:T)∼PEE=(x_0,w_{0:T-1},v_{0:T})\sim\mathbb{P}_E collects the uncertainties affecting the system in (1)-(2), whose corresponding input-output probability distribution is P0\mathbb{P}_0. Each realization of EE induces a state, process and measurement noise trajectory under the considered input. For notational simplicity, with a slight abuse of notation, we write x(k)=x(k;E)x(k)=x(k;E), y(k)=y(k;E)y(k)=y(k;E), and u=u(E)u=u(E), with the dependence on the uncertainty realization EE to be implied. Let PD\mathbb{P}_D denote the joint distribution of the multi-sample D=(DN,Dv)D=(D_N,D_v). For any such multi-sample, we define the state trajectory exclusion probability

Vx(D):=PE{E:∃k∈T, x(k)∉X^k(u;θN⋆,Dv)}.V_x(D):=\mathbb{P}_E\left\{E:\exists k\in\mathcal{T},\ x(k)\notin\widehat{\mathcal{X}}_k(u;\theta_N^\star,D_v)\right\}.

The function Vx(D)V_x(D) is the probability that a new state trajectory violates the estimated sets at some time k∈Tk\in\mathcal{T}. The following result provides a bound on this probability.

Proposition 6 For any DD, it holds that Vx(D)≤Vy(DN)+Vv(Dv)≤V~(DN)+Vv(Dv)\mathbb{V}_{x}(D) \leq\mathbb{V}_{y}(D_{N}) + \mathbb{V}_{v}(D_{v}) \leq\widetilde{\mathbb{V}}(D_{N}) + \mathbb{V}_{v}(D_{v}).

Proof. Note that if y(k)∈Y^k(u;θN⋆)y(k) \in\widehat{\mathcal{Y}}_{k}(u;\theta_{N}^{\star}) and v(k)∈Vk(Dv)v(k) \in\mathcal{V}_{k}(D_{v}), then x(k)∈X^k(u;θN⋆,Dv)x(k) \in\widehat{\mathcal{X}}_{k}(u;\theta_{N}^{\star},D_{v}). Hence, by the subadditivity property of the union of two events,

Vx(D)≤PE{E:∃k∈T, y(k)∉Y^k(u;θN⋆)}+PE{E:∃k∈T, v(k)∉Vk(Dv)}=Vy(DN)+Vv(Dv)≤V~(DN)+Vv(Dv).\begin{aligned} \mathbb{V}_{x}(D) \leq\mathbb{P}_{E}\left\{E : \exists k \in\mathcal{T},\ y(k) \notin\widehat{\mathcal{Y}}_{k}(u;\theta_{N}^{\star})\right\} + \mathbb{P}_{E}\left\{E : \exists k \in\mathcal{T},\ v(k) \notin\mathcal{V}_{k}(D_{v})\right\} \\ &= \mathbb{V}_{y}(D_{N}) + \mathbb{V}_{v}(D_{v}) \leq\widetilde{\mathbb{V}}(D_{N}) + \mathbb{V}_{v}(D_{v}). \end{aligned}

The last inequality follows from Vy(DN)≤V~(DN)\mathbb{V}_{y}(D_{N}) \leq\widetilde{\mathbb{V}}(D_{N}), which concludes the proof.

For each time step k∈Tk \in\mathcal{T}, we define the threshold Bk(D):=τN,k⋆+bv,k(Dv)B_{k}(D) := \tau_{N,k}^{\star} + b_{v,k}(D_{v}). Let us now define the probability of violation for joint state coverage and tightness of the state set as follows:

Vcs(D):=PE{E:∃k∈T:x(k)∉X^k(u;θN⋆,Dv) or diam⁡(X^k(u;θN⋆,Dv))>Bk(D)}.\mathbb{V}_{\mathrm{cs}}(D) := \mathbb{P}_{E}\left\{E : \exists k \in\mathcal{T} : x(k) \notin\widehat{\mathcal{X}}_{k}(u;\theta_{N}^{\star},D_{v}) \ \text{or}\ \operatorname{diam}\left(\widehat{\mathcal{X}}_{k}(u;\theta_{N}^{\star},D_{v})\right) > B_{k}(D)\right\}.

Unlike Vx(D)\mathbb{V}_{x}(D), which measures only state trajectory exclusion, Vcs(D)\mathbb{V}_{\mathrm{cs}}(D) also accounts for violations of the obtained diameter threshold. For example, a set may contain the true state while exceeding the allowed diameter, i.e, state inclusion guarantees alone do not ensure satisfaction of diameter bounds.

Theorem 7 Under Assumptions 1-5, let the maps Mm:Ξm→ZM_{m} : \Xi^{m} \to\mathcal{Z} be Borel measurable for every m≥0m \geq0. Let ϵN\epsilon_{N} be defined in Proposition 5, and ϵv(Dv,βv)\epsilon_{v}(D_{v},\beta_{v}) as in Assumption 4. Then, for any βy∈(0,1−βv)\beta_{y} \in(0,1-\beta_{v}) and complexity bound s^N\widehat{s}_{N} satisfying sN≤s^N≤Ns_{N} \leq\widehat{s}_{N} \leq N, it holds that

PD{D:Vcs(D)≤ϵN(s^N,βy)+ϵv(Dv,βv)}≥1−βy−βv.(12)\mathbb{P}_{D}\left\{D : \mathbb{V}_{\mathrm{cs}}(D) \leq\epsilon_{N}(\widehat{s}_{N},\beta_{y}) + \epsilon_{v}(D_{v},\beta_{v})\right\} \geq1-\beta_{y}-\beta_{v}. \tag*{(12)}

Proof. Fix DD and consider a realization EE for which output and noise inclusion and the diameter surrogate threshold holds for all k∈Tk \in\mathcal{T}. By construction, we then have that x(k)∈X^k(u;θN⋆,Dv)x(k) \in\widehat{\mathcal{X}}_{k}(u;\theta_{N}^{\star},D_{v}). Moreover, by Proposition 2, it holds that diam⁡X^k(u;θN⋆,Dv)≤dk(u;θN⋆)+bv,k(Dv)≤τN,k⋆+bv,k(Dv)=Bk(D)\operatorname{diam}\widehat{\mathcal{X}}_{k}(u;\theta_{N}^{\star},D_{v}) \leq d_{k}(u;\theta_{N}^{\star}) + b_{v,k}(D_{v}) \leq\tau_{N,k}^{\star} + b_{v,k}(D_{v}) = B_{k}(D). Consequently, we have that Vcs(D)≤V~(DN)+Vv(Dv)\mathbb{V}_{\mathrm{cs}}(D) \leq\widetilde{\mathbb{V}}(D_{N}) + \mathbb{V}_{v}(D_{v}). The result follows from (11), Assumption 4, and the subadditivity property.

Theorem 7 thus provides a finite-sample probabilistic certificate for simultaneous state inclusion and satisfaction of the learned diameter bounds throughout the horizon.

Numerical Simulations

We consider a two-dimensional unknown nonlinear system with state dynamics xk+1=Axk−0.9Bϕtanh⁡(x1,k)+Buuk+wkx_{k+1} = Ax_{k} - 0.9B_{\phi}\tanh(x_{1,k}) + B_{u}u_{k} + w_{k}, and output dynamics yk=Cxk+vky_{k} = Cx_{k} + v_{k}, with A=[0.950.10−0.200.85]A = \begin{bmatrix} 0.95 & 0.10 \\ -0.20 & 0.85 \end{bmatrix}, Bϕ=(0.18,0.06)TB_{\phi} = (0.18, 0.06)^{\mathsf{T}}, Bu=(0.15,0.24)TB_{u} = (0.15, 0.24)^{\mathsf{T}}, and C=diag⁡(1,0.14)C = \operatorname{diag}(1,0.14). Initial states are randomly chosen from a uniform distribution on [−0.6,0.6]×[−0.45,0.45][-0.6,0.6] \times[-0.45,0.45]. The measurement noise is independent and uniform on the support set V=[−0.10,0.10]×[−0.014,0.014]\mathcal{V} = [-0.10,0.10] \times[-0.014,0.014]. The input is given by the noisy output feedback law uk=sat⁡[−0.65,0.65](0.58uk−1−(0.42,16/7)yk)u_{k} = \operatorname{sat}_{[-0.65,0.65]}(0.58u_{k-1} - (0.42,16/7)y_{k}) and u−1=0u_{-1} = 0. Conditional on the input uku_{k}, the Gaussian process noise components have standard deviations σw,1(uk)=0.037+ηwmax⁡{uk,0}\sigma_{w,1}(u_{k}) = 0.037 + \eta_{w}\max\{u_{k},0\} and σw,2(uk)=0.037+ηwmax⁡{−uk,0}\sigma_{w,2}(u_{k}) = 0.037 + \eta_{w}\max\{-u_{k},0\}, where ηw≥0\eta_{w} \geq0 controls their input dependence. We then consider χ0=0\chi_{0} = 0 and χk+1=0.8χk+uk\chi_{k+1} = 0.8\chi_{k} + u_{k}. The centers of the output box are affine in χk\chi_k, while their nonnegative half-widths are affine in [χk]+[\chi_k]_+ and [−χk]+[-\chi_k]_+, where [a]+:=max⁡{a,0}[a]_+ := \max\{a,0\}. We then solve the scenario program in (6) with dk(u;θ)=2ak,1(u;θ)+2ak,2(u;θ)0.14d_k(u;\theta) = 2a_{k,1}(u;\theta) + \frac{2a_{k,2}(u;\theta)}{0.14} and bv=20.02b_v = 2\sqrt{0.02}, which yields dˉk=dk+bv\bar{d}_k = d_k + b_v (see Proposition 2). For X=R2\mathcal{X} = \mathbb{R}^2, the exact state set diameter, used only for evaluation, is diam⁡(X^k)=2(ak,1+0.10)2+((ak,2+0.014)/0.14)2\operatorname{diam}(\widehat{\mathcal{X}}_k) = 2\sqrt{(a_{k,1}+0.10)^2 + ((a_{k,2}+0.014)/0.14)^2}.

We use T=15T = 15, βy=10−4\beta_y = 10^{-4}, and the known noise set V\mathcal{V}, i.e., ϵv=βv=0\epsilon_v = \beta_v = 0. Empirical violations are evaluated on M=2500M = 2500 independent test trajectories per repetition, over 15 independent repetitions. Specifically, the quantities V^cs\widehat{V}_{cs} and V^\widehat{V} denote the empirical counterparts of the probabilities VcsV_{cs} and VV, respectively. State observations are used only for evaluation, not training. The results in Figure 1 indicate improved generalization to new unseen states with increasing number of training trajectories, as empirical violations decrease and probabilistic bounds become less conservative. For fixed ρ\rho, increasing NN also increases the weight on average relaxation relative to the diameter objective. Moreover, the relaxation penalty tunes the trade-off between state coverage and state set tightness. Finally, the decreasing mean state set diameter under weaker disturbances suggests that the attenuation of initial uncertainty dominates the accumulation of process noise, whereas stronger disturbances prevent such narrowing.

Figure 1. (a) Empirical violations V^cs\widehat{V}_{cs}, V^\widehat{V} and bound ϵ‾N(s^N,βy)\overline{\epsilon}_N(\widehat{s}_N,\beta_y) averaged over 15 repetitions for N∈{500,1000,2000}N \in\{500,1000,2000\}, ρ=5\rho= 5 and ηw=1\eta_w = 1. Shaded regions indicate the min/max range across the 15 independent repetitions. (b) State set diameter and bound dˉk:=dk+bv\bar{d}_k := d_k + b_v, both averaged over time steps, test trajectories, and 15 independent repetitions, for ρ∈{3,5,10}\rho\in\{3,5,10\}, N=1000N = 1000, and ηw=1\eta_w = 1. (c) Evolution of the mean actual and surrogate state set diameters for ηw∈{0.3,0.5,1}\eta_w \in\{0.3,0.5,1\}, with N=2000N = 2000 and ρ=5\rho= 5. Solid and dashed lines represent the actual and surrogate diameters, respectively, while shaded regions indicate the min–max range across 15 independent repetitions.

Concluding Remarks

We developed a data-driven framework for set-based state estimation from noisy input and output trajectories without identifying the unknown dynamics or requiring state measurements. We derived diameter bounds based on sensing geometry and formulated a tractable relaxed linear program. Leveraging the results in scenario optimization, we established a posteriori probabilistic guarantees for state inclusion and satisfaction of diameter bounds. Future work will investigate nonlinear sensing maps and extensions to secure set-based state estimation.

Acknowledgments

During the preparation of this work, the authors used ChatGPT to improve readability, assist with grammar and phrasing, and support code development. The authors reviewed and edited the text and code as needed and take full responsibility for the content of the publication.

References

  1. [1]Amr Alanwar, Anne Koch, Frank Allgöwer, and Karl Henrik Johansson. Data-driven reachability analysis using matrix zonotopes. Proceedings of the 3rd Conference on Learning for Dynamics and Control, 144:163–175, 07 – 08 June 2021.
  2. [2]Amr Alanwar, Alexander Berndt, Karl Henrik Johansson, and Henrik Sandberg. Data-driven set-based estimation using matrix zonotopes with set containment guarantees. 2022 European Control Conference (ECC), pages 875–881, 2022.arxiv.org/abs/2101.10784
  3. [3]M.S. Arulampalam, S. Maskell, N. Gordon, and T. Clapp. A tutorial on particle filters for online nonlinear/non-Gaussian Bayesian tracking. IEEE Transactions on Signal Processing, 50(2):174–188, 2002.DOI
  4. [4]Pauline Bernard, Vincent Andrieu, and Daniele Astolfi. Observer design for continuous-time dynamical systems. Annual Reviews in Control, 53:224–248, 2022. ISSN 1367-5788.
  5. [5]D. Bertsekas and I. Rhodes. Recursive state estimation for a set-membership description of uncertainty. IEEE Transactions on Automatic Control, 16(2):117–128, 1971.DOI
  6. [6]Christophe Combastel. An extended zonotopic and Gaussian Kalman filter (EZGKF) merging set-membership and stochastic paradigms: Toward non-linear filtering and fault detection. Annu. Rev. Control., 42:232–243, 2016.DOI
  7. [7]Alesi A. de Paula, Guilherme V. Raffo, and Bruno O.S. Teixeira. Zonotopic filtering for uncertain nonlinear systems: Fundamentals, implementation aspects, and extensions [applications of control]. IEEE Control Systems Magazine, 42(1):19–51, 2022. doi: 10.1109/MCS.2021.3122311.DOI
  8. [8]Alex Devonport and Murat Arcak. Estimating reachable sets with scenario optimization. Proceedings of the 2nd Conference on Learning for Dynamics and Control, 120:75–84, 10–11 Jun 2020.
  9. [9]Alex Devonport, Forest Yang, Laurent El Ghaoui, and Murat Arcak. Data-driven reachability and support estimation with Christoffel functions. IEEE Transactions on Automatic Control, 68(9):5216–5229, 2023. doi: 10.1109/TAC.2023.3281749.DOI
  10. [10]Elizabeth Dietrich, Alex Devonport, and Murat Arcak. Nonconvex scenario optimization for data-driven reachability. Proceedings of the 6th Annual Learning for Dynamics & Control Conference, 242:514–527, 15–17 Jul 2024.
  11. [11]Elizabeth Dietrich, Rosalyn Devonport, Stephen Tu, and Murat Arcak. Data-driven reachability with scenario optimization and the holdout method. 2025 IEEE 64th Conference on Decision and Control (CDC), pages 3925–3931, 2025.arxiv.org/abs/2504.06541
  12. [12]Simone Garatti and Marco C. Campi. Non-convex scenario optimization. Mathematical Programming, 209:557–608, 2025. doi: 10.1007/s10107-024-02074-3.DOI
  13. [13]Navid Hashemi, Xin Qin, Lars Lindemann, and Jyotirmoy V. Deshmukh. Data-driven reachability analysis of stochastic dynamical systems with conformal inference. 2023 62nd IEEE Conference on Decision and Control (CDC), pages 3102–3109, 2023.arxiv.org/abs/2309.09187
  14. [14]D. Luenberger. An introduction to observers. IEEE Transactions on Automatic Control, 16(6):596–602, 1971.
  15. [15]Mario Milanese and Antonio Vicino. Optimal estimation theory for dynamic systems with set membership uncertainty: An overview. Automatica, 27(6):997–1009, 1991. ISSN 0005-1098.
  16. [16]Devesh Nath, Haoran Yin, and Glen Chou. Scalable data-driven reachability analysis and control via Koopman operators with conformal coverage guarantees. Proceedings of The 8th Annual Learning for Dynamics and Control Conference, 331:71–97, 17–19 Jun 2026.arxiv.org/abs/2601.01076
  17. [17]Georgios Pantazis and Michelle S. Chong. Data-driven reachable set estimation with tunable adversarial and Wasserstein distributional guarantees. In Proceedings of the IEEE Conference on Decision and Control (CDC), 2026. To appear.arxiv.org/abs/2604.12654
  18. [18]Hyunsang Park, Vishnu Vijay, and Inseok Hwang. Data-driven reachability analysis for nonlinear systems. IEEE Control Systems Letters, 8:2661–2666, 2024.DOI
  19. [19]Brenner S. Rego, Joseph K. Scott, Davide M. Raimondo, and Guilherme V. Raffo. Set-valued state estimation of nonlinear discrete-time systems with nonlinear invariants based on constrained zonotopes. Automatica, 129:109638, 2021. ISSN 0005-1098.DOI
  20. [20]Luke Rickard, Alessandro Abate, and Kostas Margellos. Data-driven certificate synthesis. Automatica, 185:112798, 2026. ISSN 0005-1098.arxiv.org/abs/2502.05510
  21. [21]Simo Särkkä and Lennart Svensson. Bayesian filtering and smoothing. Cambridge University Press, 2023.
  22. [22]Joseph K. Scott, Davide M. Raimondo, Giuseppe Roberto Marseglia, and Richard D. Braatz. Constrained zonotopes: A new tool for set-based estimation and fault detection. Automatica, 69:126–136, 2016. ISSN 0005-1098.DOI
  23. [23]Abdelmouaiz Tebjou, Goran Frehse, and Faïcel Chamroukhi. Data-driven reachability using Christoffel functions and conformal prediction. Proceedings of the Twelfth Symposium on Conformal and Probabilistic Prediction with Applications, 204:194–213, 13–15 Sep 2023.arxiv.org/abs/2309.08976
  24. [24]Zhen Zhang, M Umar B Niazi, Michelle S Chong, Karl H Johansson, and Amr Alanwar. Data-driven nonconvex reachability analysis using exact multiplication. In 2025 IEEE 64th Conference on Decision and Control (CDC), pages 4882–4889. IEEE, 2025.arxiv.org/abs/2504.02147

Paper details

vlnc:W_rj5ac9gv
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

ChatGPT

View statement
Looking for related papers…
Contents