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 , … , X m {\displaystyle X_{1},\dots ,X_{m}}
of R n {\displaystyle R^{n}} , denoted by
X { q } = ⋂ { q } X i {\displaystyle X^{\{q\}}=\bigcap ^{\{q\}}X_{i}}
is the set of all
x ∈ R n {\displaystyle x\in R^{n}}
which belong to all
X i {\displaystyle X_{i}}
's, except
q {\displaystyle q}
at most. This definition is illustrated by Figure 1.
Define
λ ( x ) = card { i | x ∈ X i } . {\displaystyle \lambda (x)={\text{card}}\left\{i\ |\ x\in X_{i}\right\}.}
We have
X { q } = λ − 1 ( [ m − q , m ] ) . {\displaystyle 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 ] , {\displaystyle X_{1}=[1,4],}
X 2 = [ 2 , 4 ] , {\displaystyle X_{2}=\ [2,4],}
X 3 = [ 2 , 7 ] , {\displaystyle X_{3}=[2,7],}
X 4 = [ 6 , 9 ] , {\displaystyle X_{4}=[6,9],}
X 5 = [ 3 , 4 ] , {\displaystyle X_{5}=[3,4],}
X 6 = [ 3 , 7 ] . {\displaystyle X_{6}=[3,7].}
We have
X { 0 } = ∅ , {\displaystyle X^{\{0\}}=\emptyset ,}
X { 1 } = [ 3 , 4 ] , {\displaystyle X^{\{1\}}=[3,4],}
X { 2 } = [ 3 , 4 ] , {\displaystyle X^{\{2\}}=[3,4],}
X { 3 } = [ 2 , 4 ] ∪ [ 6 , 7 ] , {\displaystyle X^{\{3\}}=[2,4]\cup [6,7],}
X { 4 } = [ 2 , 7 ] , {\displaystyle X^{\{4\}}=[2,7],}
X { 5 } = [ 1 , 9 ] , {\displaystyle X^{\{5\}}=[1,9],}
X { 6 } = ] − ∞ , ∞ [ . {\displaystyle 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 {\displaystyle 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 λ {\displaystyle \lambda } . Then, we easily get the set
X { q } = λ − 1 ( [ m − q , m ] ) {\displaystyle X^{\{q\}}=\lambda ^{-1}([m-q,m])}
… excerpt ends here. Continue reading the full article.
