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.
