AMS eBook CollectionsOne of the world's most respected mathematical collections, available in digital format for your library or institution

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

About this Title

J. William Helton, Department of Mathematics, University of California, San Diego, California, Igor Klep, Department of Mathematics, The University of Auckland, New Zealand, Scott McCullough, Department of Mathematics, University of Florida, Gainesville, Florida 32611-8105 and Markus Schweighofer, Fachbereich Mathematik und Statistik, Universität Konstanz

Publication: Memoirs of the American Mathematical Society
Publication Year: 2019; Volume 257, Number 1232
ISBNs: 978-1-4704-3455-7 (print); 978-1-4704-4947-6 (online)
DOI: https://doi.org/10.1090/memo/1232
Published electronically: January 3, 2019
Keywords: Dilation, completely positive map, linear matrix inequality, spectrahedron, free spectrahedron, matrix cube problem, binomial distribution, beta distribution, robust stability, free analysis
MSC: Primary 47A20, 46L07, 13J30; Secondary 60E05, 33B15, 90C22

View full volume PDF

Table of Contents

Chapters

• 1. Introduction
• 2. Dilations and Free Spectrahedral Inclusions
• 3. Lifting and Averaging
• 4. A Simplified Form for $\vartheta$
• 5. $\vartheta$ is the Optimal Bound
• 6. The Optimality Condition $\alpha =\beta$ inTerms of Beta Functions
• 7. Rank versus Size for the Matrix Cube
• 8. Free Spectrahedral Inclusion Generalities
• 9. Reformulation of the Optimization Problem
• 10. Simmons’ Theorem for Half Integers
• 11. Bounds on the Median and the Equipoint of the Beta Distribution
• 12. Proof of Theorem
• 13. Estimating $\vartheta (d)$ for Odd $d$
• 14. Dilations and Inclusions of Balls
• 15. Probabilistic Theorems and Interpretations Continued

Abstract

An operator $C$ on a Hilbert space $\mathcal H$ dilates to an operator $T$ on a Hilbert space $\mathcal K$ if there is an isometry $V:\mathcal H\to \mathcal 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 $\vartheta (d)$, expressed as a ratio of $\Gamma$ functions for $d$ even, of all $d\times d$ symmetric matrices of operator norm at most one to a collection of commuting self-adjoint contraction operators on a Hilbert space.

Dilating to commuting operators has consequences for the theory of linear matrix inequalities (LMIs). Given a tuple $A=(A_1,\dots ,A_g)$ of $\nu \times \nu$ symmetric matrices, $L(x):= I-\sum A_j x_j$ is a monic linear pencil of size $\nu$. The solution set $\mathscr S_L$ of the corresponding linear matrix inequality, consisting of those $x\in \mathbb {R} ^g$ for which $L(x)\succeq 0$, is a spectrahedron. The set $\mathcal {D}_L$ of tuples $X=(X_1,\dots ,X_g)$ of symmetric matrices (of the same size) for which $L(X):=I -\sum A_j\otimes X_j$ is positive semidefinite, is a free spectrahedron. It is shown that any tuple $X$ of $d\times d$ symmetric matrices in a bounded free spectrahedron $\mathcal {D}_L$ dilates, up to a scale factor depending only on $d$, to a tuple $T$ of commuting self-adjoint operators with joint spectrum in the corresponding spectrahedron $\mathscr 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 $\tilde {L}$, the inclusion $\mathcal {D}_L\subset \mathcal {D}_{\tilde {L}}$ obviously implies the inclusion $\mathscr S_L\subset \mathscr S_{\tilde {L}}$ 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 $\mathcal {D}_L$ gives a precise measure of the worst case error inherent in the free relaxation, over all monic linear pencils $\tilde {L}$ of size $d$.

The set $\mathfrak {C} ^{(g)}$ of $g$-tuples of symmetric matrices of norm at most one is an example of a free spectrahedron known as the free cube and its associated spectrahedron is the cube $[-1,1]^g$. The free relaxation of the the NP-hard inclusion problem $[-1,1]^g\subset \mathscr S_L$ was introduced by Ben-Tal and Nemirovski. They obtained the lower bound $\vartheta (d),$ expressed as the solution of an optimization problem over diagonal matrices of trace norm $1,$ for the divergence between the original and relaxed problem. The result here on simultaneous dilations of contractions proves this bound is sharp. Determining an analytic formula for $\vartheta (d)$ produces, as a by-product, new probabilistic results for the binomial and beta distributions.