# Set inversion

> Mediated Wiki article. Canonical URL: https://mediated.wiki/source/Set_inversion
> Markdown URL: https://mediated.wiki/source/Set_inversion.md
> Source: https://en.wikipedia.org/wiki/Set_inversion
> Source revision: 1330718095
> License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/)

Mathematical problem of finding the set mapped by a specified function to a certain range

In [mathematics](/source/Mathematics), **set inversion** is the problem of characterizing the [preimage](/source/Inverse_image) *X* of a [set](/source/Set_(mathematics)) *Y* by a [function](/source/Function_(mathematics)) *f*, i.e., *X* = *f*−1(*Y* ) = {*x* ∈ **R***n* | *f*(*x*) ∈ *Y* }. It can also be viewed as the problem of describing the solution set of the quantified constraint "*Y*(*f* (*x*))", where *Y*(*y*) is a constraint, e.g. an [inequality](/source/Inequality_(mathematics)), describing the set *Y*.

In most applications, *f* is a function from **R***n* to **R***p* and the set *Y* is a box of **R***p* (i.e. a [Cartesian product](/source/Cartesian_product) of *p* [intervals](/source/Interval_(mathematics)) of **R**).

When *f* is nonlinear the set inversion problem can be solved[1] using [interval analysis](/source/Interval_analysis) combined with a [branch-and-bound](/source/Branch_and_bound) algorithm.[2]

The main idea consists in building a paving of **R***p* made with non-overlapping boxes. For each box [*x*], we perform the following tests:

1. if *f* ([*x*]) ⊂ *Y* we conclude that [*x*] ⊂ *X*;

1. if *f* ([*x*]) ∩ *Y* = [∅](/source/Empty_set) we conclude that [*x*] ∩ *X* = ∅;

1. Otherwise, the box [*x*] the box is bisected except if its width is smaller than a given precision.

To check the two first tests, we need an [interval extension](/source/Interval_arithmetic) (or an inclusion function) [*f* ] for *f*. Classified boxes are stored into [subpavings](/source/Subpaving), i.e., [union](/source/Union_(set_theory)) of non-overlapping boxes. The algorithm can be made more efficient by replacing the inclusion tests by [contractors](/source/Interval_contractor).

## Example

The set *X* = *f* −1([4,9]) where *f* (*x*1, *x*2) = *x*2 1 + *x*2 2 is represented on the figure.

For instance, since [−2,1]2 + [4,5]2 = [0,4] + [16,25] = [16,29] does not [intersect](/source/Intersection_(set_theory)) the interval [4,9], we conclude that the box [−2,1] × [4,5] is outside *X*. Since [−1,1]2 + [2,√5]2 = [0,1] + [4,5] = [4,6] is inside [4,9], we conclude that the whole box [−1,1] × [2,√5] is inside *X*.

A ring defined as a set inversion problem

## Application

Set inversion is mainly used for [path planning](/source/Motion_planning), for nonlinear parameter [set estimation](/source/Set_estimation),[3][4] for localization[5][6] or for the characterization of stability domains of [linear dynamical systems](/source/Linear_dynamical_system).[7]

## References

1. **[^](#cite_ref-1)** Jaulin, L.; Walter, E. (1993). ["Set inversion via interval analysis for nonlinear bounded-error estimation"](http://www.ensta-bretagne.fr/jaulin/paper_automatica93.pdf) (PDF). *Automatica*. **29** (4): 1053–1064. [doi](/source/Doi_(identifier)):[10.1016/0005-1098(93)90106-4](https://doi.org/10.1016%2F0005-1098%2893%2990106-4).

1. **[^](#cite_ref-2)** Jaulin, L.; Kieffer, M.; Didrit, O.; Walter, E. (2001). *Applied Interval Analysis*. Berlin: Springer. [ISBN](/source/ISBN_(identifier)) [1-85233-219-0](https://en.wikipedia.org/wiki/Special:BookSources/1-85233-219-0).

1. **[^](#cite_ref-3)** Jaulin, L.; Godet, J.L; Walter, E.; Elliasmine, A.; Leduff, Y. (1997). ["Light scattering data analysis via set inversion"](http://www.ensta-bretagne.fr/jaulin/simcf4.pdf) (PDF). *Journal of Physics A: Mathematical and General*. **30** (22): 7733–7738. [Bibcode](/source/Bibcode_(identifier)):[1997JPhA...30.7733J](https://ui.adsabs.harvard.edu/abs/1997JPhA...30.7733J). [doi](/source/Doi_(identifier)):[10.1088/0305-4470/30/22/012](https://doi.org/10.1088%2F0305-4470%2F30%2F22%2F012).

1. **[^](#cite_ref-4)** Braems, I.; Berthier, F.; Jaulin, L.; Kieffer, M.; Walter, E. (2001). ["Guaranteed Estimation of Electrochemical Parameters by Set Inversion Using Interval Analysis"](http://www.ensta-bretagne.fr/jaulin/electrochimie.pdf) (PDF). *Journal of Electroanalytical Chemistry*. **495** (1).

1. **[^](#cite_ref-5)** Colle, E.; Galerne, S. (2013). "Mobile robot localization by multiangulation using set inversion". *Robotics and Autonomous Systems*. **66** (1): 39–48. [doi](/source/Doi_(identifier)):[10.1016/j.robot.2012.09.006](https://doi.org/10.1016%2Fj.robot.2012.09.006).

1. **[^](#cite_ref-6)** Drevelle, V.; Bonnifait, Ph. (2011). ["A set-membership approach for high integrity height-aided satellite positioning"](https://hal.science/hal-00608133/file/Drevelle_rev3_HAL.pdf) (PDF). *GPS Solutions*. **15** (4): 357–368. [Bibcode](/source/Bibcode_(identifier)):[2011GPSS...15..357D](https://ui.adsabs.harvard.edu/abs/2011GPSS...15..357D). [doi](/source/Doi_(identifier)):[10.1007/s10291-010-0195-3](https://doi.org/10.1007%2Fs10291-010-0195-3). [S2CID](/source/S2CID_(identifier)) [121728552](https://api.semanticscholar.org/CorpusID:121728552).

1. **[^](#cite_ref-7)** Walter, E.; Jaulin, L. (1994). ["Guaranteed characterization of stability domains via set inversion"](http://www.ensta-bretagne.fr/jaulin/IEEEStab.pdf) (PDF). *IEEE Trans. Autom. Control*. **39** (4): 886–889. [doi](/source/Doi_(identifier)):[10.1109/9.286277](https://doi.org/10.1109%2F9.286277).

---
Adapted from the Wikipedia article [Set inversion](https://en.wikipedia.org/wiki/Set_inversion) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/Set_inversion?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.