Finding Nearest Points on Toric Varieties

Suppose that we are given a data point u and we wish to approximate this data point by a model X which is parameterized by monomials (this could be a statistical model, a computer vision model, etc.). That is, we wish to find the nearest point to u in our model X, with respect to the (weighted) Euclidean distance. Since our model is specified by monomials, this is an algebraic question (i.e. it concerns the zeros of collections of polynomial equations); the intrinsic algebraic complexity of solving this problem is determined by the number of complex critical points of the polynomial equation arising from computing the Euclidean distance from our given model to a general (i.e. random) point in the ambient space. We call this number of complex critical points the Euclidean distance degree; this degree gives a bound on the number of local minimums that may occur when solving our optimization problem. When X is parameterized by monomials (that is, when X is a toric variety), this upper bound may be determined entirely by use of combinatorial identities arising from a polytope specified by the powers of the monomials defining X. To make the discussion as concrete as possible, we will focus on the case where X has dimension 2.

Event Topic

Nonlinear Algebra and Statistics (NLASTATS)