Sums of Squares Polynomials in Optimization, Combinatorics, and Computer Vision

优化、组合学和计算机视觉中的多项式平方和

• 批准号: 1719538
• 负责人: Rekha Thomas
• 金额: $ 25万
• 依托单位: University of Washington
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2017
• 资助国家: 美国
• 起止时间: 2017-07-01 至 2021-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1719538&HistoricalAwards=false
• 关键词: Sums; Squares; Polynomials; Optimization; Combinatorics

Many questions in science and engineering can be modeled as questions in polynomial optimization, in which the goal is to find an optimal solution given a set of practical constraints on the model parameters. This field has undergone a revolution in the last two decades by incorporating novel ideas originating from several fields of mathematics and computer science. These advances have made polynomial optimization a viable tool in many applications. An important example is computer vision, for which a key goal is to estimate and characterize the three-dimensional shapes within a scene, given a set of two-dimensional images. This research project tackles such challenges by combining techniques from optimization, computer vision, and combinatorics. Special emphasis is placed on designing efficient and practical computational algorithms. Graduate students will be involved in this cross-disciplinary research project, providing the students with broad training in mathematics that intertwines theory and computation.This research investigates three topics in the field of polynomial optimization. The first project extends prior work on positive semi-definite representations of polytopes for the creation of a canonical model of realization spaces of polytopes. This research has the potential to initiate a new algebraic viewpoint of polytopes via their slack ideals, simplifying geometric results and settling longstanding questions such as understanding projective uniqueness. For the second project the focus is on algebraic vision, for which the aim is to apply techniques from algebraic geometry and polynomial optimization to questions in computer vision, with potentially important practical application. Concurrently, the study of applied formulations has the potential to inspire new mathematical theories. Research in algebraic vision continues to create strong ties to the computer vision community and will help create an intellectual exchange between mathematics and vision, benefiting both fields and providing a stimulating training environment for mathematics students looking toward careers in industry. The long-term aim of the last project is to develop the computational aspects of polynomial optimization in the presence of symmetry. Numerous problems in applications come with symmetries, and the ability to exploit this feature often determines whether or not the problem can be solved.

科学和工程中的许多问题都可以建模为多项式优化问题，其目标是在给定模型参数的一组实际约束条件下找到最优解。在过去的二十年里，这个领域经历了一场革命，融合了来自数学和计算机科学几个领域的新思想。这些进步使得多项式优化在许多应用中成为一种可行的工具。一个重要的例子是计算机视觉，它的一个关键目标是在给定一组二维图像的情况下估计和表征场景中的三维形状。本研究项目通过结合优化、计算机视觉和组合学等技术来解决这些挑战。特别强调设计高效实用的计算算法。研究生将参与这个跨学科的研究项目，为学生提供理论和计算交织在一起的广泛的数学训练。本研究探讨了多项式优化领域中的三个主题。第一个项目扩展了先前关于多面体的正半确定表示的工作，以创建多面体实现空间的规范模型。这项研究有可能通过多面体的松弛理想开创一种新的代数观点，简化几何结果，解决长期存在的问题，如理解投影唯一性。第二个项目的重点是代数视觉，其目的是将代数几何和多项式优化技术应用于计算机视觉中的问题，具有潜在的重要实际应用。同时，应用公式的研究有可能激发新的数学理论。代数视觉的研究继续与计算机视觉社区建立紧密的联系，并将有助于在数学和视觉之间建立知识交流，使这两个领域受益，并为寻求工业职业的数学学生提供一个刺激的培训环境。最后一个项目的长期目标是发展在对称存在下多项式优化的计算方面。应用程序中的许多问题都与对称性有关，利用这一特性的能力通常决定了问题能否得到解决。

项目成果

Ideals of the Multiview Variety

多视图多样性的理想

• DOI: 10.1109/tpami.2019.2950631
• 发表时间: 2021
• 期刊: IEEE Transactions on Pattern Analysis and Machine Intelligence
• 影响因子: 23.6
• 作者: Agarwal, Sameer;Pryhuber, Andrew;Thomas, Rekha R.
• 通讯作者: Thomas, Rekha R.

Simple Graph Density Inequalities with No Sum of Squares Proofs

没有平方和证明的简单图密度不等式

• DOI: 10.1007/s00493-019-4124-y
• 发表时间: 2020
• 期刊: Combinatorica
• 影响因子: 1.1
• 作者: Blekherman, Grigoriy;Raymond, Annie;Singh, Mohit;Thomas, Rekha R.
• 通讯作者: Thomas, Rekha R.

Projectively unique polytopes and toric slack ideals

• DOI: 10.1016/j.jpaa.2019.106229
• 发表时间: 2020-05-01
• 期刊: JOURNAL OF PURE AND APPLIED ALGEBRA
• 影响因子: 0.8
• 作者: Gouveia, Joao;Macchia, Antonio;Wiebe, Amy
• 通讯作者: Wiebe, Amy