Finding matrix form of Ellipsoid given general form

Question

I have data that I would like to fit with an ellipsoid and I am currently fitting it via the following Matlab commands:

xs = pts(:,1);
ys = pts(:,2);
zs = pts(:,3);

A0 = [xs.^2 ys.^2 zs.^2 xs.*ys ys.*zs xs.*zs xs ys zs ones(size(xs))];
B0 = [ones(size(xs))];

A = A0'*A0;
B = A0'*B0;

X = A\B;

but I am going to rewrite this into C++ later. For now, I have X which are the parameters for the general form of an ellipsoid in 3 space. How do I now turn these parameters into a 3x3 matrix to calculate $$ (x-C)^T \cdot A \cdot (x-C) $$ so that I can efficiently calculate if a point $x$ is inside the ellipsoid centered at $C$? Furthermore, $C$ is not any part of the original calculation of these parameters, so do I need to move xs, ys, and zs to the original before performing the LS fit?

Answer 1

You haven't actually defined an ellipsoid with

$(x-c)^{T}A(x-c)$

An ellipsoid is defined by an inequality

$(x-c)^{T}A(x-c) \leq 1$.

Keep in mind that there isn't an ellipsoid of this form corresponding to every vector $X$ that you might get out of the least squares solution.

If there is a solution, then the quadratic terms are associated with $X(1)$, $\ldots$, $X(6)$.

$A=[X(1) \; X(4) \; X(6); X(4) \; X(2) \; X(5); X(6) \; X(5) \; X(3)]$

Then solve

$-2AC=[X(7); \; X(8); \; X(9)]$

$C^{T}C=X(10)$

If there is no such solution, or $A$ isn't positive definite, then $X$ doesn't correspond to an ellipsoid.

In practice this is likely to fail to produce a solution. There are other approaches to fitting ellipsoids to data that do work, but they aren't based on on first fitting a least squares quadratic form as you've done.

Answer 2

Having all the points contained within ellipsoid reminds me of the minimum volume ellipsoid problem. This is easily solved with Khachiyan's algorithm. The MATLAB code is available here. Having said that, I think it is worth reminding you that matrix $A$ is actually the inverse covariance matrix.