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.

Definition

The q-relaxed intersection of the m subsets
of,
denoted by
is the set of all
which belong to all
's, except
at most.
This definition is illustrated by Figure 1.
Define
We have
Characterizing the q-relaxed intersection is a thus a set inversion problem.

Example

Consider 8 intervals:
We have

Relaxed intersection of intervals

The relaxed intersection of intervals is not necessary an interval. We thus take
the interval hull of the result. If 's are intervals, the relaxed
intersection can be computed with a complexity of m.log 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
associated to the previous example.

Relaxed intersection of boxes

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

The q-relaxed union of is defined by
Note that when q=0, the relaxed union/intersection corresponds to
the classical union/intersection. More precisely, we have
and

De Morgan's law

If denotes the complementary set of, we have
As a consequence

Relaxation of contractors

Let be m contractors for the sets,
then
is a contractor for
and
is a contractor for, where
are contractors for
Combined with a branch-and-bound algorithm such as SIVIA, the q-relaxed
intersection of m subsets of can be computed.

Application 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
where. Assume that we have
where and are given by the following list
The sets for different are depicted on
Figure 4.