Klep, Igor


Suchergebnisse Publikationen

Gerade angezeigt 1 - 10 von 20
Vorschaubild nicht verfügbar

Globally trace-positive noncommutative polynomials and the unbounded tracial moment problem

2022-10, Klep, Igor, Scheiderer, Claus, Volčič, Jurij

A noncommutative (nc ) polynomial is called (globally) trace-positive if its evaluation at any tuple of operators in a tracial von Neumann algebra has nonnegative trace. Such polynomials emerge as trace inequalities in several matrix or operator variables, and are widespread in mathematics and physics. This paper delivers the first Positivstellensatz for global trace positivity of nc polynomials. Analogously to Hilbert’s 17th problem in real algebraic geometry, trace-positive nc polynomials are shown to be weakly sums of hermitian squares and commutators of regular nc rational functions. In two variables, this result is strengthened further using a new sum-of-squares certificate with concrete univariate denominators for nonnegative bivariate polynomials. The trace positivity certificates in this paper are obtained by convex duality through solving the so-called unbounded tracial moment problem, which arises from noncommutative integration theory and free probability. Given a linear functional on nc polynomials, the tracial moment problem asks whether it is a joint distribution of integral operators affiliated with a tracial von Neumann algebra. A counterpart to Haviland’s theorem on solvability of the tracial moment problem is established. Moreover, a variant of Carleman’s condition is shown to guarantee the existence of a solution to the tracial moment problem. Together with semidefinite optimization, this is then used to prove that every trace-positive nc polynomial admits an explicit approximation in the 1-norm on its coefficients by sums of hermitian squares and commutators of nc polynomials.

Vorschaubild nicht verfügbar

Dilations, Linear Matrix Inequalities, the Matrix Cube Problem and Beta Distributions

2015, Helton, J. William, Klep, Igor, McCullough, Scott A., Schweighofer, Markus

An operator C on a Hilbert space H dilates to an operator T on a Hilbert space K if there is an isometry V from H to K such that C=V^*TV. A main result of this paper is, for a positive integer d, the simultaneous dilation, up to a sharp factor ϑ(d), of all d-by-d symmetric matrices of operator norm at most one to a collection of commuting self-adjoint contraction operators on a Hilbert space. An analytic formula for ϑ(d) is derived, which as a by-product gives new probabilistic results for the binomial and beta distributions. Dilating to commuting operators has consequences for the theory of linear matrix inequalities (LMIs). Given a tuple A=(A_1,...,A_g) of symmetric matrices of the same size, L(x):=I-\sum A_j x_j is a monic linear pencil. The solution set S_L of the corresponding linear matrix inequality, consisting of those x in R^g for which L(x) is positive semidefinite (PsD), is a spectrahedron. The set D_L of tuples X=(X_1,...,X_g) of symmetric matrices (of the same size) for which L(X):=I-\sum A_j \otimes X_j is PsD, is a free spectrahedron. A result here is: any tuple X of d-by-d symmetric matrices in a bounded free spectrahedron D_L dilates, up to a scale factor, to a tuple T of commuting self-adjoint operators with joint spectrum in the corresponding spectrahedron S_L. From another viewpoint, the scale factor measures the extent that a positive map can fail to be completely positive. Given another monic linear pencil M, the inclusion D_L \subset D_M obviously implies the inclusion S_L \subset S_M and thus can be thought of as its free relaxation. Determining if one free spectrahedron contains another can be done by solving an explicit LMI and is thus computationally tractable. The scale factor for commutative dilation of D_L gives a precise measure of the worst case error inherent in the free relaxation, over all monic linear pencils M of size d.


Algorithmic aspects of sums of hermitian squares

2012, Burgdorf, Sabine, Cafuta, Kristijan, Klep, Igor, Povh, Janez

This paper presents an algorithm and its implementation in the software package NCSOStools for finding sums of hermitian squares and commutators decompositions for polynomials in noncommuting variables. The algorithm is based on noncommutative analogs of the classical Gram matrix method and the Newton polytope method, which allows us to use semidefinite programming. For rational polynomials numerical evidence can be tweaked to obtain an exact certificate using rational numbers. In the presence of Slater points, the Peyrl-Parrilo rounding and projecting method applies. On the other hand, in the absence of strict feasibility, a variant of the facial reduction is proposed to reduce the size of the semidefinite program and to enforce the existence of Slater points.


A local-global principle for linear dependence of noncommutative polynomials

2011, Brešar, Matej, Klep, Igor

Abstract. A set of polynomials in noncommuting variables is called locally linearly dependent if their evaluations at tuples of matrices are always linearly dependent. By a theorem of Camino, Helton, Skelton and Ye, a nite locally
linearly dependent set of polynomials is linearly dependent. In this short note an alternative proof based on the theory of polynomial identities is given. The method of the proof yields generalizations to rectional local linear dependence and evaluations in general algebras over elds of arbitrary characteristic. A main feature of the proof is that it makes it possible to deduce bounds on the size of the matrices where the (directional) local linear dependence needs to be tested in order to establish linear dependence.

Vorschaubild nicht verfügbar

Dilations, linear matrix inequalities, the matrix cube problem and beta distributions

2019-01, Helton, J. William, Klep, Igor, McCullough, Scott, Schweighofer, Markus

Vorschaubild nicht verfügbar

Addendum to "Connes' embedding conjecture and sums of Hermitian squares" [Adv. Math. 217 (4) (2008) 1816-1837]

2014, Burgdorf, Sabine, Dykema, Ken, Klep, Igor, Schweighofer, Markus

We show that Connesʼ embedding conjecture (CEC) is equivalent to a real version of the same (RCEC). Moreover, we show that RCEC is equivalent to a real, purely algebraic statement concerning trace positive polynomials. This purely algebraic reformulation of CEC had previously been given in both a real and a complex version in a paper of the last two authors. The second author discovered a gap in this earlier proof of the equivalence of CEC to the real algebraic reformulation (the proof of the complex algebraic reformulation being correct). In this note, we show that this gap can be filled with help of the theory of real von Neumann algebras.


The matricial relaxation of a linear matrix inequality

2011, Helton, J. William, Klep, Igor, McCullough, Scott

Given linear matrix inequalities (LMIs) L1 and L2 it is natural to ask:
(Q1) when does one dominate the other, that is, does L1(X) 0 imply L2(X) 0?
(Q2) when are they mutually dominant, that is, when do they have the same solution set?
The matrix cube problem of Ben-Tal and Nemirovski [B-TN02] is an example of LMI
domination. Hence such problems can be NP-hard. This paper describes a natural relaxation
of an LMI, based on substituting matrices for the variables xj . With this relaxation, the
domination questions (Q1) and (Q2) have elegant answers, indeed reduce to constructible
semide nite programs. As an example, to test the strength of this relaxation we specialize it
to the matrix cube problem and obtain essentially the relaxation given in [B-TN02]. Thus our
relaxation could be viewed as generalizing it.
Assume there is an X such that L1(X) and L2(X) are both positive de nite, and suppose
the positivity domain of L1 is bounded. For our \matrix variable" relaxation a positive answer
to (Q1) is equivalent to the existence of matrices Vj such that
(A1) L2(x) = V
1 L1(x)V1 + + V
L1(x)V :
As for (Q2) we show that L1 and L2 are mutually dominant if and only if, up to certain
redundancies described in the paper, L1 and L2 are unitarily equivalent. Algebraic certi cates
for positivity, such as (A1) for linear polynomials, are typically called Positivstellens atze. The
paper goes on to derive a Putinar-type Positivstellensatz for polynomials with a cleaner and
more powerful conclusion under the stronger hypothesis of positivity on an underlying bounded
domain of the form fX j L(X) 0g:
An observation at the core of the paper is that the relaxed LMI domination problem is
equivalent to a classical problem. Namely, the problem of determining if a linear map from
a subspace of matrices to a matrix algebra is \completely positive". Complete positivity is
one of the main techniques of modern operator theory and the theory of operator algebras.
On one hand it provides tools for studying LMIs and on the other hand, since completely
positive maps are not so far from representations and generally are more tractable than their
merely positive counterparts, the theory of completely positive maps provides perspective on
the di culties in solving LMI domination problems.

Vorschaubild nicht verfügbar

Optimization of Polynomials in Non-Commuting Variables

2016, Burgdorf, Sabine, Klep, Igor, Povh, Janez

Vorschaubild nicht verfügbar

An exact duality theory for semidefinite programming based on sums of squares

2013, Schweighofer, Markus, Klep, Igor

Farkas' lemma is a fundamental result from linear programming providing linear certificates for infeasibility of systems of linear inequalities. In semidefinite programming, such linear certificates only exist for strongly infeasible linear matrix inequalities. We provide nonlinear algebraic certificates for all infeasible linear matrix inequalities in the spirit of real algebraic geometry: A linear matrix inequality A(x) >_ 0 is infeasible if and only if −1 lies in the quadratic module associated to A. We also present a new exact duality theory for semidefinite programming, motivated by the real radical and sums of squares certificates from real algebraic geometry.


Constrained polynominal optimization problems with noncommuting variables

2011, Cafuta, Kristijan, Klep, Igor, Povh, Janez

In this paper we study constrained eigenvalue optimization of noncommutative (nc) polynomials, focusing on the polydisc and the ball. Our three main results are as follows: (1) an nc polynomial is nonnegative if and only if it admits a weighted sum of hermitian squares decomposition; (2) (eigenvalue) optima for nc polynomials can be computed using a single semide nite program (SDP) { this sharply contrasts the commutative case where sequences of SDPs are needed; (3) the dual solution to this \single" SDP can be exploited to extract eigenvalue optimizers with an algorithm based on two ingredients: solution to a truncated nc moment problem via at extensions; Gelfand-Naimark-Segal (GNS) construction. The implementation of these procedures in our computer algebra system NCSOStools is presented and several examples pertaining to matrix inequalities are given to illustrate our results.