Discover MakerZone

MATLAB and Simulink resources for Arduino, LEGO, and Raspberry Pi

Learn more

Discover what MATLAB® can do for your career.

Opportunities for recent engineering grads.

Apply Today

Thread Subject:
Fitting a (hyper)ellipsoid to data

Subject: Fitting a (hyper)ellipsoid to data

From: David Heslop

Date: 4 Jun, 2010 10:13:03

Message: 1 of 3

Dear All,
I have a (hopefully noise free) collection of points which should all lie on the surface of an ellipse / ellipsoid / hyperellipsoid depending on the number of dimensions I’m working in. I also know the center of the data should always lie on the origin of the coordinate system.

Can anyone please offer advice on the way to find the best fit ellipse / ellipsoid / hyperellipsoid. I’ve read a number of posts on this topic, but it isn’t clear to me how to deal with the case when the location of the center of the body is know rather than a parameter to be found. Another limitation is the number of available data points, which if I am working in D dimensions is equal to 2D+2, is this enough points to solve the problem given that I could be working with values of D as high as 50.

Thanks in advance for any advice you can offer,

Dave

Subject: Fitting a (hyper)ellipsoid to data

From: Roger Stafford

Date: 5 Jun, 2010 03:59:04

Message: 2 of 3

"David Heslop" <david_heslop@xyz.com> wrote in message <huajjf$9u8$1@fred.mathworks.com>...
> Dear All,
> I have a (hopefully noise free) collection of points which should all lie on the surface of an ellipse / ellipsoid / hyperellipsoid depending on the number of dimensions I’m working in. I also know the center of the data should always lie on the origin of the coordinate system.
>
> Can anyone please offer advice on the way to find the best fit ellipse / ellipsoid / hyperellipsoid. I’ve read a number of posts on this topic, but it isn’t clear to me how to deal with the case when the location of the center of the body is know rather than a parameter to be found. Another limitation is the number of available data points, which if I am working in D dimensions is equal to 2D+2, is this enough points to solve the problem given that I could be working with values of D as high as 50.
>
> Thanks in advance for any advice you can offer,
>
> Dave
- - - - - - -
  Since you are hoping to get by with 2D+2 points, you must be assuming that the hyperellipsoids' principal axes are known to be aligned with the coordinate axes, which would require just 2D points as a minimum. Determining them with arbitrary orientation would require a minimum of D(D+1)/2 points which soon exceeds 2D+2.

  One way to accomplish what you want is this. If you are in D dimensions, let X be an N x D array of the points' coordinates where each row contains the D coordinates of a single point and where there are N points.

 [U,S,V] = svd([X.^2,ones(N,1)],0);
 a = sqrt(V(N+1,D+1)./V(:,D+1));

Then the vector a contains the lengths of the ellipsoid semi-axes along the various coordinate axes in accordance with the equation

 x1^2/a(1)^2 + x2^2/a(2)^2 + x3^2/a(3)^2 + .... + xD^2/a(D)^2 = 1

  Note that if S(N+1,N+1) is appreciably different from zero, the fit isn't very good. (If N = 2*D, it should be a perfect fit.)

  Note also that if negative values occur in the square root, then a better fit has been found with some kind of hyper-hyperboloid, which would indicate poorly located points or perhaps too few of them.

Roger Stafford

Subject: Fitting a (hyper)ellipsoid to data

From: David Heslop

Date: 7 Jun, 2010 07:23:07

Message: 3 of 3

"Roger Stafford" <ellieandrogerxyzzy@mindspring.com.invalid> wrote in message <huci28$bsb$1@fred.mathworks.com>...
> "David Heslop" <david_heslop@xyz.com> wrote in message <huajjf$9u8$1@fred.mathworks.com>...
> > Dear All,
> > I have a (hopefully noise free) collection of points which should all lie on the surface of an ellipse / ellipsoid / hyperellipsoid depending on the number of dimensions I’m working in. I also know the center of the data should always lie on the origin of the coordinate system.
> >
> > Can anyone please offer advice on the way to find the best fit ellipse / ellipsoid / hyperellipsoid. I’ve read a number of posts on this topic, but it isn’t clear to me how to deal with the case when the location of the center of the body is know rather than a parameter to be found. Another limitation is the number of available data points, which if I am working in D dimensions is equal to 2D+2, is this enough points to solve the problem given that I could be working with values of D as high as 50.
> >
> > Thanks in advance for any advice you can offer,
> >
> > Dave
> - - - - - - -
> Since you are hoping to get by with 2D+2 points, you must be assuming that the hyperellipsoids' principal axes are known to be aligned with the coordinate axes, which would require just 2D points as a minimum. Determining them with arbitrary orientation would require a minimum of D(D+1)/2 points which soon exceeds 2D+2.
>
> One way to accomplish what you want is this. If you are in D dimensions, let X be an N x D array of the points' coordinates where each row contains the D coordinates of a single point and where there are N points.
>
> [U,S,V] = svd([X.^2,ones(N,1)],0);
> a = sqrt(V(N+1,D+1)./V(:,D+1));
>
> Then the vector a contains the lengths of the ellipsoid semi-axes along the various coordinate axes in accordance with the equation
>
> x1^2/a(1)^2 + x2^2/a(2)^2 + x3^2/a(3)^2 + .... + xD^2/a(D)^2 = 1
>
> Note that if S(N+1,N+1) is appreciably different from zero, the fit isn't very good. (If N = 2*D, it should be a perfect fit.)
>
> Note also that if negative values occur in the square root, then a better fit has been found with some kind of hyper-hyperboloid, which would indicate poorly located points or perhaps too few of them.
>
> Roger Stafford

Thank you Roger for your advice, unfortunately, I cannot assume that the principle axes are aligned with the coordinate axes. However it is useful to know that I don't have enough data points, this has saved me a lot of time which would have been wasted trying to "solve" an unsolvable problem,
thanks, Dave

Tags for this Thread

What are tags?

A tag is like a keyword or category label associated with each thread. Tags make it easier for you to find threads of interest.

Anyone can tag a thread. Tags are public and visible to everyone.

Contact us