http://www.mathworks.com/matlabcentral/newsreader/view_thread/283857
MATLAB Central Newsreader  Fitting a (hyper)ellipsoid to data
Feed for thread: Fitting a (hyper)ellipsoid to data
enus
©19942014 by MathWorks, Inc.
webmaster@mathworks.com
MATLAB Central Newsreader
http://blogs.law.harvard.edu/tech/rss
60
MathWorks
http://www.mathworks.com/images/membrane_icon.gif

Fri, 04 Jun 2010 10:13:03 +0000
Fitting a (hyper)ellipsoid to data
http://www.mathworks.com/matlabcentral/newsreader/view_thread/283857#751661
David Heslop
Dear All,<br>
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. <br>
<br>
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.<br>
<br>
Thanks in advance for any advice you can offer,<br>
<br>
Dave

Sat, 05 Jun 2010 03:59:04 +0000
Re: Fitting a (hyper)ellipsoid to data
http://www.mathworks.com/matlabcentral/newsreader/view_thread/283857#751855
Roger Stafford
"David Heslop" <david_heslop@xyz.com> wrote in message <huajjf$9u8$1@fred.mathworks.com>...<br>
> Dear All,<br>
> 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. <br>
> <br>
> 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.<br>
> <br>
> Thanks in advance for any advice you can offer,<br>
> <br>
> Dave<br>
      <br>
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.<br>
<br>
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.<br>
<br>
[U,S,V] = svd([X.^2,ones(N,1)],0);<br>
a = sqrt(V(N+1,D+1)./V(:,D+1));<br>
<br>
Then the vector a contains the lengths of the ellipsoid semiaxes along the various coordinate axes in accordance with the equation<br>
<br>
x1^2/a(1)^2 + x2^2/a(2)^2 + x3^2/a(3)^2 + .... + xD^2/a(D)^2 = 1<br>
<br>
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.)<br>
<br>
Note also that if negative values occur in the square root, then a better fit has been found with some kind of hyperhyperboloid, which would indicate poorly located points or perhaps too few of them.<br>
<br>
Roger Stafford

Mon, 07 Jun 2010 07:23:07 +0000
Re: Fitting a (hyper)ellipsoid to data
http://www.mathworks.com/matlabcentral/newsreader/view_thread/283857#752191
David Heslop
"Roger Stafford" <ellieandrogerxyzzy@mindspring.com.invalid> wrote in message <huci28$bsb$1@fred.mathworks.com>...<br>
> "David Heslop" <david_heslop@xyz.com> wrote in message <huajjf$9u8$1@fred.mathworks.com>...<br>
> > Dear All,<br>
> > 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. <br>
> > <br>
> > 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.<br>
> > <br>
> > Thanks in advance for any advice you can offer,<br>
> > <br>
> > Dave<br>
>       <br>
> 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.<br>
> <br>
> 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.<br>
> <br>
> [U,S,V] = svd([X.^2,ones(N,1)],0);<br>
> a = sqrt(V(N+1,D+1)./V(:,D+1));<br>
> <br>
> Then the vector a contains the lengths of the ellipsoid semiaxes along the various coordinate axes in accordance with the equation<br>
> <br>
> x1^2/a(1)^2 + x2^2/a(2)^2 + x3^2/a(3)^2 + .... + xD^2/a(D)^2 = 1<br>
> <br>
> 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.)<br>
> <br>
> Note also that if negative values occur in the square root, then a better fit has been found with some kind of hyperhyperboloid, which would indicate poorly located points or perhaps too few of them.<br>
> <br>
> Roger Stafford<br>
<br>
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,<br>
thanks, Dave