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
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.
- William B. Arveson, Subalgebras of $C^{\ast }$-algebras, Acta Math. 123 (1969), 141–224. MR 253059, DOI 10.1007/BF02392388
- William Arveson, Subalgebras of $C^{\ast }$-algebras. II, Acta Math. 128 (1972), no. 3-4, 271–308. MR 394232, DOI 10.1007/BF02392166
- William Arveson, The noncommutative Choquet boundary, J. Amer. Math. Soc. 21 (2008), no. 4, 1065–1084. MR 2425180, DOI 10.1090/S0894-0347-07-00570-X
- C. Badea, B. Beckermann: Spectral Sets, In: Second edition of Handbook of Linear Algebra (L. Hogben, ed.). CRC Press, 2013.
- Joseph A. Ball, Multidimensional circuit synthesis and multivariable dilation theory, Multidimens. Syst. Signal Process. 22 (2011), no. 1-3, 27–44. MR 2771469, DOI 10.1007/s11045-010-0123-2
- Joseph A. Ball, Israel Gohberg, and Leiba Rodman, Interpolation of rational matrix functions, Operator Theory: Advances and Applications, vol. 45, Birkhäuser Verlag, Basel, 1990. MR 1083145
- Alexander Belton, Dominique Guillot, Apoorva Khare, and Mihai Putinar, Matrix positivity preservers in fixed dimension. I, Adv. Math. 298 (2016), 325–368. MR 3505743, DOI 10.1016/j.aim.2016.04.016
- Aharon Ben-Tal and Arkadi Nemirovski, On tractable approximations of uncertain linear matrix inequalities affected by interval uncertainty, SIAM J. Optim. 12 (2002), no. 3, 811–833. MR 1884919, DOI 10.1137/S1052623400374756
- David P. Blecher and Christian Le Merdy, Operator algebras and their modules—an operator space approach, London Mathematical Society Monographs. New Series, vol. 30, The Clarendon Press, Oxford University Press, Oxford, 2004. Oxford Science Publications. MR 2111973
- Grigoriy Blekherman, Pablo A. Parrilo, and Rekha R. Thomas (eds.), Semidefinite optimization and convex algebraic geometry, MOS-SIAM Series on Optimization, vol. 13, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA; Mathematical Optimization Society, Philadelphia, PA, 2013. MR 3075433
- Stephen Boyd, Laurent El Ghaoui, Eric Feron, and Venkataramanan Balakrishnan, Linear matrix inequalities in system and control theory, SIAM Studies in Applied Mathematics, vol. 15, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1994. MR 1284712
- J. Dereziński, Introduction to representations of the canonical commutation and anticommutation relations, Large Coulomb systems, Lecture Notes in Phys., vol. 695, Springer, Berlin, 2006, pp. 63–143. MR 2497821, DOI 10.1007/3-540-32579-4_{3}
- Persi Diaconis and Sandy Zabell, Closed form summation for classical distributions: variations on a theme of de Moivre, Statist. Sci. 6 (1991), no. 3, 284–302. MR 1144242
- Kenneth R. Davidson, The mathematical legacy of William Arveson, J. Operator Theory 68 (2012), no. 2, 307–334. MR 2995725
- Kenneth R. Davidson, Adam Dor-On, Orr Moshe Shalit, and Baruch Solel, Dilations, inclusions of matrix convex sets, and completely positive maps, Int. Math. Res. Not. IMRN 13 (2017), 4069–4130. MR 3671511, DOI 10.1093/imrn/rnw140
- Kenneth R. Davidson and Matthew Kennedy, The Choquet boundary of an operator system, Duke Math. J. 164 (2015), no. 15, 2989–3004. MR 3430455, DOI 10.1215/00127094-3165004
- Mauricio C. de Oliveira, J. William Helton, Scott A. McCullough, and Mihai Putinar, Engineering systems and free semi-algebraic geometry, Emerging applications of algebraic geometry, IMA Vol. Math. Appl., vol. 149, Springer, New York, 2009, pp. 17–61. MR 2500463, DOI 10.1007/978-0-387-09686-5_{2}
- Edward G. Effros and Soren Winkler, Matrix convexity: operator analogues of the bipolar and Hahn-Banach theorems, J. Funct. Anal. 144 (1997), no. 1, 117–152. MR 1430718, DOI 10.1006/jfan.1996.2958
- Douglas Farenick and Vern I. Paulsen, Operator system quotients of matrix algebras and their tensor products, Math. Scand. 111 (2012), no. 2, 210–243. MR 3023524, DOI 10.7146/math.scand.a-15225
- C. Foias, A. E. Frazho, I. Gohberg, and M. A. Kaashoek, Metric constrained interpolation, commutant lifting and systems, Operator Theory: Advances and Applications, vol. 100, Birkhäuser Verlag, Basel, 1998. MR 1635831
- L. Gårding and A. Wightman, Representations of the anticommutation relations, Proc. Nat. Acad. Sci. U.S.A. 40 (1954), 617–621. MR 62956, DOI 10.1073/pnas.40.7.617
- Michel X. Goemans and David P. Williamson, Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming, J. Assoc. Comput. Mach. 42 (1995), no. 6, 1115–1145. MR 1412228, DOI 10.1145/227683.227684
- Richard A. Groeneveld and Glen Meeden, The mode, median, and mean inequality, Amer. Statist. 31 (1977), no. 3, 120–121. MR 448635, DOI 10.2307/2682959
- J. William Helton, Igor Klep, and Scott McCullough, The convex Positivstellensatz in a free algebra, Adv. Math. 231 (2012), no. 1, 516–534. MR 2935397, DOI 10.1016/j.aim.2012.04.028
- J. William Helton, Igor Klep, and Scott McCullough, The matricial relaxation of a linear matrix inequality, Math. Program. 138 (2013), no. 1-2, Ser. A, 401–445. MR 3034812, DOI 10.1007/s10107-012-0525-z
- J. William Helton, Igor Klep, and Scott McCullough, The tracial Hahn-Banach theorem, polar duals, matrix convex sets, and projections of free spectrahedra, J. Eur. Math. Soc. (JEMS) 19 (2017), no. 6, 1845–1897. MR 3646877, DOI 10.4171/JEMS/707
- Deguang Han, David R. Larson, Bei Liu, and Rui Liu, Operator-valued measures, dilations, and the theory of frames, Mem. Amer. Math. Soc. 229 (2014), no. 1075, viii+84. MR 3186831
- Deguang Han, David R. Larson, Bei Liu, and Rui Liu, Dilations of frames, operator-valued measures and bounded linear maps, Operator methods in wavelets, tilings, and frames, Contemp. Math., vol. 626, Amer. Math. Soc., Providence, RI, 2014, pp. 33–53. MR 3329092, DOI 10.1090/conm/626/12520
- J. William Helton and Scott McCullough, Every convex free basic semi-algebraic set has an LMI representation, Ann. of Math. (2) 176 (2012), no. 2, 979–1013. MR 2950768, DOI 10.4007/annals.2012.176.2.6
- J. William Helton and Victor Vinnikov, Linear matrix inequality representation of sets, Comm. Pure Appl. Math. 60 (2007), no. 5, 654–674. MR 2292953, DOI 10.1002/cpa.20155
- Dmitry S. Kaliuzhnyi-Verbovetskyi and Victor Vinnikov, Foundations of free noncommutative function theory, Mathematical Surveys and Monographs, vol. 199, American Mathematical Society, Providence, RI, 2014. MR 3244229
- Ali S. Kavruk, Vern I. Paulsen, Ivan G. Todorov, and Mark Tomforde, Quotients, exactness, and nuclearity in the operator system category, Adv. Math. 235 (2013), 321–360. MR 3010061, DOI 10.1016/j.aim.2012.05.025
- Jovan D. Kečkić and Petar M. Vasić, Some inequalities for the gamma function, Publ. Inst. Math. (Beograd) (N.S.) 11(25) (1971), 107–114. MR 308446
- Kai Kellner, Thorsten Theobald, and Christian Trabandt, Containment problems for polytopes and spectrahedra, SIAM J. Optim. 23 (2013), no. 2, 1000–1020. MR 3055247, DOI 10.1137/120874898
- J. Kerman: A closed-form approximation for the median of the beta distribution, preprint http://arxiv.org/abs/1111.0433v1
- David R. Larson and Franciszek Hugon Szafraniec, Framings and dilations, Acta Sci. Math. (Szeged) 79 (2013), no. 3-4, 529–543. MR 3134503
- D. S. Mitrinović, Analytic inequalities, Springer-Verlag, New York-Berlin, 1970. In cooperation with P. M. Vasić. Die Grundlehren der mathematischen Wissenschaften, Band 165. MR 0274686
- M. Neumark, Positive definite operator functions on a commutative group, Bull. Acad. Sci. URSS Sér. Math. [Izvestia Akad. Nauk SSSR] 7 (1943), 237–244 (Russian, with English summary). MR 0010265
- Yu. Nesterov, Semidefinite relaxation and nonconvex quadratic optimization, Optim. Methods Softw. 9 (1998), no. 1-3, 141–160. MR 1618100, DOI 10.1080/10556789808805690
- Arkadi Nemirovski, Advances in convex optimization: conic programming, International Congress of Mathematicians. Vol. I, Eur. Math. Soc., Zürich, 2007, pp. 413–444. MR 2334199, DOI 10.4171/022-1/17
- Michael A. Nielsen and Isaac L. Chuang, Quantum computation and quantum information, Cambridge University Press, Cambridge, 2000. MR 1796805
- Vern Paulsen, Completely bounded maps and operator algebras, Cambridge Studies in Advanced Mathematics, vol. 78, Cambridge University Press, Cambridge, 2002. MR 1976867
- M. E. Payton, L. J. Young, and J. H. Young, Bounds for the difference between median and mean of beta and negative binomial distributions, Metrika 36 (1989), no. 6, 347–354. MR 1050698, DOI 10.1007/BF02614111
- Olivier Perrin and Edmond Redside, Generalization of Simmons’ theorem, Statist. Probab. Lett. 77 (2007), no. 6, 604–606. MR 2345025, DOI 10.1016/j.spl.2006.09.006
- Gilles Pisier, Introduction to operator space theory, London Mathematical Society Lecture Note Series, vol. 294, Cambridge University Press, Cambridge, 2003. MR 2006539
- Earl D. Rainville, Special functions, 1st ed., Chelsea Publishing Co., Bronx, N.Y., 1971. MR 0393590
- Joseph L. Taylor, A general framework for a multi-operator functional calculus, Advances in Math. 9 (1972), 183–252. MR 328625, DOI 10.1016/0001-8708(72)90017-5
- Joseph L. Taylor, Functions of several noncommuting variables, Bull. Amer. Math. Soc. 79 (1973), 1–34. MR 315446, DOI 10.1090/S0002-9904-1973-13077-0
- Robert E. Skelton, Tetsuya Iwasaki, and Karolos M. Grigoriadis, A unified algebraic approach to linear control design, The Taylor & Francis Systems and Control Book Series, Taylor & Francis Group, London, 1998. MR 1484416
- T. C. Simmons, A New Theorem in Probability, Proc. Lond. Math. Soc. 26 (1894/95), 290–323. MR 1575895, DOI 10.1112/plms/s1-26.1.290
- W. Forrest Stinespring, Positive functions on $C^*$-algebras, Proc. Amer. Math. Soc. 6 (1955), 211–216. MR 69403, DOI 10.1090/S0002-9939-1955-0069403-4
- Béla Sz.-Nagy, Sur les contractions de l’espace de Hilbert, Acta Sci. Math. (Szeged) 15 (1953), 87–92 (French). MR 58128
- Béla Sz.-Nagy, Ciprian Foias, Hari Bercovici, and László Kérchy, Harmonic analysis of operators on Hilbert space, Revised and enlarged edition, Universitext, Springer, New York, 2010. MR 2760647
- Dan Voiculescu, Free analysis questions. I. Duality transform for the coalgebra of $\partial _{X\colon B}$, Int. Math. Res. Not. 16 (2004), 793–822. MR 2036956, DOI 10.1155/S1073792804132443
- Dan-Virgil Voiculescu, Free analysis questions II: the Grassmannian completion and the series expansions at the origin, J. Reine Angew. Math. 645 (2010), 155–236. MR 2673426, DOI 10.1515/CRELLE.2010.063
- Henry Wolkowicz, Romesh Saigal, and Lieven Vandenberghe (eds.), Handbook of semidefinite programming, International Series in Operations Research & Management Science, vol. 27, Kluwer Academic Publishers, Boston, MA, 2000. Theory, algorithms, and applications. MR 1778223
- Aljaž Zalar, Operator Positivstellensätze for noncommutative polynomials positive on matrix convex sets, J. Math. Anal. Appl. 445 (2017), no. 1, 32–80. MR 3543758, DOI 10.1016/j.jmaa.2016.07.043