The Euclidean distance degree

J. Draisma; E. Horobet; G. Ottaviani; B. Sturmfels; R.R. Thomas

doi:10.1145/2631948.2631951

The Euclidean distance degree

J. Draisma
, E. Horobet
, G. Ottaviani
, B. Sturmfels
, R.R. Thomas

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

13 Citations (Scopus)

1 Downloads (Pure)

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 computation. Keywords: Nearest point map, Euclidean distance, polynomial optimization, computing critical points, dual variety, Chern class

Original language	English
Title of host publication	2014 Symposium on Symbolic-Numeric Computation (SNC'14, Shanghai, China, July 28-31, 2014)
Editors	L. Zhi, M. Watt
Place of Publication	New York
Publisher	Association for Computing Machinery, Inc.
Pages	9-16
ISBN (Print)	978-1-4503-2963-7
DOIs	https://doi.org/10.1145/2631948.2631951
Publication status	Published - 2014
Event	conference; 2014 Symposium on Symbolic-Numeric Computation; 2014-07-28; 2014-07-31 - Duration: 28 Jul 2014 → 31 Jul 2014

Conference

Conference	conference; 2014 Symposium on Symbolic-Numeric Computation; 2014-07-28; 2014-07-31
Period	28/07/14 → 31/07/14
Other	2014 Symposium on Symbolic-Numeric Computation

Access to Document

10.1145/2631948.2631951

Cite this

@inproceedings{db6ac138bfc74bee8ac15b5789c3a18a,

title = "The Euclidean distance degree",

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 computation. Keywords: Nearest point map, Euclidean distance, polynomial optimization, computing critical points, dual variety, Chern class",

author = "J. Draisma and E. Horobet and G. Ottaviani and B. Sturmfels and R.R. Thomas",

year = "2014",

doi = "10.1145/2631948.2631951",

language = "English",

isbn = "978-1-4503-2963-7",

pages = "9--16",

editor = "L. Zhi and M. Watt",

booktitle = "2014 Symposium on Symbolic-Numeric Computation (SNC'14, Shanghai, China, July 28-31, 2014)",

publisher = "Association for Computing Machinery, Inc.",

address = "United States",

note = "conference; 2014 Symposium on Symbolic-Numeric Computation; 2014-07-28; 2014-07-31 ; Conference date: 28-07-2014 Through 31-07-2014",

}

Draisma, J, Horobet, E, Ottaviani, G, Sturmfels, B & Thomas, RR 2014, The Euclidean distance degree. in L Zhi & M Watt (eds), 2014 Symposium on Symbolic-Numeric Computation (SNC'14, Shanghai, China, July 28-31, 2014). Association for Computing Machinery, Inc., New York, pp. 9-16, conference; 2014 Symposium on Symbolic-Numeric Computation; 2014-07-28; 2014-07-31, 28/07/14. https://doi.org/10.1145/2631948.2631951

The Euclidean distance degree. / Draisma, J.; Horobet, E.; Ottaviani, G. et al.
2014 Symposium on Symbolic-Numeric Computation (SNC'14, Shanghai, China, July 28-31, 2014). ed. / L. Zhi; M. Watt. New York: Association for Computing Machinery, Inc., 2014. p. 9-16.

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - The Euclidean distance degree

AU - Draisma, J.

AU - Horobet, E.

AU - Ottaviani, G.

AU - Sturmfels, B.

AU - Thomas, R.R.

PY - 2014

Y1 - 2014

N2 - 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 computation. Keywords: Nearest point map, Euclidean distance, polynomial optimization, computing critical points, dual variety, Chern class

AB - 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 computation. Keywords: Nearest point map, Euclidean distance, polynomial optimization, computing critical points, dual variety, Chern class

U2 - 10.1145/2631948.2631951

DO - 10.1145/2631948.2631951

M3 - Conference contribution

SN - 978-1-4503-2963-7

SP - 9

EP - 16

BT - 2014 Symposium on Symbolic-Numeric Computation (SNC'14, Shanghai, China, July 28-31, 2014)

A2 - Zhi, L.

A2 - Watt, M.

PB - Association for Computing Machinery, Inc.

CY - New York

T2 - conference; 2014 Symposium on Symbolic-Numeric Computation; 2014-07-28; 2014-07-31

Y2 - 28 July 2014 through 31 July 2014

ER -

The Euclidean distance degree

Abstract

Conference

Access to Document

Fingerprint

Cite this