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.
Contents
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 Failed to parse (Missing <code>texvc</code> executable. Please see math/README to configure.): \lambda (x) =\text{card} \left\{ i\ |\ x\in X_{i}\right\}.
We have
Characterizing the q-relaxed intersection is a thus a set inversion problem. [1]
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(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 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. [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
The q-relaxed union of is defined by
Failed to parse (Missing <code>texvc</code> executable. Please see math/README to configure.): \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
and
Failed to parse (Missing <code>texvc</code> executable. Please see math/README to configure.): \overset{\{0\} }{\bigcup}X_{i} =\bigcup X_i
De Morgan's law
If denotes the complementary set of
, we have
Failed to parse (Missing <code>texvc</code> executable. Please see math/README to configure.): \overline{\bigcap^{\{q\}}X_i} = \overset{\{q\}}{\bigcup}\overline{X_i}
Failed to parse (Missing <code>texvc</code> executable. Please see math/README to configure.): \overline{\overset{\{q\} }{\bigcup }X_i}=\bigcap^{\{q\}}\overline{X_i}.
As a consequence
Failed to parse (Missing <code>texvc</code> executable. Please see math/README to configure.): \overline{\bigcap\limits^{\{q\}}X_i}=\overline{\overset{\{m-q-1\} }{\bigcup }X_i}=\bigcap^{\{m-q-1\}}\overline{X_i}
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 (Set Inversion Via Interval Analysis), 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 [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
where . Assume that we have
where and
are given by the following list
The sets for different
are depicted on Figure 4.
References
- ↑ Lua error in package.lua at line 80: module 'strict' not found.
- ↑ Lua error in package.lua at line 80: module 'strict' not found.
- ↑ Lua error in package.lua at line 80: module 'strict' not found.
- ↑ Lua error in package.lua at line 80: module 'strict' not found.
- ↑ Lua error in package.lua at line 80: module 'strict' not found..
- ↑ Lua error in package.lua at line 80: module 'strict' not found.
- ↑ Lua error in package.lua at line 80: module 'strict' not found.