Algebraic Structures in Optimization

从有噪声的摄像机图像中重建三维场景是计算机视觉中的一个基本问题。在这个项目中，这些重建是作为多项式优化的问题来处理的，这在计算机视觉中不是通常的做法。通过理解这些问题的数学结构，我们的目标是推进这些问题的理论理解，并开发实用和有效的算法进行三维重建。 这个项目创造了一个不寻常的机会，从优化，代数几何和计算代数的方法应用到数学上丰富和实际上重要的应用问题。这个项目的第二个组成部分，旨在发展理论的锥因子分解的非负矩阵，特别强调半正定因子分解。这个新概念在优化、数据压缩、机器学习和统计等不同领域有许多潜在的应用。这两个项目都涉及研究生和他们在一些跨学科的数学领域的培训。 本提案中概述的主要项目是一项为期多年的努力，旨在了解计算机视觉中3D重建问题的代数几何基础。 这个过程包括两个步骤-第一个是识别约束，第二个是使用凸优化方法有效地解决这些问题。第一步需要计算代数和经典代数几何的方法，第二步依赖于优化，真实的代数几何和凸几何的技术。这些问题还提供了（计算）表示理论，多线性代数和几何的许多有趣的应用，双向交换将丰富数学和计算机视觉。学生将接受这项跨学科工作的培训，来自数学，优化和计算机视觉的几位研究人员将参与该项目。锥因子分解的项目建立在数学和计算机科学接口的一个目前蓬勃发展的领域。最初由PI和合作者为了理解凸集的扩展公式而开发，这些因子分解具有更进一步的潜力和应用。该计划是发展锥因子分解的结构和数学理论，目的是更好地理解扩展公式和其他潜在的应用。

The reconstruction of 3D-scenes from noisy camera images is a fundamental problem in computer vision. In this project, these reconstructions are approached as problems in polynomial optimization, which is not the usual practice in computer vision. By understanding the mathematical structure of these problems, we aim to advance theoretical understanding of these problems and to develop practical and efficient algorithms for 3D reconstruction. This project creates an unusual opportunity to apply methods from optimization, algebraic geometry and computational algebra to applied problems that are both mathematically rich and practically important. A second component of this project seeks to develop the theory of cone factorizations of nonnegative matrices with a special emphasis on positive semi-definite factorizations. This new concept has many potential applications to diverse areas such as optimization, data compression, machine learning and statistics. Both projects involve graduate students and their training in a number of inter-disciplinary mathematical areas. The main project outlined in this proposal is a multi-year effort to understand the algebraic geometric foundations of 3D-reconstruction problems in computer vision. This process involves two steps -- the first is to identify the constraints and the second to solve these problems efficiently using methods from convex optimization. The first step requires methods from computational algebra and classical algebraic geometry and the second step relies on techniques from optimization, real algebraic geometry and convex geometry. These problems also provide numerous fascinating applications of (computational) representation theory, multi-linear algebra, and geometry, and the two-way exchange will enrich both mathematics and computer vision. Students will be trained in this cross-disciplinary work and several researchers from mathematics, optimization, and computer vision will be involved in this project. The project on cone factorizations builds on a currently booming area at the interface of mathematics and computer science. Developed originally by the PI and collaborators for the sake of understanding extended formulations of convex sets, these factorizations have much further potential and applications. The plan is to develop the structural and mathematical theory of cone factorizations with the aim of better understanding extended formulations and other potential applications.