CSE 599I: The art and science of positive definite matrices

Spring, 2021

MW 3-4:20pm Remote on Zoom

Instructor: James R. Lee

Office hours: By appointment

Teaching assistant:

Ewin Tang (office hours by appointment)

Course email list [archives]

Homeworks

Resources:

Positive Definite Matrices [BhatiaPDM]
and Matrix Analysis [BhatiaMA]
Rajendra Bhatia
Introduction to Matrix Analysis and Applications
Hiai and Petz
Quantum Information Theory and Quantum Statistics [QITPetz]
Denes Petz
Trace Inequalities and Quantum Entropy
Eric Carlen
Trace Ideals and Their Applications
Barry Simon

Course description:

Positive semidefinite matrices are fundamental objects in semidefinite programming, quantum information theory, and spectral graph theory. Despite their widespread utility, analysis and geometry on the PSD cone is often strange, subtle and, occasionally, magical. This course will focus on the properties of such matrices with an eye toward applications.

Often this gives certain phenomena an "operational" interpretation that provides intuition to complement the underlying linear algebra. The style of the course will be to first introduce a classical argument with real numbers and then to explore analogs for PSD matrices.

Lectures

Mon, Mar 29 PSD matrices [ scribe ]	Elementary facts about Hermitian matrices PSD matrices are Gram matrices The Loewner order The Hadamard (aka Schur) product of matrices as a principal submatrix of the tensor product [BhatiaPDM] Sec 1.1-1.2
Wed, Mar 31 Sum of independent random matrices [ scribe ]	For a detailed exposition of matrix concentration: An Introduction to Matrix Concentration Inequalities
Mon, Apr 05 Golden-Thompson and the Frobenius inner product [ scribe ]	The Frobenius inner product and Schatten $p$ -norms Interleaving correlations and the Golden-Thompson inequality The Golden-Thompson inequality — historical aspects and random matrix applications The Golden-Thompson inequality (Tao’s blog)
Wed, Apr 07 Von Neumann's trace inequality and unitarily invariant norms [ scribe ]	Section II (Majorization and Doubly Stochastic Matrices) in [BhatiaMA] Section IV (Symmetric Norms) in [BhatiaMA] Chapter 6 (Majorization and Singular Values) in [Hiai-Petz] Inequalities: Theory of Majorization and Its Applications, Marshall, Olkin, and Arnold
Mon, Apr 12 Monotonicity and convexity [ scribe ]	Operator monotonicity and convexity The Loewner-Heinz Theorem
Wed, Apr 14 Joint convexity and the relative entropy [ scribe ]	A matrix convexity approach to some celebrated quantum inequalities (Effros) From joint convexity of quantum relative entropy to a concavity theorem of Lieb (Tropp)
Mon, Apr 19 Lieb's concavity theorem [ scribe ]	Convex trace functions and the Wigner-Yanase-Dyson Conjecture (E. Lieb) Loewner’s Theorem on Matrix Monotone Functions (B. Simon)
Wed, Apr 21 Quantum information theory [ scribe ]	Supplementary reading: Chapters 1-3 in Petz’s book [QITPetz] Density matrices, measurements Pure states Composite systems and the partial trace Entanglement Quantum channels Failure of monotonicity for quantum entropy
Mon, Apr 26 Quantum entropy and strong subadditivity [ scribe ]	Summer school slides: Topics in Quantum Entropy and Entanglement (E. Lieb) Subadditivity and the failure of monotonicity Quantum mutual information and strong subadditivity Additional background on classical/quantum information and entropy: Chapters 10-11, in Wilde’s From Classical to Quantum Shannon Theory
Wed, Apr 28 Nonncommutative averages [ scribe ]	Quantum channels The quantum data processing inequality The operator Jensen inequality Jensen’s operator inequality (Hansen and Pedersen)
Mon, May 03 Semidefinite programming and spectrahedra [ ]	Semidefinite programs Semidefinite characterizations of polytopes PSD rank Positive semidefinite rank (Fawzi, Gouveia, Parrilo, Robinson, Thomas) Extended formulations and lifts of polytopes Semidefinite programs and combinatorial optimization (Lovasz)
Wed, May 05 The cut polytope and SOS cones [ ]
Mon, May 10 Symmetric cone factorizations [ scribe ]	Section 4 in Approximate constraint satisfaction requires large LP relaxations Equivariant lifts and sum-of-squares hierarchies On the power of symmetric LP and SDP relaxations
Wed, May 12 Sum of squares degree [ ]	Query complexity in expectation Section 5 in Lower bounds on the size of semidefinite programming relaxations Sums of Squares on the Hypercube
Mon, May 17 Pattern matrices and smooth factorization [ scribe ]
Wed, May 19 No lecture
Mon, May 24 HW#3 discussion	Homework #3
Wed, May 26 HW#3 discussion
Wed, Jun 02 Quantum max-entropy approximation

Homeworks

You may discuss problems with your classmates, but when you write down the solutions, you should do so by yourself. You can use the internet and books for reference material but you should cite every source that you consulted (the name of the book or web page suffices). You should also cite any classmates with whom you discussed solutions. Homework should be typeset.

Homework #1: Spectral pinching
Due Mon, Apr 26, 2021
Homework #2: Quantum entropy
Due Wed, May 12, 2021
Homework #3: PSD factorizations
Due Wed, Jun 2, 2021