Polynomial systems : graphical structure, geometry, and applications
Thesis: Ph. D., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2018.
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Language: | eng |
| Published: |
Massachusetts Institute of Technology
2018
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/1721.1/115633 |
| _version_ | 1826208263752908800 |
|---|---|
| author | Cifuentes Pardo, Diego Fernando |
| author2 | Pablo A. Parrilo. |
| author_facet | Pablo A. Parrilo. Cifuentes Pardo, Diego Fernando |
| author_sort | Cifuentes Pardo, Diego Fernando |
| collection | MIT |
| description | Thesis: Ph. D., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2018. |
| first_indexed | 2024-09-23T14:02:48Z |
| format | Thesis |
| id | mit-1721.1/115633 |
| institution | Massachusetts Institute of Technology |
| language | eng |
| last_indexed | 2024-09-23T14:02:48Z |
| publishDate | 2018 |
| publisher | Massachusetts Institute of Technology |
| record_format | dspace |
| spelling | mit-1721.1/1156332019-04-11T10:27:48Z Polynomial systems : graphical structure, geometry, and applications Cifuentes Pardo, Diego Fernando Pablo A. Parrilo. Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science. Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science. Electrical Engineering and Computer Science. Thesis: Ph. D., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2018. This electronic version was submitted by the student author. The certified thesis is available in the Institute Archives and Special Collections. Cataloged from student-submitted PDF version of thesis. Includes bibliographical references (pages 199-208). Solving systems of polynomial equations is a foundational problem in computational mathematics, that has several applications in the sciences and engineering. A closely related problem, also prevalent in applications, is that of optimizing polynomial functions subject to polynomial constraints. In this thesis we propose novel methods for both of these tasks. By taking advantage of the graphical and geometrical structure of the problem, our methods can achieve higher efficiency, and we can also prove better guarantees. Various problems in areas such as robotics, power systems, computer vision, cryptography, and chemical reaction networks, can be modeled by systems of polynomial equations, and in many cases the resulting systems have a simple sparsity structure. In the first part of this thesis we represent this sparsity structure with a graph, and study the algorithmic and complexity consequences of this graphical abstraction. Our main contribution is the introduction of a novel data structure, chordal networks, that always preserves the underlying graphical structure of the system. Remarkably, many interesting families of polynomial systems admit compact chordal network representations (of size linear in the number of variables), even though the number of components is exponentially large. Our methods outperform existing techniques by orders of magnitude in applications from algebraic statistics and vector addition systems. We then turn our attention to the study of graphical structure in the computation of matrix permanents, a classical problem from computer science. We provide a novel algorithm that requires Õ(n 2[superscript w]) arithmetic operations, where [superscript w] is the treewidth of its bipartite adjacency graph. We also investigate the complexity of some related problems, including mixed discriminants, hyperdeterminants, and mixed volumes. Although seemingly unrelated to polynomial systems, our results have natural implications on the complexity of solving sparse systems. The second part of this thesis focuses on the problem of minimizing a polynomial function subject to polynomial equality constraints. This problem captures many important applications, including Max-Cut, tensor low rank approximation, the triangulation problem, and rotation synchronization. Although these problems are nonconvex, tractable semidefinite programming (SDP) relaxations have been proposed. We introduce a methodology to derive more efficient (smaller) relaxations, by leveraging the geometrical structure of the underlying variety. The main idea behind our method is to describe the variety with a generic set of samples, instead of relying on an algebraic description. Our methods are particularly appealing for varieties that are easy to sample from, such as SO(n), Grassmannians, or rank k tensors. For arbitrary varieties we can take advantage of the tools from numerical algebraic geometry. Optimization problems from applications usually involve parameters (e.g., the data), and there is often a natural value of the parameters for which SDP relaxations solve the (polynomial) problem exactly. The final contribution of this thesis is to establish sufficient conditions (and quantitative bounds) under which SDP relaxations will continue to be exact as the parameter moves in a neighborhood of the original one. Our results can be used to show that several statistical estimation problems are solved exactly by SDP relaxations in the low noise regime. In particular, we prove this for the triangulation problem, rotation synchronization, rank one tensor approximation, and weighted orthogonal Procrustes. by Diego Cifuentes. Ph. D. 2018-05-23T15:05:38Z 2018-05-23T15:05:38Z 2018 2018 Thesis http://hdl.handle.net/1721.1/115633 1036987434 eng MIT theses are protected by copyright. They may be viewed, downloaded, or printed from this source but further reproduction or distribution in any format is prohibited without written permission. http://dspace.mit.edu/handle/1721.1/7582 208 pages application/pdf Massachusetts Institute of Technology |
| spellingShingle | Electrical Engineering and Computer Science. Cifuentes Pardo, Diego Fernando Polynomial systems : graphical structure, geometry, and applications |
| title | Polynomial systems : graphical structure, geometry, and applications |
| title_full | Polynomial systems : graphical structure, geometry, and applications |
| title_fullStr | Polynomial systems : graphical structure, geometry, and applications |
| title_full_unstemmed | Polynomial systems : graphical structure, geometry, and applications |
| title_short | Polynomial systems : graphical structure, geometry, and applications |
| title_sort | polynomial systems graphical structure geometry and applications |
| topic | Electrical Engineering and Computer Science. |
| url | http://hdl.handle.net/1721.1/115633 |
| work_keys_str_mv | AT cifuentespardodiegofernando polynomialsystemsgraphicalstructuregeometryandapplications |