In
geometry
Geometry (; ) is, with arithmetic, one of the oldest branches of mathematics. It is concerned with properties of space such as the distance, shape, size, and relative position of figures. A mathematician who works in the field of geometry is ...
, the Chebyshev center of a bounded set
having non-empty
interior is the center of the minimal-radius ball enclosing the entire set
, or alternatively (and non-equivalently) the center of largest inscribed ball of
.
In the field of
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 valu ...
, the Chebyshev center approach tries to find an estimator
for
given the feasibility set
, such that
minimizes the worst possible estimation error for x (e.g. best worst case).
Mathematical representation
There exist several alternative representations for the Chebyshev center.
Consider the set
and denote its Chebyshev center by
.
can be computed by solving:
:
with respect to the
Euclidean norm , or alternatively by solving:
:
Despite these properties, finding the Chebyshev center may be a hard
numerical optimization problem. For example, in the second representation above, the inner maximization is
non-convex if the set ''Q'' is not
convex
Convex or convexity may refer to:
Science and technology
* Convex lens, in optics
Mathematics
* Convex set, containing the whole line segment that joins points
** Convex polygon, a polygon which encloses a convex set of points
** Convex polytop ...
.
Properties
In
inner product spaces and two-dimensional spaces, if
is closed, bounded and convex, then the Chebyshev center is in
. In other words, the search for the Chebyshev center can be conducted inside
without loss of generality.
In other spaces, the Chebyshev center may not be in
, even if
is convex. For instance, if
is the tetrahedron formed by the
convex hull of the points (1,1,1), (-1,1,1), (1,-1,1) and (1,1,-1), then computing the Chebyshev center using the
norm yields
:
Relaxed Chebyshev center
Consider the case in which the set
can be represented as the intersection of
ellipsoids.
:
with
:
By introducing an additional matrix variable
, we can write the inner maximization problem of the Chebyshev center as:
:
where
is the
trace operator
In mathematics, the trace operator extends the notion of the restriction of a function to the boundary of its domain to "generalized" functions in a Sobolev space. This is particularly important for the study of partial differential equations with ...
and
:
:
Relaxing our demand on
by demanding
, i.e.
where
is the set of
positive semi-definite matrices, and changing the order of the min max to max min (see the references for more details), the optimization problem can be formulated as:
:
with
:
This last convex optimization problem is known as the relaxed Chebyshev center (RCC).
The RCC has the following important properties:
* The RCC is an upper bound for the exact Chebyshev center.
* The RCC is unique.
* The RCC is feasible.
Constrained least squares
It can be shown that the well-known
constrained least squares
In constrained least squares one solves a linear least squares problem with an additional constraint on the solution.
I.e., the unconstrained equation \mathbf \boldsymbol = \mathbf must be fit as closely as possible (in the least squares sens ...
(CLS) problem is a relaxed version of the Chebyshev center.
The original CLS problem can be formulated as:
:
with
:
:
It can be shown that this problem is equivalent to the following optimization problem:
:
with
:
One can see that this problem is a relaxation of the Chebyshev center (though different than the RCC described above).
RCC vs. CLS
A solution set
for the RCC is also a solution for the CLS, and thus
.
This means that the CLS estimate is the solution of a looser relaxation than that of the RCC.
Hence the CLS is an upper bound for the RCC, which is an upper bound for the real Chebyshev center.
Modeling constraints
Since both the RCC and CLS are based upon relaxation of the real feasibility set
, the form in which
is defined affects its relaxed versions. This of course affects the quality of the RCC and CLS estimators.
As a simple example consider the linear box constraints:
:
which can alternatively be written as
:
It turns out that the first representation results with an upper bound estimator for the second one, hence using it may dramatically decrease the quality of the calculated estimator.
This simple example shows us that great care should be given to the formulation of constraints when relaxation of the feasibility region is used.
Linear programming problem
This problem can be formulated as a
linear programming problem, provided that the region Q is an intersection of finitely many hyperplanes.
Given a polytope, Q, defined as follows then it can be solved via the following linear program.
:
:
See also
*
Bounding sphere
In mathematics, given a non-empty set of objects of finite extension in d-dimensional space, for example a set of points, a bounding sphere, enclosing sphere or enclosing ball for that set is an d-dimensional solid sphere containing all of the ...
*
Smallest-circle problem
The smallest-circle problem (also known as minimum covering circle problem, bounding circle problem, least bounding circle problem, smallest enclosing circle problem) is a mathematical problem of computing the smallest circle that contains all o ...
*
Circumscribed circle
In geometry, the circumscribed circle or circumcircle of a polygon is a circle that passes through all the vertices of the polygon. The center of this circle is called the circumcenter and its radius is called the circumradius.
Not every polyg ...
(covers ''circumcenter'')
*
Centre (geometry)
In geometry, a centre (or center; ) of an object is a point in some sense in the middle of the object. According to the specific definition of center taken into consideration, an object might have no center. If geometry is regarded as the stu ...
*
Centroid
In mathematics and physics, the centroid, also known as geometric center or center of figure, of a plane figure or solid figure is the arithmetic mean position of all the points in the surface of the figure. The same definition extends to any ...
References
{{Reflist
* Y. C. Eldar, A. Beck, and M. Teboulle
"A Minimax Chebyshev Estimator for Bounded Error Estimation,"IEEE Trans. Signal Process., 56(4): 1388–1397 (2007).
* A. Beck and Y. C. Eldar
"Regularization in Regression with Bounded Noise: A Chebyshev Center Approach,"SIAM J. Matrix Anal. Appl. 29 (2): 606–625 (2007).
Estimation methods
Geometric centers
Mathematical optimization