View source for Cyclohexane-1,2-dione hydrolase

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 [[Constraint satisfaction problem|Constraints Satisfaction Problems]]
that are inconsistent by [[Maximum satisfiability problem|relaxing a small number of constraints]].
When a [[set estimation|bounded-error approach]] is considered for [[parameter estimation]],
the relaxed intersection makes it possible to be robust with respect
to some [[outlier]]s.

==Definition==

The ''q''-relaxed intersection of the ''m'' subsets
<math> X_{1},\dots ,X_{m} </math>
of <math>R^{n}</math>,
denoted by
<math>
X^{\{q\}}=\bigcap^{\{q\}}X_{i}
</math>
is the set of all
<math>
x \in R^{n}
</math>
which belong to all
<math>
X_{i}
</math>
's, except
<math>q</math>
at most.
This definition is illustrated by Figure 1.

[[File:Wiki q inter def.jpg|thumb| Figure 1. ''q''-intersection of 6 sets for ''q''=2 (red), ''q''=3 (green), ''q''= 4 (blue) , ''q''= 5 (yellow).]]

Define
<math>
\lambda (x) =\text{card} \left\{ i\ |\ x\in X_{i}\right\}. 
</math>

We have
<math>
X^{\{q\}}=\lambda ^{-1}([m-q,m]) .
</math>

Characterizing the q-relaxed intersection is a thus a [[set inversion]] problem.
<ref>
{{cite book|last1=Jaulin|first1=L.|last2=Walter|first2=E.|last3=Didrit|first3=O.|
title= Guaranteed robust nonlinear parameter bounding|
year=1996|publisher=In Proceedings of CESA'96 IMACS Multiconference (Symposium on Modelling, Analysis and Simulation)|
url=http://www.ensta-bretagne.fr/jaulin/paper_CESA96.pdf}}
</ref>

==Example==

Consider 8 intervals:
<math>
X_{1}=[1,4],
</math>
<math>
X_{2}=\ [2,4],
</math>
<math>
X_{3}=[2,7],
</math>
<math>
X_{4}=[6,9],
</math>
<math>
X_{5}=[3,4],
</math>
<math>
X_{6}=[3,7].
</math>

We have

<math>
X^{\{0\}} = \emptyset, 
</math>
<math>
X^{\{1\}}=[3,4],
</math>
<math>
X^{\{2\}}=[3,4], 
</math>
<math>
X^{\{3\}}=[2,4] \cup [6,7],
</math>
<math>
X^{\{4\}}=[2,7], 
</math>
<math>
X^{\{5\}}=[1,9],
</math>
<math>
X^{\{6\}}=]-\infty ,\infty [.
</math>

==Relaxed intersection of intervals==

The relaxed intersection of intervals is not necessary an interval. We thus take
the interval hull of the result. If <math>X_i</math>'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 <math>\lambda </math>. Then, we easily get the set

<math>
X^{\{q\}}=\lambda^{-1}([m-q,m])
</math>

which corresponds to a union of intervals.
We then return the
smallest interval which contains this union.

Figure 2 shows the function
<math> \lambda(x) </math>
associated to the previous example.

[[File:Wiki qinter intervals.jpg|thumb|Figure 2. Set-membership function associated to the 6 intervals.]]

==Relaxed intersection of boxes==

To compute the ''q''-relaxed intersection of ''m'' boxes of
<math> R^{n}</math>, 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.
<ref>
{{cite journal|last1=Jaulin|first1=L.|last2=Walter|first2=E.|
title=Guaranteed robust nonlinear minimax estimation|
journal=IEEE Transaction on Automatic Control|
year=2002|volume=47|
url=http://www.ensta-bretagne.fr/jaulin/paper_qminimax.pdf}}
</ref>
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.

[[File:Wiki q inter 6box.jpg|thumb|Figure 3. The red box corresponds to the 4-relaxed intersection of the 6 boxes]]

==Relaxed union==

The ''q''-relaxed union of <math>X_1,\dots ,X_m</math> is defined by

<math>
\overset{\{q\}}{\bigcup}X_{i}=\bigcap^{\{m-1-q\}}X_i
</math>

Note that when ''q''=0, the relaxed union/intersection corresponds to
the classical union/intersection. More precisely, we have

<math>
\bigcap^{\{0\}}X_{i} =\bigcap X_i
</math>

and

<math>
\overset{\{0\} }{\bigcup}X_{i} =\bigcup X_i
</math>

==De Morgan's law==

If <math>\overline{X}</math> denotes the complementary set of <math>X_i</math>, we have

<math>
\overline{\bigcap^{\{q\}}X_i}  = \overset{\{q\}}{\bigcup}\overline{X_i}
</math>

<math>
\overline{\overset{\{q\} }{\bigcup }X_i}=\bigcap^{\{q\}}\overline{X_i}.
</math>

As a consequence

<math>
\overline{\bigcap\limits^{\{q\}}X_i}=\overline{\overset{\{m-q-1\} }{\bigcup }X_i}=\bigcap^{\{m-q-1\}}\overline{X_i}
</math>

==Relaxation of contractors==

Let <math>C_1,\dots ,C_m</math> be ''m'' [[interval contractor|contractors]] for the sets <math>X_1,\dots ,X_m </math>,
then

<math>
C([x]) =\bigcap^{\{q\}}C_i([x]).
</math>

is a contractor for <math>X^{\{q\}}</math>
and

<math>
\overline{C}([x]) =\bigcap^{\{m-q-1\}}\overline{C}_i([x]) 
</math>

is a contractor for <math>\overline{X}^{\{q\}}</math>, where

<math>
\overline{C}_1,\dots,\overline{C}_{m}
</math>

are contractors for

<math>
\overline{X}_1,\dots ,\overline{X}_m.
</math>

Combined with a [[branch-and-bound]] algorithm such as [[set inversion|SIVIA]] (Set Inversion Via Interval Analysis), the ''q''-relaxed
intersection of ''m'' subsets of <math>R^{n}</math> can be computed.

==Application to bounded-error estimation==

The ''q''-relaxed intersection can be used for robust localization
,<ref>
{{cite book|last1=Kieffer|first1=M.|last2=Walter|first2=E.|
title= Guaranteed characterization of exact non-asymptotic confidence regions in nonlinear parameter estimation|
year=2013|publisher=In Proceedings of IFAC Symposium on Nonlinear Control Systems, Toulouse : France (2013)|
url=http://hal-supelec.archives-ouvertes.fr/docs/00/81/94/88/PDF/Nolcos2013_KW.pdf}}
</ref>
for robust localization
<ref>
{{cite journal|last1=Drevelle|first1=V.|last2=Bonnifait|first2=Ph.|
title=A set-membership approach for high integrity height-aided satellite positioning|
journal=GPS Solutions|year=2011|volume=15|issue=4|url=http://hal.archives-ouvertes.fr/hal-00608133/en/}}
</ref>
or for tracking
<ref>
{{cite journal|last1=Langerwisch|first1=M.|last2=Wagner|first1=B.|
title=Guaranteed Mobile Robot Tracking Using Robust Interval Constraint Propagation|
journal=Intelligent Robotics and Applications|
year=2012}}.
</ref>

Robust observers can also be implemented using the relaxed intersections to be robust with respect to outliers.
<ref>
{{cite journal|last=Jaulin|first=L.|
title=Robust set membership state estimation ; Application to Underwater Robotics|
journal=Automatica|
year=2009|volume=45|
url=http://www.ensta-bretagne.fr/jaulin/paper_sauce_automatica.pdf}}
</ref>

We propose here a simple example
<ref>
{{cite journal|last1=Jaulin|first1=L.|last2=Kieffer|first2=M.|last3=Walter|first3=E.|last4=Meizel|first4=D.|
title=Guaranteed robust nonlinear estimation, with application to robot localization|
journal=IEEE Transactions on systems, man and cybernetics; Part C Applications and Reviews|
year=2002|volume=32|
url=http://www.ensta-bretagne.fr/jaulin/robab.pdf}}
</ref>
to illustrate the method.
Consider a model the ''i''th model output of which is given by

<math>
f_i(p)=\frac{1}{\sqrt{2\pi p_2}}\exp (-\frac{(t_i-p_1)^{2}}{2p_2}) 
</math>

where <math>p\in R^{2}</math>.  Assume that we have

<math>
f_i(p) \in [y_i]
</math>

where <math>t_i</math> and <math>[y_i]</math> are given by the following list

<math>
\{ (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])  \}
</math>

The sets <math>\lambda^{-1}(q) </math> for different <math>q</math> are depicted on
Figure 4.

[[File:Wiki qinter robab.jpg|thumb|Figure 4. Set of all parameter vectors consistent with exactly 6-q data bars (painted red), for q=1,2,3,4,5.]]

==References==
{{Reflist|2}}

[[Category:Satisfiability problems]]
[[Category:Estimation theory| ]]