• ### On the local stability of semidefinite relaxations(1710.04287)

Dec. 4, 2018 math.AG, math.OC
In this paper we consider a parametric family of quadratically constrained quadratic programs (QCQP) and their associated semidefinite programming (SDP) relaxations. Given a value of the parameters at which the SDP relaxation is exact, we study conditions (and quantitative bounds) under which the relaxation will continue to be exact as the parameter moves in a neighborhood around it. More generally, our results can be used to analyze SDP relaxations of polynomial optimization problems. Our framework captures several estimation problems such as low rank approximation, camera triangulation, rotation synchronization and approximate matrix completion. The SDP relaxation correctly solves these problems under noiseless observations, and our results guarantee that the relaxation will continue to solve them in the low noise regime.
• ### The Geometry of SDP-Exactness in Quadratic Optimization(1804.01796)

April 5, 2018 math.AG, cs.SC, math.OC
Consider the problem of minimizing a quadratic objective subject to quadratic equations. We study the semialgebraic region of objective functions for which this problem is solved by its semidefinite relaxation. For the Euclidean distance problem, this is a bundle of spectrahedral shadows surrounding the given variety. We characterize the algebraic boundary of this region and we derive a formula for its degree.
• ### Sampling algebraic varieties for sum of squares programs(1511.06751)

Sept. 13, 2017 math.AG, math.OC
We study sum of squares (SOS) relaxations to optimize polynomial functions over a set $V\cap R^n$, where $V$ is a complex algebraic variety. We propose a new methodology that, rather than relying on some algebraic description, represents $V$ with a generic set of complex samples. This approach depends only on the geometry of $V$, avoiding representation issues such as multiplicity and choice of generators. It also takes advantage of the coordinate ring structure to reduce the size of the corresponding semidefinite program (SDP). In addition, the input can be given as a straight-line program. Our methods are particularly appealing for varieties that are easy to sample from but for which the defining equations are complicated, such as $SO(n)$, Grassmannians or rank $k$ tensors. For arbitrary varieties we can obtain the required samples by using the tools of numerical algebraic geometry. In this way we connect the areas of SOS optimization and numerical algebraic geometry.
• ### Chordal networks of polynomial ideals(1604.02618)

Nov. 22, 2016 math.AG, cs.SC, math.AC
We introduce a novel representation of structured polynomial ideals, which we refer to as chordal networks. The sparsity structure of a polynomial system is often described by a graph that captures the interactions among the variables. Chordal networks provide a computationally convenient decomposition into simpler (triangular) polynomial sets, while preserving the underlying graphical structure. We show that many interesting families of polynomial ideals admit compact chordal network representations (of size linear in the number of variables), even though the number of components is exponentially large. Chordal networks can be computed for arbitrary polynomial systems using a refinement of the chordal elimination algorithm from [Cifuentes-Parrilo-2016]. Furthermore, they can be effectively used to obtain several properties of the variety, such as its dimension, cardinality, and equidimensional components, as well as an efficient probabilistic test for radical ideal membership. We apply our methods to examples from algebraic statistics and vector addition systems; for these instances, algorithms based on chordal networks outperform existing techniques by orders of magnitude.
• ### Exploiting chordal structure in polynomial ideals: a Gr\"obner bases approach(1411.1745)

May 9, 2016 math.AG, cs.SC, math.AC, math.OC
Chordal structure and bounded treewidth allow for efficient computation in numerical linear algebra, graphical models, constraint satisfaction and many other areas. In this paper, we begin the study of how to exploit chordal structure in computational algebraic geometry, and in particular, for solving polynomial systems. The structure of a system of polynomial equations can be described in terms of a graph. By carefully exploiting the properties of this graph (in particular, its chordal completions), more efficient algorithms can be developed. To this end, we develop a new technique, which we refer to as chordal elimination, that relies on elimination theory and Gr\"obner bases. By maintaining graph structure throughout the process, chordal elimination can outperform standard Gr\"obner basis algorithms in many cases. The reason is that all computations are done on "smaller" rings, of size equal to the treewidth of the graph. In particular, for a restricted class of ideals, the computational complexity is linear in the number of variables. Chordal structure arises in many relevant applications. We demonstrate the suitability of our methods in examples from graph colorings, cryptography, sensor localization and differential equations.
• ### An efficient tree decomposition method for permanents and mixed discriminants(1507.03046)

July 10, 2015 cs.DM, cs.DS, cs.CC
We present an efficient algorithm to compute permanents, mixed discriminants and hyperdeterminants of structured matrices and multidimensional arrays (tensors). We describe the sparsity structure of an array in terms of a graph, and we assume that its treewidth, denoted as $\omega$, is small. Our algorithm requires $O(n 2^\omega)$ arithmetic operations to compute permanents, and $O(n^2 + n 3^\omega)$ for mixed discriminants and hyperdeterminants. We finally show that mixed volume computation continues to be hard under bounded treewidth assumptions.
• ### On the degree-chromatic polynomial of a tree(1107.0060)

June 30, 2011 math.CO
The degree chromatic polynomial $Pm(G,k)$ of a graph $G$ counts the number of $k$-colorings in which no vertex has $m$ adjacent vertices of its same color. We prove Humpert and Martin's conjecture on the leading terms of the degree chromatic polynomial of a tree.