AF: Small: Relaxation Techniques in Symbolic-Numeric Computation

In many physical and engineering applications one needs to solve ``ill-posed'' or ``ill-conditioned'' computational problems, i.e. problems such that a small perturbation of the input substantially changes the output. The objective of the project is to tackle the following ill-posed or ill-conditioned problems:

1. Solution of consistent overdetermined systems of polynomial equations, i.e. systems with more equations than unknowns. The coefficients of the input polynomials may be given only with limited accuracy due to measurement or rounding errors, thus the actual input system may be inconsistent. Such ill-posed problems arise for example in geometric modeling, robotics, or computer vision.

2. Decomposition of symmetric tensors which have low rank, or equivalently, decomposition of homogeneous polynomials into minimal sums of powers of linear forms. Again, small perturbations of the entries of the tensor will increase the rank to the ``generic rank'', so the structure of the decomposition changes, thus the problem is ill-posed. Low rank tensors have been utilized in numerous application areas where two-dimensional matrix representation of data was not sufficient for obtaining satisfying data analysis, including image and signal processing, algebraic complexity theory, higher order statistics, etc.

3. Solution of polynomial systems of equations which have root multiplicities. Small perturbations of the coefficients will create clusters of roots, completely changing the root structure, so these systems are ill-posed. Furthermore, roots of systems near ones with multiple roots are very sensitive to coefficient perturbations, thus they are ill-conditioned. These systems pose significant difficulties for global numerical solvers, and the distance from such degenerate systems is closely related to the computational complexity of such solvers.

Although distant in appearance, these problems will be tackled using very similar techniques: convert them into well-conditioned optimization problems based on the underlying geometry that made these problems ill-posed, analyze output sensitivity under perturbations of the input, and apply relaxation techniques to improve efficiency. This project builds on the PI's and her collaborators' previous results, further advancing the understanding of how these different symbolic-numeric techniques relate to each other, and finding a unified platform which enhance their efficiency and robustness.