Relaxed intersection – Wikipedia

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.

Definition[edit]

The q-relaxed intersection of the m subsets

${displaystyle X_{1},dots ,X_{m}}$

of

${displaystyle R^{n}}$

,
denoted by

${displaystyle X^{{q}}=bigcap ^{{q}}X_{i}}$

is the set of all

${displaystyle xin R^{n}}$

which belong to all

${displaystyle X_{i}}$

‘s, except

${displaystyle q}$

at most.
This definition is illustrated by Figure 1.

Define

${displaystyle lambda (x)={text{card}}left{i | xin X_{i}right}.}$

We have

${displaystyle X^{{q}}=lambda ^{-1}([m-q,m]).}$

Characterizing the q-relaxed intersection is a thus a set inversion problem.
^[1]

Example[edit]

Consider 8 intervals:

${displaystyle X_{1}=[1,4],}$

${displaystyle X_{2}= [2,4],}$

${displaystyle X_{3}=[2,7],}$

${displaystyle X_{4}=[6,9],}$

${displaystyle X_{5}=[3,4],}$

${displaystyle X_{6}=[3,7].}$

We have

${displaystyle X^{{0}}=emptyset ,}$

${displaystyle X^{{1}}=[3,4],}$

${displaystyle X^{{2}}=[3,4],}$

${displaystyle X^{{3}}=[2,4]cup [6,7],}$

${displaystyle X^{{4}}=[2,7],}$

${displaystyle X^{{5}}=[1,9],}$

${displaystyle X^{{6}}=]-infty ,infty [.}$

Relaxed intersection of intervals[edit]

The relaxed intersection of intervals is not necessary an interval. We thus take
the interval hull of the result. If

${displaystyle 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

${displaystyle lambda }$

. Then, we easily get the set

${displaystyle 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

${displaystyle lambda (x)}$

associated to the previous example.

Relaxed intersection of boxes[edit]

To compute the q-relaxed intersection of m boxes of

${displaystyle 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.
^[2]
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.

Relaxed union[edit]

The q-relaxed union of

${displaystyle X_{1},dots ,X_{m}}$

is defined by

${displaystyle {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

${displaystyle bigcap ^{{0}}X_{i}=bigcap X_{i}}$

and

${displaystyle {overset {{0}}{bigcup }}X_{i}=bigcup X_{i}}$

De Morgan’s law[edit]

If

${displaystyle {overline {X}}}$

denotes the complementary set of

${displaystyle X_{i}}$

, we have

${displaystyle {overline {bigcap ^{{q}}X_{i}}}={overset {{q}}{bigcup }}{overline {X_{i}}}}$

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

As a consequence

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

Relaxation of contractors[edit]

Let

${displaystyle C_{1},dots ,C_{m}}$

be m contractors for the sets

${displaystyle X_{1},dots ,X_{m}}$

,
then

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

is a contractor for

${displaystyle X^{{q}}}$

and

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

is a contractor for

${displaystyle {overline {X}}^{{q}}}$

, where

${displaystyle {overline {C}}_{1},dots ,{overline {C}}_{m}}$

are contractors for

${displaystyle {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

${displaystyle R^{n}}$

can be computed.

Application to bounded-error estimation[edit]

The q-relaxed intersection can be used for robust localization
^[3][4]
or for tracking.
^[5]

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

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

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

where

${displaystyle pin R^{2}}$

. Assume that we have

${displaystyle f_{i}(p)in [y_{i}]}$

where

${displaystyle t_{i}}$

and

${displaystyle [y_{i}]}$

are given by the following list

${displaystyle {(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

${displaystyle lambda ^{-1}(q)}$

for different

${displaystyle q}$

are depicted on
Figure 4.

References[edit]