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:
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.
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: , , and , for nonempty . The nullspace of is . For , let denote the -th standard basis vector, whose -th entry is one and all other entries are zero. Let and denote the time horizon index sets and consider the sensor index set . The operator denotes the vertical concatenation of elements in a vector. For a sequence and integers , define , where the indices run in increasing order from to . We finally define the nonnegative integers as . The indicator equals one if condition holds and zero otherwise.
Problem Formulation
Consider the system with the following state and output dynamics:
The state evolves according to the unknown dynamics , where is the known input and is the unknown process disturbance. In our setting, neither the state trajectory nor the disturbance are accessible. The state domain is known, and can possibly be the entire , whereas need not be known. Note that neither set is assumed to be bounded. For each sensor , the sensor map is , and the measured output satisfies (2) where denotes the measurement noise for sensor . For each , we thus define the concatenated output, measurement noise, and sensing map by , , , respectively, where . Thus, we have that and , and the sensor dynamics can be written in the compact form . We now impose the following assumption:
Assumption 1 For every sensor , the sensor map is given by the linear transformation , where the matrix is known.
Let denote the concatenated sensor matrix, so that . Writing and , we collect the input and corresponding output trajectory into a single vector , 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 are independent and identically distributed according to a possibly unknown probability distribution . A new trajectory pair is also independent from the multi-sample and follows the same probability distribution , i.e., it holds that .
Assumption 2 permits dependence across time, sensors, inputs, and outputs within each trajectory. We further impose the following measurability assumption.
Assumption 3 The sets , , and are Borel subsets of their respective Euclidean spaces. The dynamics and sensor maps , , are Borel measurable. Furthermore, we consider Borel measurable feedback control policies of the form , with and .
Assumption 2 holds for both open-loop and feedback experiments under identical training and deployment conditions. Let 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 such that . Hence, i.i.d. uncertainty realizations induce i.i.d. input-output trajectories with distribution for every Borel set in the input-output trajectory space.
For the measurement noise, we assume either known deterministic bounds or a specified distribution that the noise trajectory follows. Note that is the marginal distribution of under the probability distribution . In the latter case, we generate independent synthetic trajectories from , collected in the multi-sample , to construct the noise sets . The distribution of is given by the cartesian product . 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 . We then impose the following assumption:
Assumption 4 For any , the mapping is measurable and the returned set is nonempty and compact. For a confidence parameter , there exists a violation level such that .
For known deterministic noise bounds, it holds by construction that and . For example, using the synthetic trajectories , let and . If has a continuous distribution , then it holds that . We then define such that . For , define the quantile . Continuity of then gives . Moreover, is equivalent to , meaning that every sampled maximum lies below . Assuming independence of the events,
Choosing gives , which establishes Assumption 4.
Characterizing the estimated set of states under unknown dynamics
For each time , let denote an estimated output set depending on the input history and parameterized by the parameters . Using the measurement noise sets introduced in Section 2, we construct the estimated state set:
The set 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., and , which yields the state set:
where the noise vector in (3) denotes the compact form . The Cartesian product structure of these sets does not require statistical independence across sensors. Let and be feature maps used to parameterize the center and half-width of the estimated output boxes as follows:
Here, and denote the -th components of and , respectively. The feature maps and are assumed to be Borel measurable. The parameter vector collects , where , , and . The admissible parameter domain is . Since , the half-widths remain nonnegative. These linear constraints define a deterministic convex parameter domain. For inputs , a simple choice for the feature maps is , and . For , the feature dimensions are . At , we set and , so that and .
We now characterize the challenge induced by the sensing map. Specifically, for a state , let us define the measurement equivalent class as . Note that states 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 be the estimated state set. Then, for every , it holds that . If, in particular, it holds that , , and , then .
Proof. Let , which implies that there exists such that . For any , it holds that , and thus , which in turn implies that . If and , let us choose . Then for every , it holds that , so that , i.e., is unbounded.
Due to Proposition 1, we impose the following assumption:
Assumption 5. The rank of is equal to the dimension of the state vector, i.e., .
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 , such that holds. For a nonempty bounded , let us define and .
Proposition 2. For any input and such that is nonempty, it holds that
Proof. Let . By construction, there exist and such that for . Since ,
The last inequality follows from . Taking the supremum over all pairs 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 . The coefficients 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 . To obtain a computationally tractable learning formulation, we introduce the diameter surrogate . Since is independent of the learning parameters , we minimize to reduce the parameter-dependent upper bound on the estimated state set diameter. Let denote the -th component of the concatenated output for . To quantify output set violations at the trajectory level, we define the uncertain function . Note that the constraint 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 for each training trajectory. Denoting the sample index set , for a fixed penalty , we solve the scenario program
The cost balances the worst-case diameter surrogate over the samples , with , at each time against output relaxation for each trajectory. Introducing the epigraphic variables we obtain the following epigraphic reformulation which is a linear program (LP) due to the geometry of the output set.
Note that the epigraph constraints on are hard constraints, while constraints corresponding to the inclusion of output trajectories are relaxed through the variables . For fixed training inputs, (6) is linear in the decision variables and feasible for every finite multi-sample . To obtain a unique optimizer, we select the minimum-norm solution among all optimizers of (6), by minimizing over the optimal set of (6). The corresponding optimal epigraph cost and relaxation variables then satisfy , , respectively. For every , the estimated state set is obtained by evaluating (3) for , namely,
In particular, for box-shaped noise sets , this reduces to . 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 be the space of input-output trajectories and define the decision domain .
Definition 3 (Adapted from Garatti and Campi [12]) For a fixed penalty , consider for each an ordered multi-sample . Let be the minimum-norm optimizer of (6) when only these samples are used. Let denote
the number of sampled trajectories that violate output inclusion. The decision map is defined by
For the empty multi-sample, define , corresponding to the minimum-norm solution of (6) with no sample constraints and an empty slack vector. For each trajectory , the appropriateness set is given by
The coordinate represents the number of training trajectories that violate output inclusion. A decision is appropriate for if . □
Evaluating means solving (6) on these trajectories and returning the learned parameters, diameter surrogate thresholds, and number of training trajectories which violate the output set. A decision belongs to if output inclusion holds without relaxation and all diameter surrogate thresholds are satisfied. For a subset , let be the sublist of indexed by , in increasing order, and write . Thus, counts the trajectories in that violate output inclusion, and .
Lemma 4 For every , , and , write and , where contains the first trajectories. The maps satisfy the three conditions of Garatti and Campi, [12]: (i) for every permutation of , (ii) implies that and (iii) implies that .
Proof (i) Permuting samples does not change the value of the map leaving the decision unchanged. (ii) Let denote the optimal value of (6) with trajectories. Since every added trajectory is appropriate, is feasible with trajectories, i.e., . Conversely, any feasible for these trajectories yields a feasible for the original problem. Its objective is therefore at least , which implies that . Since , every optimizer has zero added slacks and restricts to an original optimizer. Appending zeros preserves the norm, so the minimum-norm rule selects . The added trajectories contribute no violations, i.e., . (iii) If an added diameter constraint fails at , this pair becomes infeasible and must change, otherwise, some added trajectory has . If the selected pair stays unchanged, then . Thus it holds that . ■
Output coverage and size certification
Let us define the complexity , where . The requirement 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 reconstructs the decision , obtained when all samples are considered. For a new input/output trajectory from , we define the following probabilities:
The function is the probability that for some time , a new yet unseen output measurement does not belong in the estimated output set . The function 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 . Consequently, it holds that . For and , let be the unique root in of the following polynomial in :
Let denote the distribution of . The following result then holds:
Proposition 5 Suppose Assumption 2 holds and the maps are Borel measurable for every . Let be the complexity defined above. For , define for , where is the unique root of (10), and set . Then, it holds that
Proof. By Lemma 4, the maps satisfy (Garatti and Campi, [12]). The result follows from (Garatti and Campi, [12]).
Since is nondecreasing in (Garatti and Campi, [12]), any measurable, integer-valued upper bound satisfying yields a valid certificate. Such a bound can be obtained by sequentially removing trajectories outside , retaining a removal only if resolving (6) with the same penalty and tie-break rule preserves . The cardinality of the remaining subset then provides .
Probabilistic Guarantees for State Inclusion and Set Tightness
We remind the reader that the variable collects the uncertainties affecting the system in (1)-(2), whose corresponding input-output probability distribution is . Each realization of induces a state, process and measurement noise trajectory under the considered input. For notational simplicity, with a slight abuse of notation, we write , , and , with the dependence on the uncertainty realization to be implied. Let denote the joint distribution of the multi-sample . For any such multi-sample, we define the state trajectory exclusion probability
The function is the probability that a new state trajectory violates the estimated sets at some time . The following result provides a bound on this probability.
Proposition 6 For any , it holds that .
Proof. Note that if and , then . Hence, by the subadditivity property of the union of two events,
The last inequality follows from , which concludes the proof.
For each time step , we define the threshold . Let us now define the probability of violation for joint state coverage and tightness of the state set as follows:
Unlike , which measures only state trajectory exclusion, 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 be Borel measurable for every . Let be defined in Proposition 5, and as in Assumption 4. Then, for any and complexity bound satisfying , it holds that
Proof. Fix and consider a realization for which output and noise inclusion and the diameter surrogate threshold holds for all . By construction, we then have that . Moreover, by Proposition 2, it holds that . Consequently, we have that . 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 , and output dynamics , with , , , and . Initial states are randomly chosen from a uniform distribution on . The measurement noise is independent and uniform on the support set . The input is given by the noisy output feedback law and . Conditional on the input , the Gaussian process noise components have standard deviations and , where controls their input dependence. We then consider and . The centers of the output box are affine in , while their nonnegative half-widths are affine in and , where . We then solve the scenario program in (6) with and , which yields (see Proposition 2). For , the exact state set diameter, used only for evaluation, is .
We use , , and the known noise set , i.e., . Empirical violations are evaluated on independent test trajectories per repetition, over 15 independent repetitions. Specifically, the quantities and denote the empirical counterparts of the probabilities and , 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 , increasing 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 , and bound averaged over 15 repetitions for , and . Shaded regions indicate the min/max range across the 15 independent repetitions. (b) State set diameter and bound , both averaged over time steps, test trajectories, and 15 independent repetitions, for , , and . (c) Evolution of the mean actual and surrogate state set diameters for , with and . 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]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]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]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]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]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]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]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]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]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]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]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]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]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]D. Luenberger. An introduction to observers. IEEE Transactions on Automatic Control, 16(6):596–602, 1971.
- [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]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]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]Hyunsang Park, Vishnu Vijay, and Inseok Hwang. Data-driven reachability analysis for nonlinear systems. IEEE Control Systems Letters, 8:2661–2666, 2024.DOI
- [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]Luke Rickard, Alessandro Abate, and Kostas Margellos. Data-driven certificate synthesis. Automatica, 185:112798, 2026. ISSN 0005-1098.arxiv.org/abs/2502.05510
- [21]Simo Särkkä and Lennart Svensson. Bayesian filtering and smoothing. Cambridge University Press, 2023.
- [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]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]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
