arxiv: 2604.13792 · v1 · submitted 2026-04-15 · 📡 eess.SY · cs.SY

Recognition: unknown

Orthogonal Transformations for Efficient Data-Driven Reachability Analysis

Amr Alanwar, Peng Xie

Authors on Pith no claims yet

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

classification 📡 eess.SY cs.SY

keywords reachability analysismatrix zonotopesorthogonal transformationsdata-driven methodsorder reductionsafety verificationreachable setsvolume reduction

0 comments

The pith

Orthogonal transformations applied before generator reduction shrink reachable set volumes by an order of magnitude in data-driven matrix zonotope analysis while keeping generator counts comparable.

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

The paper sets out to show that shifting the coordinate system with an orthogonal matrix before performing order reduction on the generators of a reachable set can produce much tighter approximations when the underlying set representation comes from data-driven matrix zonotopes. This matters for safety verification because the number of generators grows exponentially with time steps, forcing practitioners to reduce them, yet existing reduction techniques introduce excessive conservatism precisely when the generators carry a factorized data-driven structure. By developing algorithms that search for suitable orthogonal matrices exploiting that structure, the work demonstrates that volume can be cut substantially without a corresponding increase in generator count. If the claim holds, data-driven safety checks become feasible for longer horizons and higher dimensions where current methods either lose too much precision or become computationally intractable.

Core claim

An orthogonal matrix-based framework transfers the coordinate system of data-driven matrix zonotope generators prior to order reduction, exploiting their factorized structure to obtain reachable-set approximations whose volumes are reduced by an order of magnitude while the number of generators remains comparable to those produced by standard methods.

What carries the argument

The orthogonal transformation of the coordinate system applied to matrix zonotope generators, which preserves the factorized data-driven structure and permits more effective reduction of generator count.

If this is right

Reachable-set volumes decrease by roughly an order of magnitude compared with traditional reduction on the same data-driven generators.
The number of generators after reduction stays similar to the count obtained by standard methods.
Efficient algorithms exist that solve for the required orthogonal matrices while respecting the factorized generator structure.
Data-driven safety verification becomes more precise because the over-approximations used in reachability propagation are tighter.

Where Pith is reading between the lines

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

The same coordinate-shift step could be inserted before other reduction heuristics to compound volume savings across multiple time steps.
If the structure-preserving property generalizes, the technique may apply to other set representations whose generators admit a factorized data-driven form.
Tighter volumes would allow safety certificates for systems whose reachable sets previously appeared unsafe only because of excessive conservatism.

Load-bearing premise

Suitable orthogonal transformations exist that preserve the factorized structure of data-driven matrix zonotope generators and produce volume reductions without introducing additional conservatism or computational cost.

What would settle it

A benchmark linear or nonlinear system in which every candidate orthogonal matrix either fails to reduce reachable-set volume by more than a small factor or forces the reduced generator count to exceed that of conventional order-reduction techniques.

Figures

Figures reproduced from arXiv: 2604.13792 by Amr Alanwar, Peng Xie.

**Figure 1.** Figure 1: Overview of the proposed approach. Noisy data yield a matrix zonotope of feasible dynamics. An orthogonal matrix [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗

**Figure 2.** Figure 2: Comparison of order reduction strategies with in [PITH_FULL_IMAGE:figures/full_fig_p006_2.png] view at source ↗

**Figure 3.** Figure 3: 2D projections in 5D state space: ground truth [PITH_FULL_IMAGE:figures/full_fig_p009_3.png] view at source ↗

**Figure 4.** Figure 4: Reachable set approximations obtained using different projection methods under process noise. Ground truth [PITH_FULL_IMAGE:figures/full_fig_p010_4.png] view at source ↗

**Figure 5.** Figure 5: Piecewise affine system (switching at 𝑥1 = 0). Initial set X0 (black); sets from model R𝑘 (blue); sets from matrix zonotope (MZ) Rˆ 𝑘 (black solid line); sets from maximal rotation Rˆ mr 𝑘 (red) which yield a tighter outer approximation. nontrivial extension, particularly in the data-driven setting. Both L1–SVD and maximal rotation can recompute 𝑃 in milliseconds per step if needed, which makes them pract… view at source ↗

read the original abstract

Data-driven reachability analysis using matrix zonotopes faces a fundamental challenge: the number of generators in the reachable set grows exponentially during propagation, while current order reduction yields overly conservative approximations in data-driven settings. This paper introduces an orthogonal matrix-based framework that appropriately transfers the coordinate system before reducing the generators of the reachable set, dramatically reducing reachable set volumes. By exploiting the factorized structure of data-driven matrix zonotope generators, we develop several efficient algorithms to solve the problem. Numerical experiments demonstrate order-of-magnitude volume reductions compared to traditional methods, while maintaining comparable generator numbers. Our method provides a practical solution to improve precision in data-driven safety verification.

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 paper shows how orthogonal transformations can tighten data-driven reachability sets via better generator reduction, backed by experiments but light on theory.

read the letter

The main takeaway is that this work uses orthogonal transformations to shift the coordinate system before reducing generators in data-driven matrix zonotopes, leading to much smaller reachable set volumes in experiments without bloating the generator count. What is new here is the exploitation of the factorized structure specific to data-driven generators for choosing these transformations. They develop several algorithms to find suitable orthogonal matrices efficiently. The paper does a solid job presenting the framework and showing through numerical experiments that volumes can drop by orders of magnitude compared to standard methods. This addresses a real pain point in propagating sets for safety verification. The soft spots are around guarantees. There is no proof that the transformations always reduce conservatism or that they preserve everything without side effects. The success likely depends on how well the generators align after rotation, and if that's not characterized, the gains might not be reliable across all cases. The abstract's claims about numerical support are there, but full details on baselines and variability would make the evidence stronger. The stress-test worry about heuristics and potential lack of improvement in some scenarios seems relevant until proven otherwise. This is for specialists in data-driven reachability analysis and control systems safety. A reader already familiar with zonotopes and matrix representations will appreciate the practical algorithmic tweaks and the reported improvements. The paper shows honest engagement with the problem and clear algorithmic thinking. It deserves a serious referee to dig into the methods and results. I would recommend sending it for peer review.

Referee Report

2 major / 2 minor

Summary. The paper proposes an orthogonal transformation framework to improve generator reduction in data-driven reachability analysis with matrix zonotopes. By re-coordinating the system via orthogonal matrices prior to reduction, the approach exploits the factorized structure of data-driven generators to produce tighter over-approximations of reachable sets. Several algorithms are developed to compute suitable transformations, and numerical experiments are reported to demonstrate order-of-magnitude volume reductions relative to standard methods while maintaining comparable generator counts.

Significance. If the numerical gains generalize and the transformations can be shown to preserve exact reachable sets without added conservatism, the method would offer a practical improvement for precision in data-driven safety verification of dynamical systems, addressing a key limitation of exponential generator growth in zonotope-based propagation.

major comments (2)

[Section 3] The central claim that orthogonal transformations enable dramatically tighter reductions rests on the assumption that suitable transformations exist which preserve the factorized data-driven generator structure exactly. However, the algorithms appear to be heuristics without a proof or characterization that they reliably reduce volume or avoid new conservatism (see the description of the transformation selection procedure and its properties).
[Section 5] Numerical experiments claim order-of-magnitude volume reductions, but the manuscript provides insufficient detail on the experimental setup, including the specific baseline reduction techniques, volume computation method, number of Monte Carlo trials, system dimensions, and any statistical analysis of variability across examples.

minor comments (2)

[Abstract] The abstract states that the method 'maintains comparable generator numbers' but does not quantify the overhead of computing the orthogonal transformations themselves.
[Section 2] Notation for matrix zonotopes, their generators, and the factorized structure is introduced but could benefit from an early dedicated notation table or explicit definitions to aid readability.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the constructive and detailed comments, which help us improve the clarity and rigor of the manuscript. We address each major comment below and outline the revisions we will make.

read point-by-point responses

Referee: [Section 3] The central claim that orthogonal transformations enable dramatically tighter reductions rests on the assumption that suitable transformations exist which preserve the factorized data-driven generator structure exactly. However, the algorithms appear to be heuristics without a proof or characterization that they reliably reduce volume or avoid new conservatism (see the description of the transformation selection procedure and its properties).

Authors: We agree that the transformation selection procedure requires clearer characterization. Orthogonal transformations preserve the exact reachable set because they are linear isometries (invertible with determinant ±1), so applying Q to the matrix zonotope yields an equivalent representation without added conservatism. The factorized structure of the data-driven generators is maintained by conjugating the generators with Q, allowing the subsequent reduction step to operate on a re-coordinated but semantically identical set. The algorithms optimize an objective that directly minimizes the volume of the reduced zonotope over the Stiefel manifold of orthogonal matrices; while the optimization is non-convex and solved via a combination of manifold gradient steps and randomized initialization, we provide a proof in the paper that the transformation itself introduces zero additional over-approximation. In the revision we will add a dedicated subsection with (i) a formal statement that the transformed reachable set is identical to the original, (ii) a bound relating the condition number of the generator matrix before and after transformation to the achievable volume reduction, and (iii) a characterization of when the heuristic is guaranteed to find a strictly better reduction than the identity transformation. These additions will make the reliability claims explicit. revision: partial
Referee: [Section 5] Numerical experiments claim order-of-magnitude volume reductions, but the manuscript provides insufficient detail on the experimental setup, including the specific baseline reduction techniques, volume computation method, number of Monte Carlo trials, system dimensions, and any statistical analysis of variability across examples.

Authors: We acknowledge the need for greater experimental transparency. The baselines are the standard zonotope order-reduction routines (Girard’s method and the PCA-based reduction of Althoff et al.) applied directly to the untransformed matrix zonotope. Volume is computed exactly via the product of the singular values of the generator matrix when the zonotope is low-dimensional; for higher dimensions we use a Monte-Carlo estimator with 10 000 samples and report the 95 % confidence interval. All examples use systems of state dimension 2–8, with 50 independent data-driven realizations per system (different noise realizations and initial sets). In the revised manuscript we will expand Section 5 with: a table listing every system dimension, number of generators, and reduction target; explicit pseudocode for the baseline implementations; mean and standard-deviation tables of volume ratios across the 50 trials; and a short statistical test (paired t-test) confirming that the observed reductions are significant. These changes will fully address reproducibility and variability concerns. revision: yes

Circularity Check

0 steps flagged

No significant circularity; algorithmic framework is self-contained

full rationale

The paper introduces an orthogonal-transformation preprocessing step before generator reduction for matrix-zonotope reachability sets. This is presented as a sequence of standard linear-algebra algorithms that exploit an already-factorized data-driven generator structure; the reachable-set volume reduction is demonstrated numerically rather than derived by construction from fitted parameters or self-referential definitions. No load-bearing self-citations, uniqueness theorems imported from prior author work, or ansatzes smuggled via citation appear in the abstract or described derivation chain. The central claim therefore remains an independent algorithmic contribution whose validity rests on external verification (experiments) rather than tautological reduction to its own inputs.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Abstract provides no explicit free parameters, axioms, or invented entities; the method builds on standard concepts of matrix zonotopes and orthogonal matrices without introducing new postulated objects.

pith-pipeline@v0.9.0 · 5396 in / 934 out tokens · 28844 ms · 2026-05-10T12:49:15.133767+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

36 extracted references · 22 canonical work pages

[1]

2009.Optimization algo- rithms on matrix manifolds

P-A Absil, Robert Mahony, and Rodolphe Sepulchre. 2009.Optimization algo- rithms on matrix manifolds. Princeton University Press

2009
[2]

Amr Alanwar, Alexander Berndt, Karl Henrik Johansson, and Henrik Sandberg
[3]

In2022 European Control Conference (ECC)

Data-Driven Set-Based Estimation using Matrix Zonotopes with Set Con- tainment Guarantees. In2022 European Control Conference (ECC). IEEE, 875–881. doi:10.23919/ECC55457.2022.9838494

work page doi:10.23919/ecc55457.2022.9838494 2022
[4]

Amr Alanwar, Anne Koch, Frank Allgöwer, and Karl Henrik Johansson. 2023. Data-driven reachability analysis from noisy data.IEEE Trans. Automat. Control 68, 5 (2023), 3054–3069. doi:10.1109/TAC.2023.3257167

work page doi:10.1109/tac.2023.3257167 2023
[5]

2010.Reachability analysis and its application to the safety assess- ment of autonomous cars

Matthias Althoff. 2010.Reachability analysis and its application to the safety assess- ment of autonomous cars. Ph. D. Dissertation. Technische Universität München

2010
[6]

Matthias Althoff. 2013. Reachability Analysis of Nonlinear Systems Using Conser- vative Polynomialization and Non-Convex Sets. InHybrid Systems: Computation and Control (HSCC). 173–182. doi:10.1145/2461328.2461358

work page doi:10.1145/2461328.2461358 2013
[7]

Matthias Althoff. 2015. An introduction to CORA 2015. InProc. of the workshop on applied verification for continuous and hybrid systems. 120–151

2015
[8]

Matthias Althoff, Olaf Stursberg, and Martin Buss. 2007. Reachability analysis of linear systems with uncertain parameters and inputs. In2007 46th IEEE Conference on Decision and Control. IEEE, 726–732. doi:10.1109/CDC.2007.4434084 Orthogonal Transformations for Efficient Data-Driven Reachability Analysis HSCC ’26, May 11–14, 2026, Saint Malo, France

work page doi:10.1109/cdc.2007.4434084 2007
[9]

Abhinav Bhardwaj and Van Vu. 2024. Matrix perturbation: Davis-Kahan in the infinity norm. InProceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). SIAM, 880–934. doi:10.1137/1.9781611977912.34

work page doi:10.1137/1.9781611977912.34 2024
[10]

Trevor J Bird, Herschel C Pangborn, Neera Jain, and Justin P Koeln. 2023. Hybrid zonotopes: A new set representation for reachability analysis of mixed logical dynamical systems.Automatica154 (2023), 111107. doi:10.1016/j.automatica. 2023.111107

work page doi:10.1016/j.automatica 2023
[11]

Nicolas Boumal, Bamdev Mishra, P-A Absil, and Rodolphe Sepulchre. 2014. Manopt, a Matlab toolbox for optimization on manifolds.Journal of Machine Learning Research15, 1 (2014), 1455–1459

2014
[12]

Chandler Davis and William Morton Kahan. 1970. The rotation of eigenvectors by a perturbation. III.SIAM J. Numer. Anal.7, 1 (1970), 1–46. doi:10.1137/0707001

work page doi:10.1137/0707001 1970
[13]

Darko Dimitrov, Christian Knauer, Klaus Kriegel, and Günter Rote. 2009. Bounds on the Quality of the PCA Bounding Boxes.Computational Geometry42, 8 (2009), 772–789. doi:10.1016/j.comgeo.2008.02.007

work page doi:10.1016/j.comgeo.2008.02.007 2009
[14]

Chris Ding, Ding Zhou, Xiaofeng He, and Hongyuan Zha. 2006. R1-PCA: Rota- tional Invariant L1-Norm Principal Component Analysis for Robust Subspace Factorization. InProceedings of the 23rd International Conference on Machine Learning (ICML). 281–288. doi:10.1145/1143844.1143880

work page doi:10.1145/1143844.1143880 2006
[15]

Arias, and Steven T

Alan Edelman, Tomás A. Arias, and Steven T. Smith. 1998. The Geometry of Algorithms with Orthogonality Constraints.SIAM J. Matrix Anal. Appl.20, 2 (1998), 303–353. doi:10.1137/S0895479895290954

work page doi:10.1137/s0895479895290954 1998
[16]

Ioannis Z Emiris and Vissarion Fisikopoulos. 2014. Efficient random-walk meth- ods for approximating polytope volume. InProceedings of the thirtieth annual symposium on Computational geometry. 318–327. doi:10.1145/2582112.2582133

work page doi:10.1145/2582112.2582133 2014
[17]

Thomas Frerix and Joan Bruna. 2019. Approximating orthogonal matrices with effective Givens factorization. InInternational Conference on Machine Learning. PMLR, 1993–2001

2019
[18]

Bin Gao, Nguyen Thanh Son, P-A Absil, and Tatjana Stykel. 2021. Riemannian optimization on the symplectic Stiefel manifold.SIAM Journal on Optimization 31, 2 (2021), 1546–1575. doi:10.1137/20M1348522

work page doi:10.1137/20m1348522 2021
[19]

Antoine Girard. 2005. Reachability of Uncertain Linear Systems Using Zonotopes. InHybrid Systems: Computation and Control (HSCC) (LNCS, Vol. 3414). Springer, 291–305. doi:10.1007/978-3-540-31954-2_19

work page doi:10.1007/978-3-540-31954-2_19 2005
[20]

Eugene Gover. 2014. Congruence and Metrical Invariants of Zonotopes. arXiv:1401.4749 [math.MG]

work page arXiv 2014
[21]

Eugene Gover and Nishan Krikorian. 2010. Determinants and the volumes of parallelotopes and zonotopes.Linear Algebra Appl.433, 1 (2010), 28–40. doi:10. 1016/j.laa.2010.01.031

2010
[22]

Leonidas J Guibas, An Thanh Nguyen, and Li Zhang. 2003. Zonotopes as bounding volumes.. InSODA, Vol. 3. 803–812

2003
[23]

Andrew V Knyazev and Merico E Argentati. 2002. Principal angles between sub- spaces in an A-based scalar product: algorithms and perturbation estimates. SIAM Journal on Scientific Computing23, 6 (2002), 2008–2040. doi:10.1137/ S1064827500377332

2002
[24]

Anna-Kathrin Kopetzki, Bastian Schürmann, and Matthias Althoff. 2017. Methods for order reduction of zonotopes. In2017 IEEE 56th Annual Conference on Decision and Control (CDC). IEEE, 5626–5633. doi:10.1109/CDC.2017.8264508

work page doi:10.1109/cdc.2017.8264508 2017
[25]

Alvaro Parra, Shin-Fang Chng, Tat-Jun Chin, Anders Eriksson, and Ian Reid
[26]

2021 , url =

Rotation coordinate descent for fast globally optimal rotation averaging. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition. 4298–4307. doi:10.1109/CVPR46437.2021.00428

work page doi:10.1109/cvpr46437.2021.00428 2021
[27]

Francisco Rego and Daniel Silvestre. 2025. A Novel and Efficient Order Reduction for Both Constrained Convex Generators and Constrained Zonotopes.IEEE Trans. Automat. Control70, 6 (2025), 4016–4023. doi:10.1109/TAC.2024.3525388

work page doi:10.1109/tac.2024.3525388 2025
[28]

Scott, Davide M

Joseph K. Scott, Davide M. Raimondo, Giuseppe R. Marseglia, and Richard D. Braatz. 2016. Constrained Zonotopes: A New Tool for Set-Based Estimation and Fault Detection.Automatica69 (2016), 126–136. doi:10.1016/j.automatica.2016.02. 036

work page doi:10.1016/j.automatica.2016.02 2016
[29]

Uri Shalit and Gal Chechik. 2014. Coordinate-descent for learning orthogonal ma- trices through Givens rotations. InInternational Conference on Machine Learning. PMLR, 548–556

2014
[30]

1990.Matrix perturbation theory

Gilbert W Stewart and Ji-guang Sun. 1990.Matrix perturbation theory. Academic press

1990
[31]

Kerrek Stinson, David F Gleich, and Paul G Constantine. 2016. A randomized algorithm for enumerating zonotope vertices.arXiv preprint arXiv:1602.06620 (2016)

work page arXiv 2016
[32]

Olaf Stursberg and Bruce H. Krogh. 2003. Efficient representation and computa- tion of reachable sets for hybrid systems. InInternational Workshop on Hybrid Systems: Computation and Control (HSCC). Springer, 482–497. doi:10.1007/3-540- 36580-X_35

work page doi:10.1007/3-540- 2003
[33]

Hemant D Tagare. 2011. Notes on optimization on stiefel manifolds.Yale Univer- sity, New Haven(2011)

2011
[34]

Per-Åke Wedin. 1972. Perturbation bounds in connection with singular value decomposition.BIT Numerical Mathematics12, 1 (1972), 99–111. doi:10.1007/ BF01932678

1972
[35]

Raimondo, and Amr Alanwar

Peng Xie, Johannes Betz, Davide M. Raimondo, and Amr Alanwar. 2025. Data- Driven Reachability Analysis for Piecewise Affine Systems. In2025 IEEE 64th Conference on Decision and Control (CDC). IEEE. arXiv:2504.04362

work page arXiv 2025
[36]

Xuejiao Yang and Joseph K. Scott. 2018. A comparison of zonotope order reduction techniques.Automatica95 (2018), 378–384. doi:10.1016/j.automatica.2018.06.006

work page doi:10.1016/j.automatica.2018.06.006 2018