[{"@context":"http:\/\/schema.org\/","@type":"BlogPosting","@id":"https:\/\/wiki.edu.vn\/en\/wiki24\/relaxed-intersection-wikipedia\/#BlogPosting","mainEntityOfPage":"https:\/\/wiki.edu.vn\/en\/wiki24\/relaxed-intersection-wikipedia\/","headline":"Relaxed intersection – Wikipedia","name":"Relaxed intersection – Wikipedia","description":"The relaxed intersection of m sets corresponds to the classical intersection between sets except that it is allowed to relax","datePublished":"2015-11-11","dateModified":"2015-11-11","author":{"@type":"Person","@id":"https:\/\/wiki.edu.vn\/en\/wiki24\/author\/lordneo\/#Person","name":"lordneo","url":"https:\/\/wiki.edu.vn\/en\/wiki24\/author\/lordneo\/","image":{"@type":"ImageObject","@id":"https:\/\/secure.gravatar.com\/avatar\/c9645c498c9701c88b89b8537773dd7c?s=96&d=mm&r=g","url":"https:\/\/secure.gravatar.com\/avatar\/c9645c498c9701c88b89b8537773dd7c?s=96&d=mm&r=g","height":96,"width":96}},"publisher":{"@type":"Organization","name":"Enzyklop\u00e4die","logo":{"@type":"ImageObject","@id":"https:\/\/wiki.edu.vn\/wiki4\/wp-content\/uploads\/2023\/08\/download.jpg","url":"https:\/\/wiki.edu.vn\/wiki4\/wp-content\/uploads\/2023\/08\/download.jpg","width":600,"height":60}},"image":{"@type":"ImageObject","@id":"https:\/\/wikimedia.org\/api\/rest_v1\/media\/math\/render\/svg\/52837aba486d2689e4cc270345b9c18590c88f46","url":"https:\/\/wikimedia.org\/api\/rest_v1\/media\/math\/render\/svg\/52837aba486d2689e4cc270345b9c18590c88f46","height":"","width":""},"url":"https:\/\/wiki.edu.vn\/en\/wiki24\/relaxed-intersection-wikipedia\/","about":["Wiki"],"wordCount":9499,"articleBody":"The relaxed intersection of m sets corresponds to the classicalintersection 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 Problemsthat 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 respectto some outliers.Table of ContentsDefinition[edit]Example[edit]Relaxed intersection of intervals[edit]Relaxed intersection of boxes[edit]Relaxed union[edit]De Morgan’s law[edit]Relaxation of contractors[edit]Application to bounded-error estimation[edit]References[edit]Definition[edit]The q-relaxed intersection of the m subsetsX1,\u2026,Xm{displaystyle X_{1},dots ,X_{m}}of Rn{displaystyle R^{n}},denoted byX{q}=\u22c2{q}Xi{displaystyle X^{{q}}=bigcap ^{{q}}X_{i}}is the set of allx\u2208Rn{displaystyle xin R^{n}}which belong to allXi{displaystyle X_{i}}‘s, exceptq{displaystyle q}at most.This definition is illustrated by Figure 1.  Figure 1. q-intersection of 6 sets for q=2 (red), q=3 (green), q= 4 (blue), q= 5 (yellow).Define\u03bb(x)=card{i\u00a0|\u00a0x\u2208Xi}.{displaystyle lambda (x)={text{card}}left{i | xin X_{i}right}.}We haveX{q}=\u03bb\u22121([m\u2212q,m]).{displaystyle X^{{q}}=lambda ^{-1}([m-q,m]).}Characterizing the q-relaxed intersection is a thus a set inversion problem.[1]Example[edit]Consider 8 intervals:X1=[1,4],{displaystyle X_{1}=[1,4],}X2=\u00a0[2,4],{displaystyle X_{2}= [2,4],}X3=[2,7],{displaystyle X_{3}=[2,7],}X4=[6,9],{displaystyle X_{4}=[6,9],}X5=[3,4],{displaystyle X_{5}=[3,4],}X6=[3,7].{displaystyle X_{6}=[3,7].}We haveX{0}=\u2205,{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]\u222a[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}=]\u2212\u221e,\u221e[.{displaystyle X^{{6}}=]-infty ,infty [.}Relaxed intersection of intervals[edit]The relaxed intersection of intervals is not necessary an interval. We thus takethe interval hull of the result. If Xi{displaystyle X_{i}}‘s are intervals, the relaxedintersection can be computed with a complexity of m.log(m) by using theMarzullo’s algorithm. It suffices tosort all lower and upper bounds of the m intervals to represent thefunction \u03bb{displaystyle lambda }. Then, we easily get the setX{q}=\u03bb\u22121([m\u2212q,m]){displaystyle X^{{q}}=lambda ^{-1}([m-q,m])}which corresponds to a union of intervals.We then return thesmallest interval which contains this union.Figure 2 shows the function\u03bb(x){displaystyle lambda (x)}associated to the previous example.  Figure 2. Set-membership function associated to the 6 intervals.Relaxed intersection of boxes[edit]To compute the q-relaxed intersection of m boxes ofRn{displaystyle 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.[2]Figure 3 provides anillustration of the 4-relaxed intersection of 6 boxes. Each point of thered box belongs to 4 of the 6 boxes.  Figure 3. The red box corresponds to the 4-relaxed intersection of the 6 boxesRelaxed union[edit]The q-relaxed union of X1,\u2026,Xm{displaystyle X_{1},dots ,X_{m}} is defined by\u22c3{q}Xi=\u22c2{m\u22121\u2212q}Xi{displaystyle {overset {{q}}{bigcup }}X_{i}=bigcap ^{{m-1-q}}X_{i}}Note that when q=0, the relaxed union\/intersection corresponds tothe classical union\/intersection. More precisely, we have\u22c2{0}Xi=\u22c2Xi{displaystyle bigcap ^{{0}}X_{i}=bigcap X_{i}}and\u22c3{0}Xi=\u22c3Xi{displaystyle {overset {{0}}{bigcup }}X_{i}=bigcup X_{i}}De Morgan’s law[edit]If X\u00af{displaystyle {overline {X}}} denotes the complementary set of Xi{displaystyle X_{i}}, we have\u22c2{q}Xi\u00af=\u22c3{q}Xi\u00af{displaystyle {overline {bigcap ^{{q}}X_{i}}}={overset {{q}}{bigcup }}{overline {X_{i}}}}\u22c3{q}Xi\u00af=\u22c2{q}Xi\u00af.{displaystyle {overline {{overset {{q}}{bigcup }}X_{i}}}=bigcap ^{{q}}{overline {X_{i}}}.}As a consequence\u22c2{q}Xi\u00af=\u22c3{m\u2212q\u22121}Xi\u00af=\u22c2{m\u2212q\u22121}Xi\u00af{displaystyle {overline {bigcap limits ^{{q}}X_{i}}}={overline {{overset {{m-q-1}}{bigcup }}X_{i}}}=bigcap ^{{m-q-1}}{overline {X_{i}}}}Relaxation of contractors[edit]Let C1,\u2026,Cm{displaystyle C_{1},dots ,C_{m}} be m contractors for the sets X1,\u2026,Xm{displaystyle X_{1},dots ,X_{m}},thenC([x])=\u22c2{q}Ci([x]).{displaystyle C([x])=bigcap ^{{q}}C_{i}([x]).}is a contractor for X{q}{displaystyle X^{{q}}}andC\u00af([x])=\u22c2{m\u2212q\u22121}C\u00afi([x]){displaystyle {overline {C}}([x])=bigcap ^{{m-q-1}}{overline {C}}_{i}([x])}is a contractor for X\u00af{q}{displaystyle {overline {X}}^{{q}}}, whereC\u00af1,\u2026,C\u00afm{displaystyle {overline {C}}_{1},dots ,{overline {C}}_{m}}are contractors forX\u00af1,\u2026,X\u00afm.{displaystyle {overline {X}}_{1},dots ,{overline {X}}_{m}.}Combined with a branch-and-bound algorithm such as SIVIA (Set Inversion Via Interval Analysis), the q-relaxedintersection of m subsets of Rn{displaystyle R^{n}} can be computed.Application to bounded-error estimation[edit]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 byfi(p)=12\u03c0p2exp\u2061(\u2212(ti\u2212p1)22p2){displaystyle f_{i}(p)={frac {1}{sqrt {2pi p_{2}}}}exp(-{frac {(t_{i}-p_{1})^{2}}{2p_{2}}})}where p\u2208R2{displaystyle pin R^{2}}.  Assume that we havefi(p)\u2208[yi]{displaystyle f_{i}(p)in [y_{i}]}where ti{displaystyle t_{i}} and [yi]{displaystyle [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,[\u22121;0.1])}{displaystyle {(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 \u03bb\u22121(q){displaystyle lambda ^{-1}(q)} for different q{displaystyle q} are depicted onFigure 4.  Figure 4. Set of all parameter vectors consistent with exactly 6-q data bars (painted red), for q=1,2,3,4,5.References[edit]^ Jaulin, L.; Walter, E.; Didrit, O. (1996). Guaranteed robust nonlinear parameter bounding (PDF). In Proceedings of CESA’96 IMACS Multiconference (Symposium on Modelling, Analysis and Simulation).^ Jaulin, L.; Walter, E. (2002). “Guaranteed robust nonlinear minimax estimation” (PDF). IEEE Transactions on Automatic Control. 47.^ Kieffer, M.; Walter, E. (2013). Guaranteed characterization of exact non-asymptotic confidence regions in nonlinear parameter estimation (PDF). In Proceedings of IFAC Symposium on Nonlinear Control Systems, Toulouse\u00a0: France (2013).^ Drevelle, V.; Bonnifait, Ph. (2011). “A set-membership approach for high integrity height-aided satellite positioning”. GPS Solutions. 15 (4).^ Langerwisch, M.; Wagner, B. (2012). “Guaranteed Mobile Robot Tracking Using Robust Interval Constraint Propagation”. Intelligent Robotics and Applications..^ Jaulin, L. (2009). “Robust set membership state estimation\u00a0; Application to Underwater Robotics” (PDF). Automatica. 45: 202\u2013206. doi:10.1016\/j.automatica.2008.06.013.^ Jaulin, L.; Kieffer, M.; Walter, E.; Meizel, D. (2002). “Guaranteed robust nonlinear estimation, with application to robot localization” (PDF). IEEE Transactions on systems, man and cybernetics; Part C Applications and Reviews. 32. Archived from the original (PDF) on 2011-04-28."},{"@context":"http:\/\/schema.org\/","@type":"BreadcrumbList","itemListElement":[{"@type":"ListItem","position":1,"item":{"@id":"https:\/\/wiki.edu.vn\/en\/wiki24\/#breadcrumbitem","name":"Enzyklop\u00e4die"}},{"@type":"ListItem","position":2,"item":{"@id":"https:\/\/wiki.edu.vn\/en\/wiki24\/relaxed-intersection-wikipedia\/#breadcrumbitem","name":"Relaxed intersection – Wikipedia"}}]}]