×

zbMATH — the first resource for mathematics

The Euclidean distance degree of an algebraic variety. (English) Zbl 1370.51020
Given a symmetric \(n\times n\) matrix \(U\) and \(r<n,\) finding the closest (to \(U\)) symmetric matrix of rank less or equal to \(r\) is a well-known algebraic problem with important applications in various fields, including sparse optimization, image compressing, statistics and machine learning. Motivated by this problem, the authors consider the general problem of minimizing the (squared) Euclidean distance of a given point to an algebraic variety \(X\), which encompasses many other interesting applications in geometric modelling, in computer vision and in polynomial (Hurwitz) stability. The algebraic complexity of finding an optimal solution (minimizer) is measured by the so-called ED-degree (Euclidean distance degree), which refers to the set of those non-singular points of the variety \(X\) which are critical points of the squared distance function to a given point of the space. This set depends, of course, on the point of the space, but its cardinality is constant on an open dense set and defines the ED-degree. The authors give several illustrative examples and present tools for exact computations.

MSC:
51N35 Questions of classical algebraic geometry
14N10 Enumerative problems (combinatorial problems) in algebraic geometry
14M12 Determinantal varieties
90C26 Nonconvex programming, global optimization
13P25 Applications of commutative algebra (e.g., to statistics, control theory, optimization, etc.)
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] C. Aholt, B. Sturmfels and R. Thomas: A Hilbert scheme in computer vision, Canadian J. Mathematics 65 (2013), no. 5, 961-988. · Zbl 1284.13035
[2] Anderson, B; Helmke, U, Counting critical formations on a line, SIAM J. Control Optim., 52, 219-242, (2014) · Zbl 1327.93006
[3] D. Bates, J. Hauenstein, A. Sommese, and C. Wampler: Numerically Solving Polynomial Systems with Bertini, SIAM, 2013. · Zbl 1277.15007
[4] Bothmer, H-CG; Ranestad, K, A general formula for the algebraic degree in semidefinite programming, Bull. London Math. Soc., 41, 193-197, (2009) · Zbl 1185.14047
[5] Cartwright, D; Sturmfels, B, The number of eigenvectors of a tensor, Linear Algebra and its Applications, 438, 942-952, (2013) · Zbl 1277.15007
[6] F. Catanese: Caustics of plane curves, their birationality and matrix projections, in Algebraic and Complex Geometry (eds. A. Frühbis-Krüger et al), Springer Proceedings in Mathematics and Statistics 71 (2014) 109-121. · Zbl 1314.14014
[7] Catanese, F; Trifogli, C, Focal loci of algebraic varieties I, Commun. Algebra, 28, 6017-6057, (2000) · Zbl 1011.14001
[8] Chu, M; Funderlic, R; Plemmons, R, Structured low rank approximation, Linear Algebra Appl., 366, 157-172, (2003) · Zbl 1018.65057
[9] D. Cox, J. Little, and D. O’Shea: Ideals, Varieties, and Algorithms. An Introduction to Computational Algebraic Geometry and Commutative Algebra, Undergraduate Texts in Mathematics. Springer-Verlag, New York, 1992.
[10] J. Draisma and E. Horobeţ: The average number of critical rank-one approximations to a tensor, arxiv:1408.3507. · Zbl 1306.13020
[11] Draisma, J; Rodriguez, J, Maximum likelihood duality for determinantal varieties, Int. Math. Res. Not., 20, 5648-5666, (2014) · Zbl 1306.13020
[12] M. Drton, B. Sturmfels and S. Sullivant: Lectures on Algebraic Statistics, Oberwolfach Seminars, Vol 39, Birkhäuser, Basel, 2009.
[13] Ein, L, Varieties with small dual varieties, I, Invent. Math., 86, 63-74, (1986) · Zbl 0603.14025
[14] Friedland, S, Best rank one approximation of real symmetric tensors can be chosen symmetric, Front. Math. China, 8, 19-40, (2013) · Zbl 1264.15026
[15] S. Friedland and G. Ottaviani: The number of singular vector tuples and uniqueness of best rank one approximation of tensors, Found. Comput. Math., doi:10.1007/s10208-014-9194-z. · Zbl 1326.15036
[16] Faugère, J-C; Safey El Din, M; Spaenlehauer, P-J, Gröbner bases of bihomogeneous ideals generated by polynomials of bidegree (1,1): algorithms and complexity, J. Symbolic Comput., 46, 406-437, (2011) · Zbl 1226.13017
[17] W. Fulton: Introduction to Toric Varieties, Princeton University Press, 1993. · Zbl 0813.14039
[18] W. Fulton: Intersection Theory, Springer, Berlin, 1998. · Zbl 0885.14002
[19] I.M. Gelfand, M.M. Kapranov, and A.V. Zelevinsky: Discriminants, Resultants and Multidimensional Determinants, Birkhäuser, Boston, 1994. · Zbl 0827.14036
[20] D. Grayson and M. Stillman: Macaulay2, a software system for research in algebraic geometry, available at www.math.uiuc.edu/Macaulay2/. · Zbl 1300.14036
[21] D. Grayson, M. Stillman, S. Strømme, D. Eisenbud, and C. Crissman: Schubert2, computations of characteristic classes for varieties without equations, available at www.math.uiuc.edu/Macaulay2/.
[22] Hartley, R; Sturm, P, Triangulation, Computer Vision and Image Understanding: CIUV, 68, 146-157, (1997)
[23] R. Hartshorne: Algebraic Geometry, Graduate Texts in Mathematics 52, Springer-Verlag, New York, 1977.
[24] D. Hilbert and S. Cohn-Vossen: Anschauliche Geometrie, Springer-Verlag, Berlin, 1932. · Zbl 0005.11202
[25] Holme, A, The geometric and numerical properties of duality in projective algebraic geometry, Manuscripta Math., 61, 145-162, (1988) · Zbl 0657.14033
[26] Hoşten, S; Khetan, A; Sturmfels, B, Solving the likelihood equations, Foundations of Computational Mathematics, 5, 389-407, (2005) · Zbl 1097.13035
[27] J. Huh and B. Sturmfels: Likelihood geometry, in Combinatorial Algebraic Geometry (eds. Aldo Conca et al.), Lecture Notes in Mathematics 2108, Springer, (2014) 63-117. · Zbl 1328.14004
[28] N.V. Ilyushechkin: The discriminant of the characteristic polynomial of a normal matrix, Mat. Zametki 51 (1992) 16-23; translation in Math. Notes 51(3-4) (1992) 230-235.
[29] Josse, A; Pène, F, On the degree of caustics by reflection, Commun. Algebra, 42, 2442-2475, (2014) · Zbl 1300.14036
[30] A. Josse and F. Pène: On the normal class of curves and surfaces, arXiv:1402.7266. · Zbl 1226.13017
[31] M. Laurent: Cuts, matrix completions and graph rigidity, Mathematical Programming 79 (1997) 255-283. · Zbl 0887.90174
[32] L.-H. Lim: Singular values and eigenvalues of tensors: a variational approach, Proc. IEEE International Workshop on Computational Advances in Multi-Sensor Adaptive Processing (CAMSAP 05), 1 (2005), 129-132. · Zbl 1327.93006
[33] E. Miller and B. Sturmfels: Combinatorial Commutative Algebra, Graduate Texts in Mathematics 227, Springer, New York, 2004.
[34] The Online Encyclopedia of Integer Sequences, http://oeis.org/.
[35] G. Ottaviani, P.J. Spaenlehauer, B. Sturmfels: Exact solutions in structured low-rank approximation, SIAM Journal on Matrix Analysis and Applications 35 (2014) 1521-1542. · Zbl 1318.14057
[36] P.A. Parrilo: Structured Semidefinite Programs and Semialgebraic Geometry Methods in Robustness and Optimization, PhD Thesis, Caltech, Pasadena, CA, May 2000.
[37] Piene, R, Polar classes of singular varieties, Ann. Sci. École Norm. Sup.(4), 11, 247-276, (1978) · Zbl 0401.14007
[38] P. Rostalski and B. Sturmfels: Dualities, Chapter 5 in G. Blekherman, P. Parrilo and R. Thomas: Semidefinite Optimization and Convex Algebraic Geometry, pp. 203-250, MPS-SIAM Series on Optimization, SIAM, Philadelphia, 2013. · Zbl 1248.60011
[39] G. Salmon: A Treatise on the Higher Plane Curves, Dublin, 1879, available on the web at http://archive.org/details/117724690.
[40] Stegeman, A; Comon, P, Subtracting a best rank-1 approximation does not necessarily decrease tensor rank, Linear Algebra Appl., 433, 1276-1300, (2010) · Zbl 1198.15018
[41] H. Stewénius, F. Schaffalitzky, and D. Nistér: How hard is 3-view triangulation really?, Proc. International Conference on Computer Vision, Beijing, China (2005) 686-693.
[42] B. Sturmfels: Solving systems of polynomial equations, CBMS Regional Conference Series in Mathematics 97, Amer. Math. Soc., Providence, 2002. · Zbl 1101.13040
[43] Tao, T; Vu, V, A central limit theorem for the determinant of a Wigner matrix, Adv. Math., 231, 74-101, (2012) · Zbl 1248.60011
[44] J. Thomassen, P. Johansen, and T. Dokken: Closest points, moving surfaces, and algebraic geometry, Mathematical methods for curves and surfaces: Tromsø, 2004, 351-362, Mod. Methods Math., Nashboro Press, Brentwood, TN, 2005 · Zbl 1079.65516
[45] Trifogli, C, Focal loci of algebraic hypersurfaces: a general theory, Geometriae Dedicata, 70, 1-26, (1998) · Zbl 0935.14028
[46] J. Weyman: Cohomology of Vector Bundles and Syzygies, Cambridge Tracts in Mathematics, 14, Cambridge University Press, Cambridge, 2003.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.