Algebraic Structures in Optimization

最优化中的代数结构

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

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.

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