Source author record

J. William Helton

J. William Helton appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record

Catalog footprint

What is connected

23works
9topics
4close collaborators

Actions

Connect this record

Log in to claim

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

23 published item(s)

preprint2022arXiv

Empirical properties of optima in free semidefinite programs

Semidefinite programming is based on optimization of linear functionals over convex sets defined by linear matrix inequalities, namely, inequalities of the form $$L_A(X)=I-A_1X_1-\dots-A_g X_g\succeq0.$$ Here the $X_j$ are real numbers and the set of solutions is called a spectrahedron. These inequalities make sense when the $X_i$ are symmetric matrices of any size, $n\times n$, and enter the formula though tensor product $A_i\otimes X_i$: The solution set of $L_A(X)\succeq0$ is called a free spectrahedron since it contains matrices of all sizes and the defining ``linear pencil" is ``free" of the sizes of the matrices. In this article, we report on empirically observed properties of optimizers obtained from optimizing linear functionals over free spectrahedra restricted to matrices $X_i$ of fixed size $n\times n$. The optimizers we find are always classical extreme points. Surprisingly, in many reasonable parameter ranges, over 99.9\% are also free extreme points. Moreover, the dimension of the active constraint, $\ker(L_A(X^\ell))$, is about twice what we expected. Another distinctive pattern regards reducibility of optimizing tuples $(X_1^\ell,\dots,X_g^\ell)$. We give an algorithm for representing elements of a free spectrahedron as matrix convex combinations of free extreme points; these representations satisfy a very low bound on the number of free extreme points neede

preprint2022arXiv

Satisfiability Phase Transtion for Random Quantum 3XOR Games

Recent results showed it was possible to determine if a modest size 3XOR game has a perfect quantum strategy. We build on these and give an explicit polynomial time algorithm which constructs such a perfect strategy or refutes its existence. This new tool lets us numerically study the behavior of randomly generated 3XOR games with large numbers of questions. A key issue is: how common are pseudotelephathy games (games with perfect quantum strategies but no perfect classical strategies)? Our experiments strongly indicate that the probability of a randomly generated game being pseudotelpathic stays far from 1, indeed it is bounded below 0.15. We also find strong evidence that randomly generated 3XOR games undergo both a quantum and classical "phase transition", transitioning from almost certainly perfect to almost certainly imperfect as the ratio of number of clauses ($m$) to number of questions ($n$) increases. The locations of these two phase transitions appear to coincide at $m/n \approx 2.74$.

preprint2021arXiv

Efficient evaluation of noncommutative polynomials using tensor and noncommutative Waring decompositions

This paper analyses a Waring type decomposition of a noncommuting (NC) polynomial $p$ with respect to the goal of evaluating $p$ efficiently on tuples of matrices. Such a decomposition can reduce the number of matrix multiplications needed to evaluate a noncommutative polynomial and is valuable when a single polynomial must be evaluated on many matrix tuples. In pursuit of this goal we examine a noncommutative analog of the classical Waring problem and various related decompositions. For example, we consider a "Waring decomposition" in which each product of linear terms is actually a power of a single linear NC polynomial or more generally a power of a homogeneous NC polynomial. We describe how NC polynomials compare to commutative ones with regard to these decompositions, describe a method for computing the NC decompositions and compare the effect of various decompositions on the speed of evaluation of generic NC polynomials.

preprint2020arXiv

Factorization of noncommutative polynomials and Nullstellensätze for the free algebra

This article gives a class of Nullstellensätze for noncommutative polynomials. The singularity set of a noncommutative polynomial $f=f(x_1,\dots,x_g)$ is $Z(f)=(Z_n(f))_n$, where $Z_n(f)=\{X \in M_n^g: \det f(X) = 0\}.$ The first main theorem of this article shows that the irreducible factors of $f$ are in a natural bijective correspondence with irreducible components of $Z_n(f)$ for every sufficiently large $n$. With each polynomial $h$ in $x$ and $x^*$ one also associates its real singularity set $Z^{re}(h)=\{X: \det h(X,X^*)=0\}$. A polynomial $f$ which depends on $x$ alone (no $x^*$ variables) will be called analytic. The main Nullstellensatz proved here is as follows: for analytic $f$ but for $h$ dependent on possibly both $x$ and $x^*$, the containment $Z(f) \subseteq Z^{re}(h)$ is equivalent to each factor of $f$ being "stably associated" to a factor of $h$ or of $h^*$. For perspective, classical Hilbert type Nullstellensätze typically apply only to analytic polynomials $f,h $, while real Nullstellensätze typically require adjusting the functions by sums of squares of polynomials (sos). Since the above "algebraic certificate" does not involve a sos, it seems justified to think of this as the natural determinantal Hilbert Nullstellensatz. An earlier paper of the authors (Adv. Math. 331 (2018) 589-626) obtained such a theorem for special classes of analytic polynomials $f$ and $h$. This paper requires few hypotheses and hopefully brings this type of Nullstellensatz to near final form. Finally, the paper gives a Nullstellensatz for zeros $V(f)=\{X: f(X,X^*)=0\}$ of a hermitian polynomial $f$, leading to a strong Positivstellensatz for quadratic free semialgebraic sets by the use of a slack variable.

preprint2019arXiv

Arveson extreme points span free spectrahedra

Let $ SM_n(\mathbb{R})^g$ denote $g$-tuples of $n \times n$ real symmetric matrices. Given tuples $X=(X_1, \dots, X_g) \in SM_{n_1}(\mathbb{R})^g$ and $Y=(Y_1, \dots, Y_g) \in SM_{n_2}(\mathbb{R})^g$, a matrix convex combination of $X$ and $Y$ is a sum of the form \[ V_1^* XV_1+V_2^* Y V_2 \quad \quad \quad V_1^* V_1+V_2^* V_2=I_n \] where $V_1:\mathbb{R}^n \to \mathbb{R}^{n_1}$ and $V_2:\mathbb{R}^n \to \mathbb{R}^{n_2}$ are contractions. Matrix convex sets are sets which are closed under matrix convex combinations. A key feature of matrix convex combinations is that the $g$-tuples $X, Y$, and $V_1^* XV_1+V_2^* Y V_2$ do not need to have the same size. As a result, matrix convex sets are a dimension free analog of convex sets. While in the classical setting there is only one notion of an extreme point, there are three main notions of extreme points for matrix convex sets: ordinary, matrix, and absolute extreme points. Absolute extreme points are closely related to the classical Arveson boundary. A central goal in the theory of matrix convex sets is to determine if one of these types of extreme points for a matrix convex set minimally recovers the set through matrix convex combinations. This article shows that every real compact matrix convex set which is defined by a linear matrix inequality is the matrix convex hull of its absolute extreme points, and that the absolute extreme points are the minimal set with this property. Furthermore, we give an algorithm which expresses a tuple as a matrix convex combination of absolute extreme points with optimal bounds. Similar results hold when working over the field of complex numbers rather than the reals.

preprint2019arXiv

Bianalytic free maps between spectrahedra and spectraballs

Linear matrix inequalities (LMIs) are ubiquitous in real algebraic geometry, semidefinite programming, control theory and signal processing. LMIs with (dimension free) matrix unknowns are central to the theories of completely positive maps and operator algebras, operator systems and spaces, and serve as the paradigm for matrix convex sets. The matricial feasibility set of an LMI is called a free spectrahedron. In this article, the bianalytic maps between a very general class of ball-like free spectrahedra (examples of which include row or column contractions, and tuples of contractions) and arbitrary free spectrahedra are characterized and seen to have an elegant algebraic form. They are all highly structured rational maps. In the case that both the domain and codomain are ball-like, these bianalytic maps are explicitly determined and the article gives necessary and sufficient conditions for the existence of such a map with a specified value and derivative at a point. In particular, this leads to a classification of automorphism groups of ball-like free spectrahedra. The results depend on a novel free Nullstellensatz, established only after new tools in free analysis are developed and applied to obtain fine detail, geometric in nature locally and algebraic in nature globally, about the boundary of ball-like free spectrahedra.

preprint2019arXiv

Plurisubharmonic Noncommutative Rational Functions

A noncommutative (nc) function in $x_1,\dots,x_g,x_1^*,\dots,x_g$ is called plurisubharmonic (plush) if its nc complex Hessian takes only positive semidefinite values on an nc neighborhood of 0. The main result of this paper shows that an nc rational function is plush if and only if it is a composite of a convex rational function with an analytic (no $x_j^*$) rational function. The proof is entirely constructive. Further, a simple computable necessary and sufficient condition for an nc rational function to be plush is given in terms of its minimal realization.

preprint2015arXiv

Convex entire noncommutative functions are polynomials of degree two or less

This paper concerns matrix "convex" functions of (free) noncommuting variables, $x = (x_1, \ldots, x_g)$. Helton and McCullough showed that a polynomial in $x$ which is matrix convex is of degree two or less. We prove a more general result: that a function of $x$ that is matrix convex near $0$ and also that is "analytic" in some neighborhood of the set of all self-adjoint matrix tuples is in fact a polynomial of degree two or less. More generally, we prove that a function $F$ in two classes of noncommuting variables, $a = (a_1, \ldots, a_{\tilde{g}})$ and $x = (x_1, \ldots, x_g)$ that is "analytic" and matrix convex in $x$ on a "noncommutative open set" in $a$ is a polynomial of degree two or less.

preprint2014arXiv

Free Semidefinite Representation of Matrix Power Functions

Consider the matrix power function X^p defined over the cone of positive definite matrices S^{n}_{++}. It is known that X^p is convex over S^{n}_{++} if p is in [-1,0] or [1,2] and X^p is concave over S^{n}_{++} if p is in [0,1]. We show that the hypograph of X^p admits a free semidefinite representation if p in [0,1] is rational, and the epigraph of X^p admits a free semidefinite representation if p in [-1,0] or [1,2] is rational.

preprint2013arXiv

Free Convex Algebraic Geometry

This chapter is a tutorial on techniques and results in free convex algebraic geometry and free real algebraic geometry (RAG). The term free refers to the central role played by algebras of noncommutative polynomials R<x> in free (freely noncommuting) variables x=(x_1,...,x_g). The subject pertains to problems where the unknowns are matrices or Hilbert space operators as arise in linear systems engineering and quantum information theory. The subject of free RAG flows in two branches. One, free positivity and inequalities is an analog of classical real algebraic geometry, a theory of polynomial inequalities embodied in algebraic formulas called Positivstellensätze; often free Positivstellensätze have cleaner statements than their commutative counterparts. Free convexity, the second branch of free RAG, arose in an effort to unify a torrent of ad hoc optimization techniques which came on the linear systems engineering scene in the mid 1990's. Mathematically, much as in the commutative case, free convexity is connected with free positivity through the second derivative: A free polynomial is convex if and only if its Hessian is positive. However, free convexity is a very restrictive condition, for example, free convex polynomials have degree 2 or less. This article describes for a beginner techniques involving free convexity. As such it also serves as a point of entry into the larger field of free real algebraic geometry.

preprint2012arXiv

A Semidefinite Approach for Truncated K-Moment Problems

A truncated moment sequence (tms) of degree d is a vector indexed by monomials whose degree is at most d. Let K be a semialgebraic set.The truncated K-moment problem (TKMP) is: when does a tms y admit a positive Borel measure supported? This paper proposes a semidefinite programming (SDP) approach for solving TKMP. When K is compact, we get the following results: whether a tms y of degree d admits a K-measure or notcan be checked via solving a sequence of SDP problems; when y admits no K-measure, a certificate will be given; when y admits a K-measure, a representing measure for y would be obtained from solving the SDP under some necessary and some sufficient conditions. Moreover, we also propose a practical SDP method for finding flat extensions, which in our numerical experiments always finds a finitely atomic representing measure for a tms when it admits one.

preprint2012arXiv

Free analysis, convexity and LMI domains

This paper concerns free analytic maps on noncommutative domains. These maps are free analogs of classical holomorphic functions in several complex variables, and are defined in terms of noncommuting variables amongst which there are no relations - they are free variables. Free analytic maps include vector-valued polynomials in free (noncommuting) variables and form a canonical class of mappings from one noncommutative domain D in say g variables to another noncommutative domain D' in g' variables. Motivated by determining the possibilities for mapping a nonconvex noncommutative domain to a convex noncommutative domain, this article focuses on rigidity results for free analytic maps. Those obtained to date, parallel and are often stronger than those in several complex variables. For instance, a proper free analytic map between noncommutative domains is one-one and, if g=g', free biholomorphic. Making its debut here is a free version of a theorem of Braun-Kaup-Upmeier: between two freely biholomorphic bounded circular noncommutative domains there exists a linear biholomorphism. An immediate consequence is the following nonconvexification result: if two bounded circular noncommutative domains are freely biholomorphic, then they are either both convex or both not convex. Because of their roles in systems engineering, linear matrix inequalities (LMIs) and noncommutative domains defined by an LMI (LMI domains) are of particular interest. As a refinement of above the nonconvexification result, if a bounded circular noncommutative domain D is freely biholomorphic to a bounded circular LMI domain, then D is itself an LMI domain.

preprint2012arXiv

Free convex sets defined by rational expressions have LMI representations

Suppose p is a symmetric matrix whose entries are polynomials in freely noncommutating variables and p(0) is positive definite. Let D(p) denote the component of zero of the set of those g-tuples X of symmetric matrices (of the same size) such that p(X) is positive definite. By a previous result of the authors, if D(p) is convex and bounded, then D(p) can be described as the set of all solutions to a linear matrix inequality (LMI). This article extends that result from matrices of polynomials to matrices of rational functions in free variables. As a refinement of a theorem of Kaliuzhnyi-Verbovetskyi and Vinnikov, it is also shown that a minimal symmetric descriptor realization r for a symmetric free matrix-valued rational function R in g freely noncommuting variables precisely encodes the singularities of the rational function. This singularities result is an important ingredient in the proof of the LMI representation theorem stated above.

preprint2012arXiv

Non-commutative varieties with curvature having bounded signature

The signature(s) of the curvature of the zero set V of a free (non-commutative) polynomial is defined as the number of positive and negative eigenvalues of the non-commutative second fundamental form on V determined by p. With some natural hypotheses, the degree of p is bounded in terms of the signature. In particular, if one of the signatures is zero, then the degree of p is at most two.

preprint2011arXiv

Every free basic convex semi-algebraic set has an LMI representation

The (matricial) solution set of a Linear Matrix Inequality (LMI) is a convex basic non-commutative semi-algebraic set. The main theorem of this paper is a converse, a result which has implications for both semidefinite programming and systems engineering. For p(x) a non-commutative polynomial in free variables x= (x1, ... xg) we can substitute a tuple of symmetric matrices X= (X1, ... Xg) for x and obtain a matrix p(X). Assume p is symmetric with p(0) invertible, let Ip denote the set {X: p(X) is an invertible matrix}, and let Dp denote the component of Ip containing 0. THEOREM: If the set Dp is uniformly bounded independent of the size of the matrix tuples, then Dp has an LMI representation if and only if it is convex. Linear engineering systems problems are called "dimension free" if they can be stated purely in terms of a signal flow diagram with L2 performance measures, e.g., H-infinity control. Conjecture: A dimension free problem can be made convex if and only it can be made into an LMI. The theorem here settles the core case affirmatively.

preprint2011arXiv

Noncommutative Plurisubharmonic Polynomials Part I: Global Assumptions

We consider symmetric polynomials, p, in the noncommutative free variables (x_1, x_2, ..., x_g). We define the noncommutative complex hessian of p and we call a noncommutative symmetric polynomial noncommutative plurisubharmonic if it has a noncommutative complex hessian that is positive semidefinite when evaluated on all tuples of n x n matrices for every size n. In this paper, we show that the symmetric noncommutative plurisubharmonic polynomials are precisely the noncommutative convex polynomials with a noncommutative analytic change of variables; i.e., a noncommutative symmetric polynomial, p, is noncommutative plurisubharmonic if and only if it has the form p = \sum f_j^T f_j + \sum k_j k_j^T + F + F^T where the sums are finite and f_j, k_j, F are all noncommutative analytic. We also present a theory of noncommutative integration for noncommutative polynomials and we prove a noncommutative version of the Frobenius theorem. A subsequent paper by Greene proves that if the noncommutative complex hessian of p takes positive semidefinite values on a "noncommutative open set" then the noncommutative complex hessian takes positive semidefinite values on all matrix tuples. Thus, p has the form above. The proof in the subsequent paper draws on most of the theorems in this paper together with a very different technique involving representations of noncommutative quadratic functions.

preprint2011arXiv

Semidefinite programming in matrix unknowns which are dimension free

One of the main applications of semidefinite programming lies in linear systems and control theory. Many problems in this subject, certainly the textbook classics, have matrices as variables, and the formulas naturally contain non-commutative polynomials in matrices. These polynomials depend only on the system layout and do not change with the size of the matrices involved, hence such problems are called "dimension-free". Analyzing dimension-free problems has led to the development recently of a non-commutative (nc) real algebraic geometry (RAG) which, when combined with convexity, produces dimension-free Semidefinite Programming. This article surveys what is known about convexity in the non-commutative setting and nc SDP and includes a brief survey of nc RAG. Typically, the qualitative properties of the non-commutative case are much cleaner than those of their scalar counterparts - variables in R^g. Indeed we describe how relaxation of scalar variables by matrix variables in several natural situations results in a beautiful structure.

preprint2010arXiv

Analytic mappings between noncommutative pencil balls

In this paper, we analyze problems involving matrix variables for which we use a noncommutative algebra setting. To be more specific, we use a class of functions (called NC analytic functions) defined by power series in noncommuting variables and evaluate these functions on sets of matrices of all dimensions; we call such situations dimension-free. In an earlier paper we characterized NC analytic maps that send dimension-free matrix balls to dimension-free matrix balls and carry the boundary to the boundary; such maps we call "NC ball maps". In this paper we turn to a more general dimension-free ball B_L, called a "pencil ball", associated with a homogeneous linear pencil L(x):= A_1 x_1 + ... + A_m x_m, where A_j are complex matrices. For an m-tuple X of square matrices of the same size, define L(X):=\sum A_j \otimes X_j and let B_L denote the set of all such tuples X satisfying ||L(X)||<1. We study the generalization of NC ball maps to these pencil balls B_L, and call them "pencil ball maps". We show that every B_L has a minimal dimensional (in a certain sense) defining pencil L'. Up to normalization, a pencil ball map is the direct sum of L' with an NC analytic map of the pencil ball into the ball. That is, pencil ball maps are simple, in contrast to the classical result of D'Angelo on such analytic maps in C^m. To prove our main theorem, this paper uses the results of our previous paper mentioned above plus entirely different techniques, namely, those of completely contractive maps.

preprint2010arXiv

Proper Analytic Free Maps

This paper concerns analytic free maps. These maps are free analogs of classical analytic functions in several complex variables, and are defined in terms of non-commuting variables amongst which there are no relations - they are free variables. Analytic free maps include vector-valued polynomials in free (non-commuting) variables and form a canonical class of mappings from one non-commutative domain D in say g variables to another non-commutative domain D' in g' variables. As a natural extension of the usual notion, an analytic free map is proper if it maps the boundary of D into the boundary of D'. Assuming that both domains contain 0, we show that if f:D->D' is a proper analytic free map, and f(0)=0, then f is one-to-one. Moreover, if also g=g', then f is invertible and f^(-1) is also an analytic free map. These conclusions on the map f are the strongest possible without additional assumptions on the domains D and D'.

preprint2009arXiv

Sign patterns for chemical reaction networks

Most differential equations found in chemical reaction networks (CRNs) have the form $dx/dt=f(x)= Sv(x)$, where $x$ lies in the nonnegative orthant, where $S$ is a real matrix (the stoichiometric matrix) and $v$ is a column vector consisting of real-valued functions having a special relationship to $S$. Our main interest will be in the Jacobian matrix, $f'(x)$, of $f(x)$, in particular in whether or not each entry $f'(x)_{ij}$ has the same sign for all $x$ in the orthant, i.e., the Jacobian respects a sign pattern. In other words species $x_j$ always acts on species $x_i$ in an inhibitory way or its action is always excitatory. In Helton, Klep, Gomez we gave necessary and sufficient conditions on the species-reaction graph naturally associated to $S$ which guarantee that the Jacobian of the associated CRN has a sign pattern. In this paper, given $S$ we give a construction which adds certain rows and columns to $S$, thereby producing a stoichiometric matrix $\widehat S$ corresponding to a new CRN with some added species and reactions. The Jacobian for this CRN based on $\hat S$ has a sign pattern. The equilibria for the $S$ and the $\hat S$ based CRN are in exact one to one correspondence with each equilibrium $e$ for the original CRN gotten from an equilibrium $\hat e$ for the new CRN by removing its added species. In our construction of a new CRN we are allowed to choose rate constants for the added reactions and if we choose them large enough the equilibrium $\hat e$ is locally asymptotically stable if and only if the equilibrium $e$ is locally asymptotically stable. Further properties of the construction are shown, such as those pertaining to conserved quantities and to how the deficiencies of the two CRNs compare.

preprint2008arXiv

Determinant Expansions of Signed Matrices and of Certain Jacobians

This paper treats two topics: matrices with sign patterns and Jacobians of certain mappings. The main topic is counting the number of plus and minus coefficients in the determinant expansion of sign patterns and of these Jacobians. The paper is motivated by an approach to chemical networks initiated by Craciun and Feinberg. We also give a graph-theoretic test for determining when the Jacobian of a chemical reaction dynamics has a sign pattern.

preprint2008arXiv

Noncommutative ball maps

In this paper, we analyze problems involving matrix variables for which we use a noncommutative algebra setting. To be more specific, we use a class of functions (called NC analytic functions) defined by power series in noncommuting variables and evaluate these functions on sets of matrices of all dimensions; we call such situations dimension-free. These types of functions have recently been used in the study of dimension-free linear system engineering problems. In this paper we characterize NC analytic maps that send dimension-free matrix balls to dimension-free matrix balls and carry the boundary to the boundary; such maps we call "NC ball maps". We find that up to normalization, an NC ball map is the direct sum of the identity map with an NC analytic map of the ball into the ball. That is, "NC ball maps" are very simple, in contrast to the classical result of D'Angelo on such analytic maps over C. Another mathematically natural class of maps carries a variant of the noncommutative distinguished boundary to the boundary, but on these our results are limited. We shall be interested in several types of noncommutative balls, conventional ones, but also balls defined by constraints called Linear Matrix Inequalities (LMI). What we do here is a small piece of the bigger puzzle of understanding how LMIs behave with respect to noncommutative change of variables.