Author 
Message 
chengiz@mydeja.com science forum beginner
Joined: 19 Jan 2006
Posts: 6

Posted: Wed Jul 19, 2006 6:16 pm Post subject:
Best fit orthogonal basis for list of vectors



Hi,
Given a list of vectors in 3D, the problem is to find 3 orthogonal axes
that are "closest" to these vectors. These vectors would therefore be
in 3 groups, each associated with one of the axes. For vectors in a
group, only closeness to the axis associated with that group would
matter.
I thought of setting up something like an inertia matrix and getting
the eigenvectors, but that only works for one axis and a common inertia
metric... here the vectors in one group should probably not affect the
other group in any way except orthogonality I suppose. Perhaps this is
an optimization problem.
Is there a solution or references I could look up? Thank you very much. 

Back to top 


Robert B. Israel science forum Guru
Joined: 24 Mar 2005
Posts: 2151

Posted: Wed Jul 19, 2006 7:10 pm Post subject:
Re: Best fit orthogonal basis for list of vectors



In article <1153332973.885295.156660@m73g2000cwd.googlegroups.com>,
<chengiz@mydeja.com> wrote:
Quote:  Given a list of vectors in 3D, the problem is to find 3 orthogonal axes
that are "closest" to these vectors. These vectors would therefore be
in 3 groups, each associated with one of the axes. For vectors in a
group, only closeness to the axis associated with that group would
matter.
I thought of setting up something like an inertia matrix and getting
the eigenvectors, but that only works for one axis and a common inertia
metric... here the vectors in one group should probably not affect the
other group in any way except orthogonality I suppose. Perhaps this is
an optimization problem.
Is there a solution or references I could look up? Thank you very much.

Supppose your vectors are x_i, i=1..n. For y in R^3 let
f(y) = y_1^2 + y_2^2 + y_3^2  max(y_1^2, y_2^2, y_3^2). Then you
want to minimize sum_i f(A x_i) over all rotation matrices A (i.e.
orthogonal matrices with determinant 1). You might use Euler angles to
parametrize A. Some optimization software might have trouble with the
nondifferentiability of the objective: you might get good results
replacing max by, say, an l^p norm, e.g.
f(y) = y_1^2 + y_2^2 + y_3^2  (y_1^8 + y_2^8 + y_3^^(1/4).
Robert Israel israel@math.ubc.ca
Department of Mathematics http://www.math.ubc.ca/~israel
University of British Columbia Vancouver, BC, Canada 

Back to top 


Ray Koopman science forum Guru Wannabe
Joined: 25 Mar 2005
Posts: 216

Posted: Wed Jul 19, 2006 7:30 pm Post subject:
Re: Best fit orthogonal basis for list of vectors



Try varimax, or one of the many other blind simplestructureseeking
orthogonal transformations that are used in factor analysis.
chengiz@mydeja.com wrote:
Quote:  Hi,
Given a list of vectors in 3D, the problem is to find 3 orthogonal axes
that are "closest" to these vectors. These vectors would therefore be
in 3 groups, each associated with one of the axes. For vectors in a
group, only closeness to the axis associated with that group would
matter.
I thought of setting up something like an inertia matrix and getting
the eigenvectors, but that only works for one axis and a common inertia
metric... here the vectors in one group should probably not affect the
other group in any way except orthogonality I suppose. Perhaps this is
an optimization problem.
Is there a solution or references I could look up? Thank you very much. 


Back to top 


richard.koolhans@gmail.co science forum beginner
Joined: 29 Nov 2005
Posts: 8

Posted: Wed Jul 19, 2006 9:07 pm Post subject:
Re: Best fit orthogonal basis for list of vectors



Quote: 
Is there a solution or references I could look up? Thank you very much.

Start by looking forward from Analysis of Measurements Based on the
Singular Value Decomposition, SIAM J. of Sci. and Stat. Comp.
(September 1981), Hanson/Norris. This considers many of the issues you
raise. Euler angles may be unstable in their determination and there
are easy alternatives. The fitting in the paper is least squares (with
weights).
DTB 

Back to top 


keez science forum beginner
Joined: 03 Jul 2006
Posts: 2

Posted: Thu Jul 20, 2006 8:34 am Post subject:
Re: Best fit orthogonal basis for list of vectors



Hi Chen,
Quote: 
Given a list of vectors in 3D, the problem is to find 3 orthogonal axes
that are "closest" to these vectors. These vectors would therefore be
in 3 groups, each associated with one of the axes. For vectors in a
group, only closeness to the axis associated with that group would
matter.
I thought of setting up something like an inertia matrix and getting
the eigenvectors, but that only works for one axis and a common inertia
metric... here the vectors in one group should probably not affect the
other group in any way except orthogonality I suppose. Perhaps this is
an optimization problem.

When you have a set v[N] of 3D vectors you can construct the 3x3 normal
matrix:
Sxx Sxy Sxz
Sxy Syy Syz
Sxz Syz Szz
With
Sxx = sum (v[i].x * v[i].x)
Sxy = sum (v[i].x * v[i].y)
Sxz = sum (v[i].x * v[i].z)
Syy = sum (v[i].y * v[i].y)
Syz = sum (v[i].y * v[i].z)
Szz = sum (v[i].z * v[i].z)
This symmetric matrix has three orthogonal eigen vectors, representing
the directions of the main axes of the orientation of your point cloud.
The eigen vector associated with the eigen value with the largest
magnitude is the longitudinal axis (for fitting a line) and the
smallest will give you the normal direction (for fitting a plane.
Cornelis Wessels 

Back to top 


Google


Back to top 



The time now is Fri Sep 21, 2018 5:22 pm  All times are GMT

