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)\).

Die Anzahl der Seminarteilnehmer ist aktuell auf 15 Personen beschränkt. Leider ist diese Anzahl bereits erreicht.

18.10.2021, 14:55