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
Estimation theory is a branch of statistics that deals with estimating the values of parameters based on measured empirical data that has a random component. The parameters describe an underlying physical setting in such a way that their value ...
,
the relaxed intersection makes it possible to be robust with respect
to some
outlier
In statistics, an outlier is a data point that differs significantly from other observations. An outlier may be due to a variability in the measurement, an indication of novel data, or it may be the result of experimental error; the latter are ...
s.
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.
![Wiki q inter def](https://upload.wikimedia.org/wikipedia/commons/7/7e/Wiki_q_inter_def.jpg)
Define
We have
Characterizing the q-relaxed intersection is a thus a
set inversion
In mathematics, set inversion is the problem of characterizing the preimage ''X'' of a set ''Y'' by a function ''f'', i.e., ''X'' = ''f''  −1(''Y'' ) = . It can also be viewed as the problem of describing the solution set of ...
problem.
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.
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
Note that when ''q''=0, the relaxed union/intersection corresponds to
the classical union/intersection. More precisely, we have
and
De Morgan's law
If
denotes the complementary set of
, we have
As a consequence
Relaxation of contractors
Let
be ''m''
contractors
A general contractor, main contractor or prime contractor is responsible for the day-to-day oversight of a construction site, management of vendors and trades, and the communication of information to all involved parties throughout the course of ...
for the sets
,
then
is a contractor for
and
is a contractor for
, where
are contractors for
Combined with a
branch-and-bound
Branch and bound (BB, B&B, or BnB) is an algorithm design paradigm for discrete and combinatorial optimization problems, as well as mathematical optimization. A branch-and-bound algorithm consists of a systematic enumeration of candidate solutio ...
algorithm such as
SIVIA
Sivia is a town in central Peru, capital of the Sivia District in Huanta Province, Ayacucho Region. It is on the west bank of the Apurímac River, about from the town of Pichari, capital of the Pichari District, La Convención Province, Cusc ...
(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
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 ''i''th model output of which is given by
where
. Assume that we have
where
and