Inner Approximations

Localization > Back | Inner Approximations | Next

Inner spherical approximation
Inner box approximation

Inner spherical approximation

We first focus on the problem of finding the largest radius of a sphere contained in the intersection. It is easy to check that a sphere of center x_0 and radius R_0 is contained in a sphere of center x_i and radius R_i if and only if the differences in the radiuses exceeds the distance between the centers:

Our inner approximation problem then becomes the SOCP

$max_{x_0,R_0} : R_0 ~:~ R_i ge R_0 + |x_i-x_0|_2, ;; i=1,ldots,m.$

We note that the measurements are inconsistent if and only if at optimum, R_0^ast < 0 . This is the same as saying that there is no point x_0 which satisfies the constraints |x_i - x_0|_2 le R_i , i=1,ldots,m .

Inner spherical approximation to the intersection. This provides an estimated point (the center of the inner shpere), with an optimistic estimate of the uncertainty around it.

Inner box approximation

We can also consider the problem of finding the largest box inside the intersection. We simply ensure that the vertices of a box with size rho are inside the intersection, and then maximize rho . In 2D or 3D, this is easy, as there is a moderate number of vertices. The problem is written

$max_{rho, x_0} : rho ~:~ |x_0 + rho v_k - x_i|_2 le R_i, ;; i=1,ldots,m, ;; k=1,ldots,K.$

In the above, is the number of vertices of the box ( K=4 in 2D, K=8 in 3D), and v_k , k=1,ldots,K are the vertices of the unit box, that is, the vectors with elements pm 1 .

Inner box approximation to the intersection. This provides an estimated point (the center of the inner box), with an optimistic estimate of the uncertainty around it. Here, the uncertainty is given as two intervals of confidence on each of the coordinates of the estimated point.