Optimization Online


The Euclidean distance degree of an algebraic variety

Jan Draisma(j.draisma***at***tue.nl)
Emil Horobet(e.horobet***at***tue.nl)
Giorgio Ottaviani(ottavian***at***math.unifi.it)
Bernd Sturmfels(bernd***at***math.berkeley.edu)
Rekha R. Thomas(rrthomas***at***uw.edu)

Abstract: The nearest point map of a real algebraic variety with respect to Euclidean distance is an algebraic function. For instance, for varieties of low rank matrices, the Eckart-Young Theorem states that this map is given by the singular value decomposition. This article develops a theory of such nearest point maps from the perspective of computational algebraic geometry. The Euclidean distance degree of a variety is the number of critical points of the squared distance to a generic point outside the variety. Focusing on varieties seen in applications, we present numerous tools for exact computations.

Keywords: Euclidean distance degree, algebraic variety, duality, critical points

Category 1: Nonlinear Optimization (Constrained Nonlinear Optimization )

Category 2: Nonlinear Optimization (Unconstrained Optimization )


Download: [PDF]

Entry Submitted: 08/30/2013
Entry Accepted: 09/01/2013
Entry Last Modified: 08/30/2013

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society