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
formula_1
of formula_2,
denoted by
formula_3
is the set of all
formula_4
which belong to all
formula_5
's, except
formula_6
at most.
This definition is illustrated by Figure 1.
Define
formula_7
We have
formula_8
Characterizing the q-relaxed intersection is a thus a set inversion problem.
Example.
Consider 8 intervals:
formula_9
formula_10
formula_11
formula_12
formula_13
formula_14
We have
formula_15
formula_16
formula_17
formula_18
formula_19
formula_20
formula_21
Relaxed intersection of intervals.
The relaxed intersection of intervals is not necessary an interval. We thus take
the interval hull of the result. If formula_22'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 formula_23. Then, we easily get the set
formula_24
which corresponds to a union of intervals.
We then return the
smallest interval which contains this union.
Figure 2 shows the function
formula_25
associated to the previous example.
Relaxed intersection of boxes.
To compute the "q"-relaxed intersection of "m" boxes of
formula_26, 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 formula_27 is defined by
formula_28
Note that when "q"=0, the relaxed union/intersection corresponds to
the classical union/intersection. More precisely, we have
formula_29
and
formula_30
De Morgan's law.
If formula_31 denotes the complementary set of formula_22, we have
formula_33
formula_34
As a consequence
formula_35
Relaxation of contractors.
Let formula_36 be "m" contractors for the sets formula_37,
then
formula_38
is a contractor for formula_39
and
formula_40
is a contractor for formula_41, where
formula_42
are contractors for
formula_43
Combined with a branch-and-bound algorithm such as SIVIA (Set Inversion Via Interval Analysis), the "q"-relaxed
intersection of "m" subsets of formula_2 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 "i"th model output of which is given by
formula_45
where formula_46. Assume that we have
formula_47
where formula_48 and formula_49 are given by the following list
formula_50
The sets formula_51 for different formula_6 are depicted on
Figure 4.
References.
 ;templatestyles src="Reflist/styles.css" / ;