Suggest edit — minimum volume ellipsoid

Title

Name

Note

---
title: "minimum volume ellipsoid"
type: concept
source: https://www.jemoka.com/posts/kbhminimum_volume_elipsolid/
confidence: high
status: active
---

Lowner-John Ellipsoid minimum volume surrounding ellipsoid
Consider a set of ellipsoid \(C\). Minimum volume ellipsoid \(\epsilon\) with \(C \subset \epsilon\). We can parameterize \(\epsilon\) as \(\epsilon = \qty {v \mid \norm{Av + b}_{2} \leq 1}\); where we assume \(A \in \mathcal{S}_{++}^{n}\).
The volume is proportional to \(\text{det} A^{-1}\). Thus to find minimal-volume ellipsoid, solve:
\begin{align} \min_{A,b}\quad &amp; \log \text{det} A^{-1} \\ \textrm{s.t.} \quad &amp; \text{sup}_{v \in C} \norm{A v + b}_{2} \leq 1 \end{align}
OR, for finite sets:
\begin{align} \min_{A,b}\quad &amp; \log \text{det} A^{-1} \\ \textrm{s.t.} \quad &amp; \norm{A x_{i} + b }_{2} \leq 1, i = 1 \dots m \end{align}
Inside maximum volume inscribing ellipsoid
Consider a set of ellipsoid \(C\). Minimum volume ellipsoid \(\epsilon\) with \(C \subset \epsilon\). We can parameterize \(\epsilon\) as \(\epsilon = \qty {Bu + d \mid \norm{u}_{2} \leq 1}\); where we assume \(B \in \mathcal{S}_{++}^{n}\).
\begin{align} \max_{B,d}\quad &amp; \log \text{det} B \\ \textrm{s.t.} \quad &amp; \text{sup}_{\norm{u}_{2}} \leq 1, I_{C}\qty(Bu+d) \leq 0 \end{align}
where \(I_{C} = 0\) when \(c \in C\), \(\infty\) otherwise.