The Euclidean distance degree of an algebraic variety (Q5963081)

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.