SOLUTIONS TO THE MINIMUM VARIANCE PROBLEM USING DELAUNAY TRIANGULATION

摘要

We consider the problem of minimizing the variance of a distribution supported on a finite set of points Omega in R-n given the expected value of the distribution. This produces the distribution with the least uncertainty in X, in the l(2) sense, given the support and the mean. We show that, for general norms, the support of the solution must be small in the sense that it does not contain any points from Omega in the interior of its convex hull. We then show that, under an appropriate choice of norm on the covariance, the solution is given by evaluating the tent functions associated with a Delaunay triangulation of the support at the mean. Moreover, when the Delaunay triangulation is not unique the space of solutions is the space of convex combinations of solutions associated with each possible triangulation. Solutions to special cases are presented, along with a special solution on the lattice which simultaneously minimizes three natural choices of norm.