Relaxed intersection

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.

The q-relaxed intersection of the m subsets

This definition is illustrated by Figure 1.

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

[1] Consider 8 intervals:

We thus take the interval hull of the result.

'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

Then, we easily get the set

which corresponds to a union of intervals.

We then return the smallest interval which contains this union.

Figure 2 shows the function

To compute the q-relaxed intersection of m boxes of

, 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.

The q-relaxed union of

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

denotes the complementary set of

be m contractors for the sets

Combined with a branch-and-bound algorithm such as SIVIA (Set Inversion Via Interval Analysis), the q-relaxed intersection of m subsets of

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

are depicted on Figure 4.

Figure 1. q -intersection of 6 sets for q =2 (red), q =3 (green), q = 4 (blue), q = 5 (yellow).
Figure 2. Set-membership function associated to the 6 intervals.
Figure 3. The red box corresponds to the 4-relaxed intersection of the 6 boxes
Figure 4. Set of all parameter vectors consistent with exactly 6-q data bars (painted red), for q=1,2,3,4,5.