The Euclidean Distance Degree of an Algebraic Variety
Open accessThe DOI matches its Crossref record; 23 of the 23 references it cites were found in a registry or an index.
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 general point outside the variety. Focusing on varieties seen in applications, we present numerous tools for exact computations.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Introduction to Toric Varieties.
Fulton, W. (1993) · Cited by 2,778
Discriminants, Resultants, and Multidimensional Determinants
Gelfand, I. M., Kapranov, M. M., & Zelevinsky, A. V. (1994) · Birkhäuser Boston eBooks · doi:10.1007/978-0-8176-4771-1 · Cited by 2,306
Structured semidefinite programs and semialgebraic geometry methods in robustness and optimization
Parrilo, P. A. (2000) · doi:10.7907/2k6y-ch43 · Cited by 1,802
Introduction to Toric Varieties. (AM-131)
Fulton, W. (1993) · Princeton University Press eBooks · doi:10.1515/9781400882526 · Cited by 1,402
Fulton, W. (1998) · Springer · doi:10.1007/978-1-4612-1700-8 · Cited by 1,002
Hartley, R. I., & Sturm, P. (1997) · Computer Vision and Image Understanding · doi:10.1006/cviu.1997.0547 · Cited by 961
Solving Systems of Polynomial Equations
Sturmfels, B. (2002) · CBMS Regional Conference Series in Mathematics · doi:10.1090/cbms/097 · Cited by 792 · cited 1×
“The set of real points in the hypersurface V (Σ Xr ) has codimension two in the space of real s × t matrices; see [42, § 7.5].”
BackgroundInfluentialSelf-citationSingular Values and Eigenvalues of Tensors: A Variational Approach
Lim, L. (2006) · IEEE International Workshop on Computational Advances in Multi-Sensor Adaptive Processing · doi:10.1109/camap.2005.1574201 · Cited by 789 · cited 1×
“The following generalization to arbitrary tensors, due to Lim [32], is the key ingredient used in [15].”
BackgroundLectures on Algebraic Statistics
Drton, M., Sturmfels, B., & Sullivant, S. (2009) · Birkhäuser Basel eBooks · doi:10.1007/978-3-7643-8905-5 · Cited by 365 · cited 2×
“The closest rank 1 matrix in the maximum likelihood sense of [12, 27] has rational entries: it is the unique rank-one matrix with the same row sums and the same column sums as u .”
BackgroundSelf-citationTriangulation, Computer Vision and Image Understanding
Hartley, R. I. (1997) · Computer Vision and Image Understanding · Cited by 354
Hilbert, D., & Cohn-Vossen, S. (1932) · Springer eBooks · doi:10.1007/978-3-662-36685-1 · Cited by 287
The number of eigenvalues of a tensor
Cartwright, D., & Sturmfels, B. (2011) · Linear Algebra and its Applications · doi:10.1016/j.laa.2011.05.040 · Cited by 210
Self-citationHow hard is 3-view triangulation really?
Stewénius, H., Schaffalitzky, F., & Nistér, D. (2005) · IEEE/CVF International Conference on Computer Vision (ICCV) · doi:10.1109/iccv.2005.115 · Cited by 129 · cited 2×
“3 (Computer vision) This article got started with the following problem from [1,22,41].”
BackgroundMethodVarieties with small dual varieties, I
Ein, L. (1986) · Inventiones mathematicae · doi:10.1007/bf01391495 · Cited by 127 · cited 1×
“Unfortunately, it happens very rarely that X and Y are both smooth (see [13]).”
BackgroundThe Number of Singular Vector Tuples and Uniqueness of Best Rank-One Approximation of Tensors
Friedland, S., & Ottaviani, G. (2014) · Foundations of Computational Mathematics · doi:10.1007/s10208-014-9194-z · Cited by 81 · cited 6×
“In the special case p = 2, these are the equations, familiar from linear algebra, that characterize the singular vector pairs of a rectangular matrix [15, (1.1)].”
BackgroundInfluentialSelf-citationHuh, J., & Sturmfels, B. (2014) · Lecture notes in mathematics · doi:10.1007/978-3-319-04870-3_3 · Cited by 74 · cited 4×
“The closest rank 1 matrix in the maximum likelihood sense of [12, 27] has rational entries: it is the unique rank-one matrix with the same row sums and the same column sums as u .”
BackgroundInfluentialSelf-citationA Hilbert Scheme in Computer Vision
Aholt, C., Sturmfels, B., & Thomas, R. R. (2012) · Cited by 63
Self-citationA central limit theorem for the determinant of a Wigner matrix
Tao, T., & Vu, V. (2012) · Advances in Mathematics · doi:10.1016/j.aim.2012.05.006 · Cited by 57 · cited 1×
“from [43], should still help in comparing aEDdegree(X) with EDdegree(X) for large p.”
BackgroundCounting Critical Formations on a Line
Anderson, B. D. O., & Helmke, U. (2014) · SIAM Journal on Control and Optimization · doi:10.1137/120890533 · Cited by 50 · cited 4×
“This concerns a problem we learned from work of Anderson and Helmke [2].”
BackgroundMethodInfluentialThe geometric and numerical properties of duality in projective algebraic geometry
Holme, A. (1988) · manuscripta mathematica · doi:10.1007/bf01259325 · Cited by 38 · cited 4×
“4, we can now use the results described in Holme’s article [25] to express the ED degree of a smooth projective variety X in terms of its Chern classes.”
BackgroundMethodInfluentialFocal loci of algebraic varieties i
Catanese, F., & Trifogli, C. (2000) · Communications in Algebra · doi:10.1080/00927870008827202 · Cited by 22 · cited 10×
“The total space of that bundle, called normal variety in [6, 37], is precisely our projective ED correspondence PEX from Theorem 4.”
BackgroundInfluentialOn the Degree of Caustics by Reflection
Josse, A., & Pène, F. (2014) · Communications in Algebra · doi:10.1080/00927872.2012.759956 · Cited by 15 · cited 2×
“Work of Catanese, Trifogli and others [7,29] offers degree formulas for ED discriminants in various situations.”
BackgroundCaustics of Plane Curves, Their Birationality and Matrix Projections
Catanese, F. (2014) · Springer proceedings in mathematics & statistics · doi:10.1007/978-3-319-05404-9_5 · Cited by 5
Metadata
- Authors
- Draisma, J., Horobeţ, E., Ottaviani, G., Sturmfels, B., & Thomas, R. R.
- Venue
- Foundations of Computational Mathematics
- Published
- 2015-01-06
- Volume
- 16
- Issue
- 1
- Pages
- 99-149
- ISSN
- 1615-3375 (ISSN-L)
- 1615-3383
- OpenAlex
- W2124706092
- Cited by
- 198
- References
- 23
- FWCI
- 23.96
- Type
- journal article
- Language
- en
- Open access
- green
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.