Zusammenfassung für den Vortrag am 30.08.2021 (14:00 Uhr)Numerical Algebra and Optimization Seminar
Dogyoon Song (Massachusetts Institute of Technology)
On Approximating Positive Semidefinite Cone Using Small-sized PSD Constraints
We study the problem of approximating the cone of positive semidefinite (PSD) matrices with a convex cone that can be described by smaller-sized PSD constraints. Specifically, we ask the question: “how closely can we approximate the set of unit-trace \(n \times n\) positive semidefinite (PSD) matrices, denoted by \(D\), using at most \(N\) number of \(k \times k\) PSD constraints?” We show that any set that approximates \(D\) within a constant approximation ratio must have superpolynomially large \(k\)-semidefinite extension complexity when \(k = o(n / \log n)\).