Relaxed intersection
≈ 5 min read
Names in other languages
No names in other languages are held for this entry yet.
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
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 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 X_{1},\dots ,X_{m} of R^{n} , denoted by X^{\{q\}}=\bigcap^{\{q\}}X_{i} is the set of all x \in R^{n} which belong to all X_{i} 's, except q at most. This definition is illustrated by Figure 1. Define \lambda (x) =\text{card} \left\{ i\ |\ x\in X_{i}\right\}. We have X^{\{q\}}=\lambda ^{-1}([m-q,m]) . Characterizing the q-relaxed intersection is a thus a set inversion problem.
Example
Consider 8 intervals: X_{1}=[1,4], X_{2}=\ [2,4], X_{3}=[2,7], X_{4}=[6,9], X_{5}=[3,4], X_{6}=[3,7]. We have X^{\{0\}} = \emptyset, X^{\{1\}}=[3,4], X^{\{2\}}=[3,4], X^{\{3\}}=[2,4] \cup [6,7], X^{\{4\}}=[2,7], X^{\{5\}}=[1,9], X^{\{6\}}=]-\infty ,\infty [.
Relaxed intersection of intervals
The relaxed intersection of intervals is not necessary an interval. We thus take the interval hull of the result. If 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 \lambda . Then, we easily get the set 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 \lambda(x) associated to the previous example.
Relaxed intersection of boxes
To compute the q-relaxed intersection of m boxes of 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. 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 X_1,\dots ,X_m is defined by \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 \bigcap^{\{0\}}X_{i} =\bigcap X_i and \overset{\{0\} }{\bigcup}X_{i} =\bigcup X_i
De Morgan's law
If \overline{X} denotes the complementary set of X_i , we have \overline{\bigcap^{\{q\}}X_i} = \overset{\{q\}}{\bigcup}\overline{X_i} \overline{\overset{\{q\} }{\bigcup }X_i}=\bigcap^{\{q\}}\overline{X_i}. As a consequence \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 C_1,\dots ,C_m be m contractors for the sets X_1,\dots ,X_m , then C([x]) =\bigcap^{\{q\}}C_i([x]). is a contractor for X^{\{q\}} and \overline{C}([x]) =\bigcap^{\{m-q-1\}}\overline{C}_i([x]) is a contractor for \overline{X}^{\{q\}} , where \overline{C}_1,\dots,\overline{C}_{m} are contractors for \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 R^{n} 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 f_i(p)=\frac{1}{\sqrt{2\pi p_2}}\exp (-\frac{(t_i-p_1)^{2}}{2p_2}) where p\in R^{2} . Assume that we have f_i(p) \in [y_i] where t_i and [y_i] are given by the following list \{ (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 \lambda^{-1}(q) for different q are depicted on Figure 4.
References
Text derived from https://en.wikipedia.org/w/index.php?oldid=1264474617 under CC BY-SA 4.0; modifications have been made.