Reference articles on history, science, culture and more
Surprise meSurprise meSubscribe
Encyclopedia

Relaxed intersection

Wikipedia contributorsAdapted for Fathomly · View authors
2 min read
Source updated December 22, 2024

The relaxed intersection of m sets corresponds to the classical intersection between sets except that it is allowed to relax few sets in order to avoid an empty intersection. This notion can be used to solve constraints satisfaction problems that are inconsistent by relaxing a small number of constraints. When a bounded-error approach is considered for parameter estimation, the relaxed intersection makes it possible to be robust with respect to some outliers.

01Definition

The q-relaxed intersection of the m subsets X_{1},\dots ,X_{m} of R^{n}, denoted by X^{\{q\}}=\bigcap ^{\{q\}}X_{i} is the set of all x\in R^{n} which belong to all X_{i} 's, except q at most. This definition is illustrated by Figure 1.

Define \lambda (x)={\text{card}}\left\{i\ |\ x\in X_{i}\right\}.

We have X^{\{q\}}=\lambda ^{-1}([m-q,m]).

Characterizing the q-relaxed intersection is a thus a set inversion problem.

Figure 1. q-intersection of 6 sets for q=2 (red), q=3 (green), q= 4 (blue), q= 5 (yellow).
Figure 1. q-intersection of 6 sets for q=2 (red), q=3 (green), q= 4 (blue), q= 5 (yellow).

02Relaxed intersection of intervals

The relaxed intersection of intervals is not necessary an interval. We thus take the interval hull of the result. If X_{i}'s are intervals, the relaxed intersection can be computed with a complexity of m.log(m) by using the Marzullo's algorithm. It suffices to sort all lower and upper bounds of the m intervals to represent the function \lambda. Then, we easily get the set

X^{\{q\}}=\lambda ^{-1}([m-q,m])

which corresponds to a union of intervals. We then return the smallest interval which contains this union.

Figure 2 shows the function \lambda (x) associated to the previous example.

Figure 2. Set-membership function associated to the 6 intervals.
Figure 2. Set-membership function associated to the 6 intervals.

03Relaxed intersection of boxes

To compute the q-relaxed intersection of m boxes of R^{n}, we project all m boxes with respect to the n axes. For each of the n groups of m intervals, we compute the q-relaxed intersection. We return Cartesian product of the n resulting intervals. Figure 3 provides an illustration of the 4-relaxed intersection of 6 boxes. Each point of the red box belongs to 4 of the 6 boxes.

04Relaxed union

The q-relaxed union of X_{1},\dots ,X_{m} is defined by

{\overset {\{q\}}{\bigcup }}X_{i}=\bigcap ^{\{m-1-q\}}X_{i}

Note that when q=0, the relaxed union/intersection corresponds to the classical union/intersection. More precisely, we have

\bigcap ^{\{0\}}X_{i}=\bigcap X_{i}

and

{\overset {\{0\}}{\bigcup }}X_{i}=\bigcup X_{i}

Figure 3. The red box corresponds to the 4-relaxed intersection of the 6 boxes
Figure 3. The red box corresponds to the 4-relaxed intersection of the 6 boxes

05De Morgan's law

If {\overline {X}} denotes the complementary set of X_{i}, we have

{\overline {\bigcap ^{\{q\}}X_{i}}}={\overset {\{q\}}{\bigcup }}{\overline {X_{i}}}

{\overline {{\overset {\{q\}}{\bigcup }}X_{i}}}=\bigcap ^{\{q\}}{\overline {X_{i}}}.

As a consequence

{\overline {\bigcap \limits ^{\{q\}}X_{i}}}={\overline {{\overset {\{m-q-1\}}{\bigcup }}X_{i}}}=\bigcap ^{\{m-q-1\}}{\overline {X_{i}}}

06Relaxation of contractors

Let C_{1},\dots ,C_{m} be m contractors for the sets X_{1},\dots ,X_{m}, then

C([x])=\bigcap ^{\{q\}}C_{i}([x]).

is a contractor for X^{\{q\}} and

{\overline {C}}([x])=\bigcap ^{\{m-q-1\}}{\overline {C}}_{i}([x])

is a contractor for {\overline {X}}^{\{q\}}, where

{\overline {C}}_{1},\dots ,{\overline {C}}_{m}

are contractors for

{\overline {X}}_{1},\dots ,{\overline {X}}_{m}.

Combined with a branch-and-bound algorithm such as SIVIA (Set Inversion Via Interval Analysis), the q-relaxed intersection of m subsets of R^{n} can be computed.

Figure 4. Set of all parameter vectors consistent with exactly 6-q data bars (painted red), for q=1,2,3,4,5.
Figure 4. Set of all parameter vectors consistent with exactly 6-q data bars (painted red), for q=1,2,3,4,5.

07Application to bounded-error estimation

The q-relaxed intersection can be used for robust localization or for tracking.

Robust observers can also be implemented using the relaxed intersections to be robust with respect to outliers.

We propose here a simple example to illustrate the method. Consider a model the ith model output of which is given by

f_{i}(p)={\frac {1}{\sqrt {2\pi p_{2}}}}\exp(-{\frac {(t_{i}-p_{1})^{2}}{2p_{2}}})

where p\in R^{2}. Assume that we have

f_{i}(p)\in [y_{i}]

where t_{i} and [y_{i}] are given by the following list

\{(1,[0;0.2]),(2,[0.3;2]),(3,[0.3;2]),(4,[0.1;0.2]),(5,[0.4;2]),(6,[-1;0.1])\}

The sets \lambda ^{-1}(q) for different q are depicted on Figure 4.

Watch videos about Relaxed intersectionExplainers and documentaries on YouTube (opens in a new tab)

Sources and credits

This article is adapted from the Wikipedia article “Relaxed intersection”, written by its contributors and licensed under CC BY-SA 4.0. Fathomly has changed the layout, removed citation markers, navigation and maintenance notices, and adjusted punctuation. This adapted version is shared under the same license. For references, see the original article.

Images, from Wikimedia Commons:

Fathomly is not affiliated with or endorsed by the Wikimedia Foundation. Spotted a problem? Tell us.