# Data-Driven Reachability analysis and Support set Estimation with Christoffel Functions

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 11 of its 35 references that are in the map.
- First posted on arXiv 18 Dec 2021.

## Builds on (most cited first, 11 of 11)

- [DRYVR:Data-driven verification and compositional reasoning for automotive systems](https://mlsanity.com/paper/1702.06902/) (2017)
- [Data-Driven Reachable Set Computation using Adaptive Gaussian Process Classification and Monte Carlo Methods](https://mlsanity.com/paper/1910.02500/) (2019)
- [Data-Driven Reachability Analysis with Christoffel Functions](https://mlsanity.com/paper/2104.13902/) (2021)
- [Sorting out typicality with the inverse moment matrix SOS polynomial](https://mlsanity.com/paper/1606.03858/) (2016)
- [On-The-Fly Control of Unknown Smooth Systems from Limited Data](https://mlsanity.com/paper/2009.12733/) (2020)
- [Kernel-based Outlier Detection using the Inverse Christoffel Function](https://mlsanity.com/paper/1806.06775/) (2018)
- [Voronoi Partition-based Scenario Reduction for Fast Sampling-based Stochastic Reachability Computation of LTI Systems](https://mlsanity.com/paper/1811.03643/) (2018)
- [Data analysis from empirical moments and the Christoffel function](https://mlsanity.com/paper/1810.08480/) (2018)
- [Invariant, Viability and Discriminating Kernel Under-Approximation via Zonotope Scaling](https://mlsanity.com/paper/1901.01006/) (2019)
- [The empirical Christoffel function with applications in data analysis](https://mlsanity.com/paper/1701.02886/) (2017)
- [A Benchmark Problem in Transportation Networks](https://mlsanity.com/paper/1803.00367/) (2018)

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

- [Machine Learning for Smart and Energy-Efficient Buildings](https://mlsanity.com/paper/2211.14889/) (2022)
- [Recovering Lower-Dimensional Semialgebraic Support of a Measure from its Moments](https://mlsanity.com/paper/2609.33420/) (2026)

## Abstract (arXiv)

We present algorithms for estimating the forward reachable set of a dynamical system using only a finite collection of independent and identically distributed samples. The produced estimate is the sublevel set of a function called an empirical inverse Christoffel function: empirical inverse Christoffel functions are known to provide good approximations to the support of probability distributions. In addition to reachability analysis, the same approach can be applied to general problems of estimating the support of a random variable, which has applications in data science towards detection of novelties and outliers in data sets. In applications where safety is a concern, having a guarantee of accuracy that holds on finite data sets is critical. In this paper, we prove such bounds for our algorithms under the Probably Approximately Correct (PAC) framework. In addition to applying classical Vapnik-Chervonenkis (VC) dimension bound arguments, we apply the PAC-Bayes theorem by leveraging a formal connection between kernelized empirical inverse Christoffel functions and Gaussian process regression models. The bound based on PAC-Bayes applies to a more general class of Christoffel functions than the VC dimension argument, and achieves greater sample efficiency in experiments.