arxiv: 2604.11336 · v1 · submitted 2026-04-13 · 📡 eess.SY · cs.SY

Divide and Discard: Fast Tightening of Guaranteed State Bounds for Nonlinear Systems

Nico Holzinger , Matthias Althoff This is my paper

Pith reviewed 2026-05-10 16:12 UTC · model grok-4.3

classification 📡 eess.SY cs.SY

keywords guaranteed state estimationnonlinear discrete-time systemsinterval enclosuresdivide-and-discardmean-value enclosureset-based observers

0 comments

The pith

A divide-and-discard strategy tightens guaranteed state bounds for nonlinear discrete-time systems by early elimination of invalid interval sets.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper introduces a divide-and-discard approach for guaranteed state estimation in nonlinear discrete-time systems. It repeatedly subdivides simple interval enclosures of the state, propagates them forward using mean-value enclosures, and discards sets that cannot contain the true trajectory as soon as possible. By limiting the number of maintained sets this way, the method achieves low computational cost that scales quadratically with state dimension instead of exploding with more elaborate set representations. Evaluations on standard nonlinear benchmarks show it runs faster and produces tighter enclosures than prior guaranteed observers. A reader would care because the technique offers a practical, easy-to-implement way to obtain reliable state bounds without switching to complex set representations.

Core claim

The central claim is that repeated subdivision of interval enclosures combined with mean-value forward propagation and aggressive early discarding of invalid sets yields guaranteed state bounds that are both tighter and cheaper to compute than those obtained from more sophisticated set representations, while the number of active sets remains bounded so that complexity grows only quadratically in the state dimension.

What carries the argument

The divide-and-discard strategy, which subdivides interval enclosures of possible states, propagates them with mean-value enclosures, and discards non-viable sets early to limit the total number maintained.

If this is right

The observer can be inserted into existing interval-based frameworks because it only manipulates ordinary interval vectors.
Computational cost remains manageable even as state dimension grows because only a controlled number of sets are kept at each step.
Tighter enclosures are obtained on the same benchmark problems previously used to evaluate guaranteed observers.
Implementation is straightforward since no advanced set representations such as zonotopes or ellipsoids are required.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The same early-discard idea might be adapted to continuous-time systems by replacing the discrete propagation step with a suitable flow-pipe enclosure.
The quadratic scaling suggests the method could be applied to moderately high-dimensional systems where exponential-cost methods become intractable.
One could test whether the tightness advantage persists when the underlying mean-value enclosure is replaced by a less conservative but more expensive propagation operator.

Load-bearing premise

That repeated subdivision with mean-value enclosures will let many invalid sets be discarded early without either missing the true state trajectory or introducing so much conservatism that the final bounds become useless.

What would settle it

A nonlinear discrete-time benchmark system on which the divide-and-discard observer either fails to enclose the true trajectory at some time step or requires more runtime and yields looser final bounds than at least one competing guaranteed observer method.

Figures

Figures reproduced from arXiv: 2604.11336 by Matthias Althoff, Nico Holzinger.

**Figure 1.** Figure 1: Running example of the binning heuristics used for splitting and pruning. In (a), four two-dimensional intervals are binned by their largest scaled [PITH_FULL_IMAGE:figures/full_fig_p004_1.png] view at source ↗

**Figure 3.** Figure 3: Effect of maximum number of intervals Mmax on tightness and computation time for the 30-tank benchmark. German Research Foundation under grant GRK 2428. APPENDIX A. Benchmark Details This appendix summarizes the benchmark models and uncertainty settings used for the evaluation. a) Van der Pol Oscillator: The first benchmark is an Euler-discretized Van der Pol oscillator with sampling time h, x1,k+1 = x1,k … view at source ↗

**Figure 2.** Figure 2: Effect of maximum number of intervals Mmax on tightness and computation time for the Van der Pol oscillator with µ = 5. refinement strategy that reduces conservatism through subdivision of the state space. The numerical evaluation shows that the proposed observer consistently achieves the tightest state enclosures across the considered comparisons and nonlinear systems. In particular, for strongly nonline… view at source ↗

read the original abstract

We propose a simple yet effective divide-and-discard (DD) approach to guaranteed state estimation for nonlinear discrete-time systems. Our method iteratively subdivides interval enclosures of the state and propagates them forward in time using a mean-value enclosure. The central idea is to rely on repeated refinement of simple sets rather than on more complex set representations, yielding an observer that is straightforward to implement and easy to integrate into existing frameworks. Our divide-and-discard strategy exploits that many sets can be discarded early and limits the number of maintained sets, resulting in low computational cost with complexity that scales only quadratically in the state dimension. The proposed method is evaluated on nonlinear benchmark problems previously used to compare guaranteed observers, where it outperforms state-of-the-art approaches in terms of both computational efficiency and enclosure tightness.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The divide-and-discard strategy offers a simple way to get quadratic scaling and improved tightness for guaranteed nonlinear observers.

read the letter

The main point is that this divide-and-discard observer achieves quadratic scaling in state dimension and tighter bounds than existing methods by subdividing intervals, using mean-value enclosures, and discarding inconsistent sets early. What is new is the specific strategy of limiting the number of maintained sets through early discarding while still refining the bounds. This keeps things simple—no complex zonotopes or other representations—just basic intervals that are easy to implement and integrate. The paper shows good results on nonlinear benchmarks, with lower run times and smaller enclosure widths compared to state-of-the-art approaches. The approach is solid on the technical side. Discarding sets that do not intersect with measurements preserves the guaranteed enclosure property. The quadratic complexity follows from controlling the active set size instead of full subdivision trees. The experiments report concrete numbers on both efficiency and tightness, using problems from prior literature. One soft spot is that performance relies on frequent early discards, which may not occur in all scenarios, such as with loose measurements or highly uncertain initial sets. The paper demonstrates success on the chosen examples but could note more about when the method shines or struggles. Mean-value propagation is reliable but known to be conservative in some nonlinear cases, and while subdivision helps, it is not a complete fix. This paper targets engineers and researchers working on guaranteed state estimation for safety-critical systems. It offers practical value to those looking for straightforward algorithms that improve on current interval-based observers. It deserves a serious referee because the claims are backed by derivations and benchmark data. I would send this to peer review.

Referee Report

0 major / 3 minor

Summary. The paper proposes a divide-and-discard (DD) approach for guaranteed state estimation of nonlinear discrete-time systems. Interval enclosures of the state are iteratively subdivided and propagated forward using mean-value enclosures; sets that do not intersect the measurement are discarded early, and the number of maintained sets is capped to obtain quadratic complexity in the state dimension. The method is claimed to be straightforward to implement and is shown to outperform prior guaranteed observers on standard nonlinear benchmarks in both runtime and enclosure tightness.

Significance. If the soundness and scaling claims hold, the work supplies a simple, low-overhead alternative to set-valued observers that rely on complex representations (zonotopes, ellipsoids, etc.). The explicit use of early discarding to bound active-set cardinality, combined with reproducible benchmark comparisons using timing and width metrics, addresses a practical bottleneck in real-time guaranteed estimation. The construction preserves enclosure properties by design and avoids hidden parameters, which strengthens its potential impact.

minor comments (3)

§3.2: the rule for capping the number of maintained sets is stated procedurally but lacks an explicit pseudocode listing or complexity derivation; adding a short algorithm box would clarify how the quadratic bound is enforced without affecting soundness.
Table 2: the reported enclosure widths and CPU times for the DD method versus the three baselines are given only as averages; including standard deviations or per-run histograms would strengthen the tightness claim.
§4.1: the mean-value enclosure formula is referenced to a prior work but the exact interval arithmetic implementation (e.g., centered form or slope matrix) is not restated; a one-line reminder of the enclosure operator would aid reproducibility.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive assessment of our work, the accurate summary of the divide-and-discard approach, and the recommendation for minor revision. We appreciate the recognition of its simplicity, quadratic complexity, and performance advantages on nonlinear benchmarks.

Circularity Check

0 steps flagged

No significant circularity

full rationale

The paper describes a direct algorithmic procedure: repeated interval subdivision of state enclosures, forward propagation via the mean-value theorem, and early discarding of sets whose enclosures do not intersect the measurement set, with an explicit cap on the number of retained sets. Soundness follows immediately from the enclosure property of the mean-value form and the fact that discarding only occurs when a set is provably inconsistent with the data; the quadratic scaling claim is obtained by bounding the cardinality of the active set rather than by any fitted parameter or self-referential definition. No equations, uniqueness theorems, or self-citations are invoked in a load-bearing way that would make the claimed performance equivalent to the inputs by construction. The benchmark comparisons are external empirical evaluations and do not reduce the derivation to a tautology.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

Based solely on the abstract, the approach relies on standard properties of interval arithmetic and the mean-value theorem for function enclosures; no free parameters, ad-hoc axioms, or invented entities are mentioned.

axioms (2)

standard math Mean-value theorem provides a valid enclosure for the image of a nonlinear function over an interval
Invoked for forward propagation of state intervals.
standard math Interval arithmetic operations are sound over-approximations
Underlying all enclosure computations.

pith-pipeline@v0.9.0 · 5428 in / 1355 out tokens · 69251 ms · 2026-05-10T16:12:58.850945+00:00 · methodology

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

IndisputableMonolith/Foundation/AbsoluteFloorClosure.lean reality_from_one_distinction unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

Theorem 1 (Soundness): ... each step in Sec. III preserves inclusion. Splitting... Prediction... Correction and discarding... Pruning...

What do these tags mean?

matches: The paper's claim is directly supported by a theorem in the formal canon.
supports: The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends: The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses: The paper appears to rely on the theorem as machinery.
contradicts: The paper's claim conflicts with a theorem or certificate in the canon.
unclear: Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

30 extracted references · 30 canonical work pages

[1]

Online Verification of Automated Road Vehicles Using Reachability Analysis,

M. Althoff and J. M. Dolan, “Online Verification of Automated Road Vehicles Using Reachability Analysis,”IEEE Transactions on Robotics, vol. 30, no. 4, pp. 903–918, Aug. 2014

work page 2014
[2]

Autonomy for Surgical Robots: Concepts and Paradigms,

T. Haidegger, “Autonomy for Surgical Robots: Concepts and Paradigms,”IEEE Transactions on Medical Robotics and Bionics, vol. 1, no. 2, pp. 65–76, May 2019

work page 2019
[3]

Reachset Model Predictive Control for Disturbed Nonlinear Systems,

B. Schurmann, N. Kochdumper, and M. Althoff, “Reachset Model Predictive Control for Disturbed Nonlinear Systems,” in2018 IEEE Conference on Decision and Control (CDC). IEEE, Dec. 2018, pp. 3463–3470

work page 2018
[4]

Set Propagation Techniques for Reachability Analysis,

M. Althoff, G. Frehse, and A. Girard, “Set Propagation Techniques for Reachability Analysis,”Annual Review of Control, Robotics, and Autonomous Systems, vol. 4, no. 1, pp. 369–395, May 2021

work page 2021
[5]

Fault detection techniques based on set-membership state estimation for uncertain systems,

S. B. Chabane, “Fault detection techniques based on set-membership state estimation for uncertain systems,” Ph.D. dissertation, Universit ´e Paris-Saclay, 2015

work page 2015
[6]

Set-based fault diagnosis for uncertain nonlinear systems,

B. Mu and J. K. Scott, “Set-based fault diagnosis for uncertain nonlinear systems,”Computers & Chemical Engineering, vol. 180, p. 108479, Jan. 2024

work page 2024
[7]

Nonlinear bounded-error state estimation of continuous- time systems,

L. Jaulin, “Nonlinear bounded-error state estimation of continuous- time systems,”Automatica, vol. 38, no. 6, pp. 1079–1082, Jun. 2002

work page 2002
[8]

Accurate Set-Based State Estimation for Nonlinear Discrete-Time Systems using Differential Inequalities with Model Redundancy,

X. Yang and J. K. Scott, “Accurate Set-Based State Estimation for Nonlinear Discrete-Time Systems using Differential Inequalities with Model Redundancy,” in2018 IEEE Conference on Decision and Control (CDC). IEEE, Dec. 2018, pp. 680–685

work page 2018
[9]

A Unified KKL-Based Interval Observer for Nonlinear Discrete-Time Systems,

T. N. Dinh and G. Quoc Bao Tran, “A Unified KKL-Based Interval Observer for Nonlinear Discrete-Time Systems,”IEEE Control Sys- tems Letters, vol. 8, pp. 430–435, 2024

work page 2024
[10]

Set- Membership State Estimation with Optimal Bounding Ellipsoids,

S. Gollamudi, S. Nagaraj, S. Kapoor, and Y .-F. Huang, “Set- Membership State Estimation with Optimal Bounding Ellipsoids,” International Symposium on Information Theory and its Applications, Jul. 1998

work page 1998
[11]

A nonlinear set-membership filter for online applications,

E. Scholte and M. E. Campbell, “A nonlinear set-membership filter for online applications,”International Journal of Robust and Nonlinear Control, vol. 13, no. 15, pp. 1337–1358, Dec. 2003

work page 2003
[12]

Recursive state bounding by parallelotopes,

L. Chisci, A. Garulli, and G. Zappa, “Recursive state bounding by parallelotopes,”Automatica, vol. 32, no. 7, pp. 1049–1055, Jul. 1996

work page 1996
[13]

Nonlinear state estimation by Extended Parallelotope Set-Membership Filter,

D. Qu, Z. Huang, Y . Zhao, G. Song, K. Yi, and X. Zhao, “Nonlinear state estimation by Extended Parallelotope Set-Membership Filter,” ISA Transactions, vol. 128, pp. 414–423, Sep. 2022

work page 2022
[14]

A State Bounding Observer for Uncertain Non-linear Continuous-time Systems based on Zonotopes,

C. Combastel, “A State Bounding Observer for Uncertain Non-linear Continuous-time Systems based on Zonotopes,” inProceedings of the 44th IEEE Conference on Decision and Control. IEEE, 2005, pp. 7228–7234

work page 2005
[15]

Guaranteed state estimation by zonotopes,

T. Alamo, J. Bravo, and E. Camacho, “Guaranteed state estimation by zonotopes,”Automatica, vol. 41, no. 6, pp. 1035–1043, Jun. 2005

work page 2005
[16]

Zonotopic guaranteed state estimation for uncertain systems,

V . T. H. Le, C. Stoica, T. Alamo, E. F. Camacho, and D. Dumur, “Zonotopic guaranteed state estimation for uncertain systems,”Auto- matica, vol. 49, no. 11, pp. 3418–3424, Nov. 2013

work page 2013
[17]

Guaranteed State Estimation via Indirect Polytopic Set Computation for Nonlinear Discrete-Time Systems,

M. Khajenejad, F. Shoaib, and S. Zheng Yong, “Guaranteed State Estimation via Indirect Polytopic Set Computation for Nonlinear Discrete-Time Systems,” in2021 60th IEEE Conference on Decision and Control (CDC). IEEE, Dec. 2021, pp. 6167–6174

work page 2021
[18]

Constrained zonotopes: A new tool for set-based estimation and fault detection,

J. K. Scott, D. M. Raimondo, G. R. Marseglia, and R. D. Braatz, “Constrained zonotopes: A new tool for set-based estimation and fault detection,”Automatica, vol. 69, pp. 126–136, Jul. 2016

work page 2016
[19]

Guaranteed methods based on constrained zonotopes for set-valued state estimation of nonlinear discrete-time systems,

B. S. Rego, G. V . Raffo, J. K. Scott, and D. M. Raimondo, “Guaranteed methods based on constrained zonotopes for set-valued state estimation of nonlinear discrete-time systems,”Automatica, vol. 111, p. 108614, Jan. 2020

work page 2020
[20]

A comparison of set-based observers for nonlinear systems,

N. Holzinger and M. Althoff, “A comparison of set-based observers for nonlinear systems,” 2026. [Online]. Available: https: //arxiv.org/abs/2602.03646

work page arXiv 2026
[21]

Jaulin, M

L. Jaulin, M. Kieffer, O. Didrit, and E. Walter,Applied Interval Analysis. Springer, 2001

work page 2001
[22]

Implementation of Taylor models in CORA 2018,

M. Althoff, D. Grebenyuk, and N. Kochdumper, “Implementation of Taylor models in CORA 2018,” 2018, pp. 145–115. [Online]. Available: https://easychair.org/publications/paper/9Tz3

work page 2018
[23]

Constraints propagation techniques on intervals for a guaranteed localization using redundant data,

A. Gning and P. Bonnifait, “Constraints propagation techniques on intervals for a guaranteed localization using redundant data,”Auto- matica, vol. 42, no. 7, pp. 1167–1175, Jul. 2006

work page 2006
[24]

Fast computation of the median by successive binning,

R. J. Tibshirani, “Fast computation of the median by successive binning,”arXiv preprint arXiv:0806.3301, 2008

work page arXiv 2008
[25]

Guaranteed recursive nonlinear state estimation using interval analysis,

M. Kieffer, L. Jaulin, and E. Walter, “Guaranteed recursive nonlinear state estimation using interval analysis,” inProceedings of the 37th IEEE Conference on Decision and Control, vol. 4. IEEE, 1998, pp. 3966–3971

work page 1998
[26]

Set inversion via interval analysis for nonlinear bounded-error estimation,

L. Jaulin and E. Walter, “Set inversion via interval analysis for nonlinear bounded-error estimation,”Automatica, vol. 29, no. 4, pp. 1053–1064, Jul. 1993

work page 1993
[27]

An introduction to cora 2015,

M. Althoff, “An introduction to cora 2015,”ARCH14-15. 1st and 2nd International Workshop on Applied veRification of Continuous and Hybrid Systems, vol. 34, pp. 120–151, 2015

work page 2015
[28]

Set-membership approach and Kalman observer based on zonotopes for discrete-time descriptor systems,

Y . Wang, V . Puig, and G. Cembrano, “Set-membership approach and Kalman observer based on zonotopes for discrete-time descriptor systems,”Automatica, vol. 93, pp. 435–443, Jul. 2018

work page 2018
[29]

Zonotopes and Kalman observers: Gain optimality under distinct uncertainty paradigms and robust convergence,

C. Combastel, “Zonotopes and Kalman observers: Gain optimality under distinct uncertainty paradigms and robust convergence,”Auto- matica, vol. 55, pp. 265–273, May 2015

work page 2015
[30]

Bounded Error Identification of Systems With Time-Varying Parameters,

J. Bravo, T. Alamo, and E. Camacho, “Bounded Error Identification of Systems With Time-Varying Parameters,”IEEE Transactions on Automatic Control, vol. 51, no. 7, pp. 1144–1150, Jul. 2006

work page 2006