AF: Small: Relaxation Techniques in Symbolic-Numeric Computation

在许多物理和工程应用中，人们需要解决“病态”或“病态”的计算问题，即输入的微小扰动实质上改变了输出的问题。该项目的目标是解决以下不适定或病态问题：多项式方程的一致超定系统的解，即方程多于未知数的系统。由于测量误差或舍入误差，输入多项式的系数只能给出有限的精度，因此实际输入系统可能不一致。这种不适定问题出现在几何建模、机器人或计算机视觉等领域。2. 低秩对称张量的分解，或等价地，齐次多项式分解成线性形式的最小幂和。同样，张量元素的小扰动将使秩增加到“一般秩”，因此分解的结构发生变化，因此问题是不适定的。在数据的二维矩阵表示不足以获得令人满意的数据分析的许多应用领域，包括图像和信号处理、代数复杂性理论、高阶统计等，都使用了低秩张量。具有根多重性的多项式方程组的解。系数的微小扰动会产生根簇，完全改变根的结构，因此这些系统是不适定的。此外，多根系统的根对系数扰动非常敏感，因此它们是病态的。这些系统给全局数值解算器带来了很大的困难，并且与这些退化系统的距离与这些解算器的计算复杂度密切相关。虽然看起来很遥远，但这些问题将使用非常相似的技术来解决：将它们转换为基于使这些问题不适定的底层几何结构的条件良好的优化问题，分析输入扰动下的输出灵敏度，并应用松弛技术来提高效率。该项目建立在PI和她的合作者之前的结果之上，进一步推进了对这些不同的符号-数字技术如何相互关联的理解，并找到了一个统一的平台，提高了它们的效率和鲁棒性。

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.