# Sparse Polynomial Zonotopes: A Novel Set Representation for Reachability Analysis

arXiv: https://arxiv.org/abs/1901.01780 · HTML: https://mlsanity.com/paper/1901.01780/

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 7 Jan 2019.

## Built on by (most cited first, 14 of 14)

- [Verification of Neural-Network Control Systems by Integrating Taylor Models and Zonotopes](https://mlsanity.com/paper/2112.09197/) (2021)
- [Provably Safe Reinforcement Learning via Action Projection using Reachability Analysis and Polynomial Zonotopes](https://mlsanity.com/paper/2210.10691/) (2022)
- [Open- and Closed-Loop Neural Network Verification using Polynomial Zonotopes](https://mlsanity.com/paper/2207.02715/) (2022)
- [Data-Driven Reachability Analysis from Noisy Data](https://mlsanity.com/paper/2105.07229/) (2021)
- [Formal Verification of Graph Convolutional Networks with Uncertain Node Features and Uncertain Graph Structure](https://mlsanity.com/paper/2404.15065/) (2024)
- [Fully Automatic Neural Network Reduction for Formal Verification](https://mlsanity.com/paper/2305.01932/) (2023)
- [RAIL: Reachability-Aided Imitation Learning for Safe Policy Execution](https://mlsanity.com/paper/2409.19190/) (2024)
- [Robust Data-Driven Predictive Control using Reachability Analysis](https://mlsanity.com/paper/2103.14110/) (2021)
- [The FABRIC Strategy for Verifying Neural Feedback Systems](https://mlsanity.com/paper/2603.08964/) (2026)
- [Towards Global Neural Network Abstractions with Locally-Exact Reconstruction](https://mlsanity.com/paper/2210.12054/) (2022)
- [Learning from Uncertain Data: From Possible Worlds to Possible Models](https://mlsanity.com/paper/2405.18549/) (2024)
- [Perception with Guarantees: Certified Pose Estimation via Reachability Analysis](https://mlsanity.com/paper/2602.10032/) (2026)
- [Formally Verifying Analog Neural Networks Under Process Variations Using Polynomial Zonotopes](https://mlsanity.com/paper/2605.10474/) (2026)
- [Safe Multi-Robot Coordination via VLM-LLM Reasoning and Reachability Analysis](https://mlsanity.com/paper/2609.27816/) (2026)

## Abstract (arXiv)

We introduce sparse polynomial zonotopes, a new set representation for formal verification of hybrid systems. Sparse polynomial zonotopes can represent non-convex sets and are generalizations of zonotopes, polytopes, and Taylor models. Operations like Minkowski sum, quadratic mapping, and reduction of the representation size can be computed with polynomial complexity w.r.t. the dimension of the system. In particular, for reachability analysis of nonlinear systems, the wrapping effect is substantially reduced using sparse polynomial zonotopes, as demonstrated by numerical examples. In addition, we can significantly reduce the computation time compared to zonotopes when dealing with nonlinear dynamics.