# Given a set of 3 orthogonal vectors, how can I find a minimum volume enclosing ellipsoid expressed in the Cartesian coordinate frame?

Generalized Problem Given values to start the problem:

• A 3D orthonormal coordinate frame (we'll call it the 'V' coordinate frame) that is rotated from the global coordinate system (we'll call it 'G') but shares a common origin.
• 3 magnitudes representing the semi-major axes of an ellipsoid defined in the 'V' coordinate frame
• All necessary information (angles, etc.) required to fully describe the system.

Desired output:

• 3 magnitudes representing the semi-major axes of an ellipsoid expressed in the 'G' coordinate frame that completely encompasses the input ellipsoid.

I realize that there may be different solutions depending on the type of ellipsoid-fit. I believe what I desire is a minimum volume enclosing ellipsoid. I don't believe that a mere direction cosine matrix rotation is a sufficient solution to be physically meaningful.

Problem Background

To give context for this problem, I am trying to geolocate a ground feature using Line-of-Bearing measurements (with range measurements) from a quad-copter in the air the stationary ground feature. I am trying to convert the sensor covariances ($\sigma_{psi}$, $\sigma_{theta}$, and $\sigma_{range}$) of the sensor to their minimum equivalent values represented in the global coordinate system (North, East, and Up in this instance).

Given that $\sigma_{psi}$ and $\sigma_{theta}$ are expressed as covariance of an angular measurement, their values can be converted to a distance using the approximation of $s=r\theta$ or any similar equation. $\sigma_{range}$ is already expressed in units of distance.

Depending on the location and altitude of the quad-copter, the alignment of the 'V' coordinate system with 'G' will change.

As I will be tracking the location of the target using an estimator (in the global coordinate frame), I want to know the equivalent covariances in XYZ of each measurement as they depend on the location and slant range of the quad-copter and target.

Please let me know if any further information or explanations are needed. Thanks in advance for any help!

• Why use an axis-aligned enclosing ellipsoid rather than a sphere? Especially when you can use the three covariances (and perhaps a few past measurements) to estimate the radius. I personally don't see any downsides to using a sphere instead of an ellipsoid here, especially if the sphere location is just displayed to the human operator. Is there a real reason for requiring the ellipsoid instead? – Nominal Animal Oct 13 '16 at 3:58
• I am using the covariance ellipsoid as a cost function in a min-maxCovarianceComponent optimization problem. Viewing the shape of the covariance ellipsoid is a common method for this type of problem. I'm not positive, but I believe that the ellipsoid contains more information for the optimization solver. – pheidlauf Oct 13 '16 at 17:08
• The original ellipsoid probably does contain more information for the optimization solver, but I do believe that is lost when replaced by an axis-aligned minimum volume enclosing ellipsoid. (Consider the case for a cigar-like ellipsoid oriented roughly diagonally compared to coordinate axes. The minimum volume enclosing axis-aligned ellipsoid will be very large compared to the original ellipsoid volume.) I claim, but have no proof, that you could retain most of that information (otherwise lost) by approximating the ellipsoid with a sphere using the initial covariances. – Nominal Animal Oct 13 '16 at 17:26
• Thank you for the input! I will definitely consider that method. My main counter to the sphere approximation given your cigar approximation is if the ellipsoid is aligned primarily in the XY plane. The Z-axis component of covariance would be unnecessarily inflated by a sphere approximation, though the X and Y components would be more accurate. If the "cigar" was oriented along the <1,1,1> direction, the sphere would be perfectly correct, but for any other orientation I believe the sphere is a sub-optimal fit. – pheidlauf Oct 13 '16 at 18:02
• Consider other spheres than those that fully enclose the ellipse; perhaps one with equal volume. (Or a scaled volume, if the sensor covariances have a tendency towards a specific shape.) Does the sensor actually provide covariances rather than variances? Do you have any actual test data from a physical sensor, to see if there is gainable information there? Just in case if converting each sensor reading to a physical location (absolute; not relative to the sensor platform), and using statistics on them, would yield more practical results? – Nominal Animal Oct 13 '16 at 21:21

I have a partial solution.

First, to find a sphere enclosing a given ellipsoid with semiaxes $\vec v_i = ((v_i)_j)$, you would need the largest singular value of the matrix $V$ with elements $v_{ij} := (v_i)_j$:

$$r = \sqrt{\max \sigma(V^T V)}$$

Now this also works when the vectors $\vec v_i$ are not orthogonal, i.e., when the ellipsoid is deformed by a linear transform along with its spanning vectors. So you can try different semiaxis ratios by scaling the problem in $(x, y, z)$, finding an enclosing sphere, and scaling back to deform the sphere to an ellipsoid.

If the scaling transform has a determinant of 1, that is, if the scale factors $\alpha_x, \alpha_y, \alpha_z$ in the three axes multiply to 1, then the volume of the ellipsoid found this way is identical to the volume of the sphere and thus proportional (cubically) to

$$\tilde r = \sqrt{\max \sigma(D V^T V D)},$$

where

$$D = \mathrm{diag}(\alpha_x, \alpha_y, \alpha_z), \qquad \alpha_x\alpha_y\alpha_z = 1.$$

So the problem really is to find a constrained minimum of the maximal eigenvalue of $D V^T V D$ where $D$ conforms to the conditions above.

I don't know a trick to do this reduced problem but someone might take it from here. But you can finish it using a direct approach. The characteristic equation is cubic and a priori known to have three positive roots so it's possible in principle to express the maximal eigenvalue analytically and then differentiate it by $\alpha_i$ and use the method of Lagrange coefficients to find the constrained extreme.

Or, since you are going to implement this on a computer anyway, this is an optimization problem with two independent variables and a very quick evaluation, so just use any stochastic optimization strategy. It might be a good idea to encode $\alpha_i = \exp \beta_i$ and convert $\prod\alpha_i = 1$ to $\sum\beta_i = 0$.

Addendum: By the way, the problem becomes very simple if you only ask for the smallest-volume ellipsoid enclosing the three vectors alone, not an ellipsoid defined by them. It's easy to prove that would be the ellipsoid uniquely defined by containing the three vectors, its semiaxes are related to the solutions to the linear system of equations

$$\sum_{j\in\{x,y,z\}} a_j v_{ij}^2 = 1, \quad \forall i \in \{1,2,3\}$$

by $a_j = r_j^{-2}$. Maybe that could be sufficient for your application?

• The addendum hits at the problem of the model used in this question: if the three orthogonal vectors are some sort of error measures, why would an ellipse be a better than e.g. a box fit? I suspect that interpolation of the vectors -- roughly, rotating the ellipsoid then measuring the intersection of the ellipse along each positive axis -- would work just as well; no need for a minimum-volume fit. – Nominal Animal Oct 29 '16 at 19:20
• @NominalAnimal: Uhm well, even simpler. I was thinking of a sphere with the largest of the semi-axes of the original ellipsoid as the radius. – Han de Bruijn Nov 2 '16 at 14:26
• @HandeBruijn: As I mentioned in a comment to the original question, I think the spherical approximation is even better in many ways. However, we must remember this is all very tangential, and not at all directed at this answer The Vee has provided. (Which I have no issue with, by the way: I know of no algebraic way to do the volume minimization referred to, and the numerical methods "feel" way too slow (as in orders of magnitude too slow) compared to the possible gains. That said, the OP knows their problem best, so I'm not criticising them either, just interested and asking questions.) – Nominal Animal Nov 2 '16 at 14:41