Relaxed intersection

Last updated

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.

Contents

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.

Figure 1. q-intersection of 6 sets for q=2 (red), q=3 (green), q= 4 (blue), q= 5 (yellow). Wiki q inter def.jpg
Figure 1. q-intersection of 6 sets for q=2 (red), q=3 (green), q= 4 (blue), q= 5 (yellow).

Define

We have

Characterizing the q-relaxed intersection is a thus a set inversion problem. [1]

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.

Figure 2. Set-membership function associated to the 6 intervals. Wiki qinter intervals.jpg
Figure 2. Set-membership function associated to the 6 intervals.

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. [2] 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.

Figure 3. The red box corresponds to the 4-relaxed intersection of the 6 boxes Wiki q inter 6box.jpg
Figure 3. The red box corresponds to the 4-relaxed intersection 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 for the sets , then

is a contractor for and

is a contractor for , where

are contractors for

Combined with a branch-and-bound algorithm such as SIVIA (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 [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 by

where . Assume that we have

where and are given by the following list

The sets for different are depicted on Figure 4.

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

Related Research Articles

In mathematics, the Cantor set is a set of points lying on a single line segment that has a number of unintuitive properties. It was discovered in 1874 by Henry John Stephen Smith and introduced by German mathematician Georg Cantor in 1883.

In measure theory, a branch of mathematics, the Lebesgue measure, named after French mathematician Henri Lebesgue, is the standard way of assigning a measure to subsets of higher dimensional Euclidean n-spaces. For lower dimensions n = 1, 2, or 3, it coincides with the standard measure of length, area, or volume. In general, it is also called n-dimensional volume, n-volume, hypervolume, or simply volume. It is used throughout real analysis, in particular to define Lebesgue integration. Sets that can be assigned a Lebesgue measure are called Lebesgue-measurable; the measure of the Lebesgue-measurable set A is here denoted by λ(A).

<span class="mw-page-title-main">Limit inferior and limit superior</span> Bounds of a sequence

In mathematics, the limit inferior and limit superior of a sequence can be thought of as limiting bounds on the sequence. They can be thought of in a similar fashion for a function. For a set, they are the infimum and supremum of the set's limit points, respectively. In general, when there are multiple objects around which a sequence, function, or set accumulates, the inferior and superior limits extract the smallest and largest of them; the type of object and the measure of size is context-dependent, but the notion of extreme limits is invariant. Limit inferior is also called infimum limit, limit infimum, liminf, inferior limit, lower limit, or inner limit; limit superior is also known as supremum limit, limit supremum, limsup, superior limit, upper limit, or outer limit.

<span class="mw-page-title-main">Exponential distribution</span> Probability distribution

In probability theory and statistics, the exponential distribution or negative exponential distribution is the probability distribution of the distance between events in a Poisson point process, i.e., a process in which events occur continuously and independently at a constant average rate; the distance parameter could be any meaningful mono-dimensional measure of the process, such as time between production errors, or length along a roll of fabric in the weaving manufacturing process. It is a particular case of the gamma distribution. It is the continuous analogue of the geometric distribution, and it has the key property of being memoryless. In addition to being used for the analysis of Poisson point processes it is found in various other contexts.

<span class="mw-page-title-main">Linear span</span> In linear algebra, generated subspace

In mathematics, the linear span (also called the linear hull or just span) of a set S of vectors (from a vector space), denoted span(S), is defined as the set of all linear combinations of the vectors in S. For example, two linearly independent vectors span a plane. The linear span can be characterized either as the intersection of all linear subspaces that contain S, or as the smallest subspace containing S. The linear span of a set of vectors is therefore a vector space itself. Spans can be generalized to matroids and modules.

In vector calculus, Green's theorem relates a line integral around a simple closed curve C to a double integral over the plane region D bounded by C. It is the two-dimensional special case of Stokes' theorem.

In topology and related branches of mathematics, the Kuratowski closure axioms are a set of axioms that can be used to define a topological structure on a set. They are equivalent to the more commonly used open set definition. They were first formalized by Kazimierz Kuratowski, and the idea was further studied by mathematicians such as Wacław Sierpiński and António Monteiro, among others.

<span class="mw-page-title-main">Inclusion–exclusion principle</span> Counting technique in combinatorics

In combinatorics, a branch of mathematics, the inclusion–exclusion principle is a counting technique which generalizes the familiar method of obtaining the number of elements in the union of two finite sets; symbolically expressed as

In mathematics, and especially differential geometry and gauge theory, a connection is a device that defines a notion of parallel transport on the bundle; that is, a way to "connect" or identify fibers over nearby points. A principal G-connection on a principal G-bundle over a smooth manifold is a particular type of connection which is compatible with the action of the group .

In mathematics, a canonical basis is a basis of an algebraic structure that is canonical in a sense that depends on the precise context:

In mathematics, the Vitali–Hahn–Saks theorem, introduced by Vitali (1907), Hahn (1922), and Saks (1933), proves that under some conditions a sequence of measures converging point-wise does so uniformly and the limit is also a measure.

In mathematics, the Poincaré metric, named after Henri Poincaré, is the metric tensor describing a two-dimensional surface of constant negative curvature. It is the natural metric commonly used in a variety of calculations in hyperbolic geometry or Riemann surfaces.

In theoretical physics, there are many theories with supersymmetry (SUSY) which also have internal gauge symmetries. Supersymmetric gauge theory generalizes this notion.

In mathematics, in particular in measure theory, a content is a real-valued function defined on a collection of subsets such that

In mathematics, the spectral theory of ordinary differential equations is the part of spectral theory concerned with the determination of the spectrum and eigenfunction expansion associated with a linear ordinary differential equation. In his dissertation, Hermann Weyl generalized the classical Sturm–Liouville theory on a finite closed interval to second order differential operators with singularities at the endpoints of the interval, possibly semi-infinite or infinite. Unlike the classical case, the spectrum may no longer consist of just a countable set of eigenvalues, but may also contain a continuous part. In this case the eigenfunction expansion involves an integral over the continuous part with respect to a spectral measure, given by the Titchmarsh–Kodaira formula. The theory was put in its final simplified form for singular differential equations of even degree by Kodaira and others, using von Neumann's spectral theorem. It has had important applications in quantum mechanics, operator theory and harmonic analysis on semisimple Lie groups.

<span class="mw-page-title-main">Poisson distribution</span> Discrete probability distribution

In probability theory and statistics, the Poisson distribution is a discrete probability distribution that expresses the probability of a given number of events occurring in a fixed interval of time or space if these events occur with a known constant mean rate and independently of the time since the last event. It is named after French mathematician Siméon Denis Poisson. The Poisson distribution can also be used for the number of events in other specified interval types such as distance, area, or volume. It plays an important role for discrete-stable distributions.

In mathematics, especially measure theory, a set function is a function whose domain is a family of subsets of some given set and that (usually) takes its values in the extended real number line which consists of the real numbers and

In mathematics, a càdlàg, RCLL, or corlol function is a function defined on the real numbers that is everywhere right-continuous and has left limits everywhere. Càdlàg functions are important in the study of stochastic processes that admit jumps, unlike Brownian motion, which has continuous sample paths. The collection of càdlàg functions on a given domain is known as Skorokhod space.

In statistics, a random vector x is classically represented by a probability density function. In a set-membership approach or set estimation, x is represented by a set X to which x is assumed to belong. This means that the support of the probability distribution function of x is included inside X. On the one hand, representing random vectors by sets makes it possible to provide fewer assumptions on the random variables and dealing with nonlinearities is easier. On the other hand, a probability distribution function provides a more accurate information than a set enclosing its support.

In algebraic geometry, the problem of residual intersection asks the following:

References

  1. 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).
  2. Jaulin, L.; Walter, E. (2002). "Guaranteed robust nonlinear minimax estimation" (PDF). IEEE Transactions on Automatic Control. 47 (11): 1857–1864. doi:10.1109/TAC.2002.804479.
  3. 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 : France (2013).
  4. Drevelle, V.; Bonnifait, Ph. (2011). "A set-membership approach for high integrity height-aided satellite positioning". GPS Solutions. 15 (4): 357–368. doi:10.1007/s10291-010-0195-3. S2CID   121728552.
  5. Langerwisch, M.; Wagner, B. (2012). "Guaranteed Mobile Robot Tracking Using Robust Interval Constraint Propagation". Intelligent Robotics and Applications..
  6. Jaulin, L. (2009). "Robust set membership state estimation; Application to Underwater Robotics" (PDF). Automatica. 45: 202–206. doi:10.1016/j.automatica.2008.06.013.
  7. 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 (4): 374–381. doi:10.1109/TSMCC.2002.806747. S2CID   17436801. Archived from the original (PDF) on 2011-04-28.