Fitting a (hyper)ellipsoid to data
in [Matlab]
|
From: David Heslop on 4 Jun 2010 06:13 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
From: Roger Stafford on 4 Jun 2010 23:59 "David Heslop" <david_heslop(a)xyz.com> wrote in message <huajjf$9u8$1(a)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
From: David Heslop on 7 Jun 2010 03:23 "Roger Stafford" <ellieandrogerxyzzy(a)mindspring.com.invalid> wrote in message <huci28$bsb$1(a)fred.mathworks.com>... > "David Heslop" <david_heslop(a)xyz.com> wrote in message <huajjf$9u8$1(a)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
|
Pages: 1 Prev: code obfuscation (no p-code is not enough) Next: neural network |