×

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.)
PDFBibTeX XMLCite
Full Text: DOI arXiv Link

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] B. Anderson and U. Helmke: Counting critical formations on a line, SIAM J. Control Optim. 52 (2014) 219-242. · Zbl 1327.93006 · doi:10.1137/120890533
[3] D. Bates, J. Hauenstein, A. Sommese, and C. Wampler: Numerically Solving Polynomial Systems with Bertini, SIAM, 2013. · Zbl 1295.65057
[4] H.-C.G. von Bothmer and K. Ranestad: A general formula for the algebraic degree in semidefinite programming, Bull. London Math. Soc. 41 (2009) 193-197. · Zbl 1185.14047 · doi:10.1112/blms/bdn114
[5] D. Cartwright and B. Sturmfels: The number of eigenvectors of a tensor, Linear Algebra and its Applications 438 (2013) 942-952. · Zbl 1277.15007 · doi:10.1016/j.laa.2011.05.040
[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] F. Catanese and C. Trifogli: Focal loci of algebraic varieties I, Commun. Algebra 28 (2000) 6017-6057. · Zbl 1011.14001 · doi:10.1080/00927870008827202
[8] M. Chu, R. Funderlic, and R. Plemmons: Structured low rank approximation, Linear Algebra Appl. 366 (2003) 157-172. · Zbl 1018.65057 · doi:10.1016/S0024-3795(02)00505-0
[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. · Zbl 0756.13017
[10] J. Draisma and E. Horobeţ: The average number of critical rank-one approximations to a tensor, arxiv:1408.3507. · Zbl 1358.15015
[11] J. Draisma and J. Rodriguez: Maximum likelihood duality for determinantal varieties, Int. Math. Res. Not. 20 (2014) 5648-5666. · Zbl 1306.13020
[12] M. Drton, B. Sturmfels and S. Sullivant: Lectures on Algebraic Statistics, Oberwolfach Seminars, Vol 39, Birkhäuser, Basel, 2009. · Zbl 1166.13001 · doi:10.1007/978-3-7643-8905-5
[13] L. Ein: Varieties with small dual varieties, I, Invent. Math. 86(1) (1986) 63-74. · Zbl 0603.14025 · doi:10.1007/BF01391495
[14] S. Friedland: Best rank one approximation of real symmetric tensors can be chosen symmetric, Front. Math. China 8(1) (2013) 19-40. · Zbl 1264.15026 · doi:10.1007/s11464-012-0262-x
[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] J.-C. Faugère, M. Safey El Din and P.-J. Spaenlehauer: Gröbner bases of bihomogeneous ideals generated by polynomials of bidegree (1,1): algorithms and complexity, J. Symbolic Comput. 46 (2011) 406-437. · Zbl 1226.13017 · doi:10.1016/j.jsc.2010.10.014
[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 · doi:10.1007/978-1-4612-1700-8
[19] I.M. Gelfand, M.M. Kapranov, and A.V. Zelevinsky: Discriminants, Resultants and Multidimensional Determinants, Birkhäuser, Boston, 1994. · Zbl 0827.14036 · doi:10.1007/978-0-8176-4771-1
[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] R. Hartley and P. Sturm: Triangulation, Computer Vision and Image Understanding: CIUV (1997) 68(2): 146-157. · doi:10.1006/cviu.1997.0547
[23] R. Hartshorne: Algebraic Geometry, Graduate Texts in Mathematics 52, Springer-Verlag, New York, 1977. · Zbl 0367.14001
[24] D. Hilbert and S. Cohn-Vossen: Anschauliche Geometrie, Springer-Verlag, Berlin, 1932. · Zbl 0005.11202 · doi:10.1007/978-3-662-36685-1
[25] A. Holme: The geometric and numerical properties of duality in projective algebraic geometry, Manuscripta Math. 61 (1988) 145-162. · Zbl 0657.14033 · doi:10.1007/BF01259325
[26] S. Hoşten, A. Khetan, and B. Sturmfels: Solving the likelihood equations, Foundations of Computational Mathematics 5 (2005) 389-407. · Zbl 1097.13035 · doi:10.1007/s10208-004-0156-8
[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. · Zbl 0796.15009
[29] A. Josse and F. Pène: On the degree of caustics by reflection, Commun. Algebra 42 (2014), 2442-2475. · Zbl 1300.14036 · doi:10.1080/00927872.2012.759956
[30] A. Josse and F. Pène: On the normal class of curves and surfaces, arXiv:1402.7266. · Zbl 1330.14055
[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] R. Piene: Polar classes of singular varieties, Ann. Sci. École Norm. Sup. (4) 11 (1978), no. 2, 247-276. · 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] A. Stegeman and P. Comon: Subtracting a best rank-1 approximation does not necessarily decrease tensor rank, Linear Algebra Appl. 433 (2010) 1276-1300. · Zbl 1198.15018 · doi:10.1016/j.laa.2010.06.027
[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] T. Tao and V. Vu: A central limit theorem for the determinant of a Wigner matrix, Adv. Math. 231 (2012) 74-101. · Zbl 1248.60011 · doi:10.1016/j.aim.2012.05.006
[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] C. Trifogli: Focal loci of algebraic hypersurfaces: a general theory, Geometriae Dedicata 70 (1998) 1-26. · Zbl 0935.14028 · doi:10.1023/A:1005059516044
[46] J. Weyman: Cohomology of Vector Bundles and Syzygies, Cambridge Tracts in Mathematics, 14, Cambridge University Press, Cambridge, 2003. · Zbl 1075.13007 · doi:10.1017/CBO9780511546556
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.