How to find a covariance matrix of minimal volume including all data points by Mahalanobis distance?

Question

Let $v_i$ be real vectors from $R^D$, for $i=0..N-1$.

How to find a real symmetric positive-definite matrix $\Sigma$ so that

• $v_i^T \Sigma^{-1}v_i \leq 1$ for any $v_i$ and
• $det\ \Sigma$ is minimal?

In human words: How to find a Gaussian ellipsoid having minimal volume so that Mahalanobis distance to any data point is limited by some constant?

Answer 1

That's a very standard so called MAXDET program, for which there are specialized solvers. More generally, it is a semidefinite program. Here is a full example in the MATLAB Toolbox YALMIP (disclaimer, developed by me). It requires a semidefinite programming solver, such as Mosek, SeDuMi, SDPT (which has specialized code for the determinant part)

v = randn(2,10);
P = sdpvar(2);
Model = [P>=0];
for i = 1:size(v,2)
    Model = [Model, v(:,i)'*P*v(:,i) <= 1];
end
optimize(Model,-logdet(P))
x = sdpvar(2,1);
clf
plot(x'*value(P)*x <= 1);
hold on;
plot(v(1,:),v(2,:),'*')

https://yalmip.github.io/tutorial/maxdetprogramming/

Answer 2

An interpretation of this question could lead to fitting a guassian with $\mu = \mathbf{0}$ and $$\Sigma = \frac{1}{N}\sum_iv_iv_i^T$$However the requirement that $\max v_i^T \Sigma^{-1} v_i \le 1$would mean that you would need to multiply it by a scale factor $\eta$. This would depend on what the largest value is, but you should be able to find that easily enough (its just normalizing).