Abstract for the talk on 30.08.2021 (14:00 h)
Numerical Algebra and Optimization SeminarDogyoon 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)\).
Physical attendance in seminars is restricted to 15 participants. Unfortunately this max. number of allowed participants is reached.