The matricial relaxation of a linear matrix inequality

Abstract

Given linear matrix inequalities (LMIs) L_1 and L_2, it is natural to ask: (Q1) when does one dominate the other, that is, does L_1(X) PsD imply L_2(X) PsD? (Q2) when do they have the same solution set? Such questions can be NP-hard. This paper describes a natural relaxation of an LMI, based on substituting matrices for the variables x_j. With this relaxation, the domination questions (Q1) and (Q2) have elegant answers, indeed reduce to constructible semidefinite programs. Assume there is an X such that L_1(X) and L_2(X) are both PD, and suppose the positivity domain of L_1 is bounded. For our "matrix variable" relaxation a positive answer to (Q1) is equivalent to the existence of matrices V_j such that L_2(x)=V_1^* L_1(x) V_1 + ... + V_k^* L_1(x) V_k. As for (Q2) we show that, up to redundancy, L_1 and L_2 are unitarily equivalent. Such algebraic certificates are typically called Positivstellensaetze and the above are examples of such for linear polynomials. The paper goes on to derive a cleaner and more powerful Putinar-type Positivstellensatz for polynomials positive on a bounded set of the form {X | L(X) PsD}. 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".

v1: 34 pages, v2: 41 pages; supplementary material is available in the source file, or see http://srag.fmf.uni-lj.si/

References in corpus (2)

• The noncommutative Choquet boundary
• Pure states, positive matrix polynomials and sums of hermitian squares

Cited by in corpus (33)

• Dilations, inclusions of matrix convex sets, and completely positive maps
• Minimal and maximal matrix convex sets
• Spectrahedral Containment and Operator Systems with Finite-Dimensional Realization
• Geometry of free loci and factorization of noncommutative polynomials
• Joint measurability of quantum effects and the matrix diamond
• Extreme points of matrix convex sets, free spectrahedra and dilation theory
• Operator Positivstellensätze for noncommutative polynomials positive on matrix convex sets
• Arveson extreme points span free spectrahedra
• Incompatibility in general probabilistic theories, generalized spectrahedra, and tensor norms
• Matrix Convex Sets Without Absolute Extreme Points
• Noncommutative polynomials nonnegative on a variety intersect a convex set
• Compatibility of quantum measurements and inclusion constants for the matrix jewel
• Bianalytic Maps Between Free Spectrahedra
• There are many more positive maps than completely positive maps
• Strongly peaking representations and compressions of operator systems
• Compressions of compact tuples
• Dilations of $q$-commuting unitaries
• A Real Nullstellensatz for Free Modules
• Bianalytic free maps between spectrahedra and spectraballs
• On fixed points of self maps of the free ball
• Separability for mixed states with operator Schmidt rank two
• Noncommutative partial convexity via $\Gamma$-convexity
• Circular Free Spectrahedra
• Noncommutative polynomials describing convex sets
• Facial structure of matrix convex sets
• Maximal violation of steering inequalities and the matrix cube
• Factorization of noncommutative polynomials and Nullstellensätze for the free algebra
• Optimal bounds on the positivity of a matrix from a few moments
• A Matrix Positivstellensatz with lifting polynomials
• Empirical properties of optima in free semidefinite programs
• Extreme points of matrix convex sets and their spanning properties
• Matrix convex sets over the Euclidean ball and polar duals of real free spectrahedra
• Matrix Extreme Points and Free extreme points of Free spectrahedra