Minimum volume ellipsoid

1 Problem

Illustration

Let x_1, \ldots, x_n be the points in \mathbb{R}^2. Given these points we need to find an ellipsoid, that contains all points with the minimum volume (in 2d case volume of an ellipsoid is just the square).

An invertible linear transformation applied to a unit sphere produces an ellipsoid with the square, that is \det A^{-1} times bigger, than the unit sphere square, that’s why we parametrize the interior of ellipsoid in the following way:

S = \{x \in \mathbb{R}^2 \; | \; u = Ax + b, \|u\|_2^2 \leq 1\}

Sadly, the determinant is the function, which is relatively hard to minimize explicitly. However, the function \log \det A^{-1} = -\log \det A is actually convex, which provides a great opportunity to work with it. As soon as we need to cover all the points with ellipsoid of minimum volume, we pose an optimization problem on the convex function with convex restrictions:

\begin{align*} & \min_{A \in \mathbb{R}^{2 \times 2}, b \in \mathbb{R}^{2}} -\log\det(A)\\ \text{s.t. } & \|Ax_i + b\| \leq 1, i = 1, \ldots, n\\ & A \succ 0 \end{align*}

Illustration

2 Code

Open In Colab{: .btn }

3 References