gdalgorithms-list

[Algorithms] solving for multiple matrices

[Andras B. <and...@gm...>]

Hi, I have a chain of transformations with multiple unknown (but fixed!)
transforms. What I do know is the end result transformation and some of
the transformations in between, and I know these for multiple frames. So
  from here, I'd like to compute the unknowns. Here it is in more formal
version:

I'd like to find 2 unknown matrices X and Y. I have 4 known matrices A1,
A2, B1 and B2, and also know this:
A1 = X * B1 * Y
A2 = X * B2 * Y

I can compute X from the first equation:
X = A1 * Y^-1 * B1^-1

And substitute it into the second:
A2 = A1 * Y^-1 * B1^-1 * B2 * y

Assigning:
C = A1^-1 * A2
D = B1^-1 * B2

Then it becomes:
C = Y^-1 * D * Y

Now, how do I solve this for Y? This form lookes strangely familiar, but I
cannot figure out what to do from here (wish I knew how to Google this ;).  
Hopefully there's an analytic solution to this. Any ideas?

Thanks,



Andras

Re: [Algorithms] solving for multiple matrices

[David B. <dbe...@na...>]

This is just a shot in the dark, but the wikipedia entry on "QZ decomposition" looks a lot like your original statement of the problem --
http://en.wikipedia.org/wiki/Matrix_decomposition#QZ_decomposition

I don't know if X & Y are "unitary" matrices though.  I guess that depends on which kinds of transforms you are using.

Hope that helps,

David Bennett
NAMCO BANDAI Games America Inc.


-----Original Message-----
From: Andras Balogh [mailto:and...@gm...]
Sent: Thursday, September 17, 2009 12:38 PM
To: gda...@li...
Subject: [Algorithms] solving for multiple matrices

Hi, I have a chain of transformations with multiple unknown (but fixed!) transforms. What I do know is the end result transformation and some of the transformations in between, and I know these for multiple frames. So
  from here, I'd like to compute the unknowns. Here it is in more formal
version:

I'd like to find 2 unknown matrices X and Y. I have 4 known matrices A1, A2, B1 and B2, and also know this:
A1 = X * B1 * Y
A2 = X * B2 * Y

I can compute X from the first equation:
X = A1 * Y^-1 * B1^-1

And substitute it into the second:
A2 = A1 * Y^-1 * B1^-1 * B2 * y

Assigning:
C = A1^-1 * A2
D = B1^-1 * B2

Then it becomes:
C = Y^-1 * D * Y

Now, how do I solve this for Y? This form lookes strangely familiar, but I cannot figure out what to do from here (wish I knew how to Google this ;).
Hopefully there's an analytic solution to this. Any ideas?

Thanks,



Andras

------------------------------------------------------------------------------
Come build with us! The BlackBerry® Developer Conference in SF, CA is the only developer event you need to attend this year. Jumpstart your developing skills, take BlackBerry mobile applications to market and stay ahead of the curve. Join us from November 9-12, 2009. Register now! http://p.sf.net/sfu/devconf _______________________________________________
GDAlgorithms-list mailing list
GDA...@li...
https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
Archives:
http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list

Re: [Algorithms] solving for multiple matrices

[Bill B. <wb...@gm...>]

> -----Original Message-----
> From: Andras Balogh [mailto:and...@gm...]
> Sent: Thursday, September 17, 2009 12:38 PM
> To: gda...@li...
> Subject: [Algorithms] solving for multiple matrices
>
> Hi, I have a chain of transformations with multiple unknown (but fixed!) transforms. What I do know is the end result transformation and some of the transformations in between, and I know these for multiple frames. So
>  from here, I'd like to compute the unknowns. Here it is in more formal
> version:
>
> I'd like to find 2 unknown matrices X and Y. I have 4 known matrices A1, A2, B1 and B2, and also know this:
> A1 = X * B1 * Y
> A2 = X * B2 * Y
>
> I can compute X from the first equation:
> X = A1 * Y^-1 * B1^-1
>
> And substitute it into the second:
> A2 = A1 * Y^-1 * B1^-1 * B2 * y
>
> Assigning:
> C = A1^-1 * A2
> D = B1^-1 * B2
>
> Then it becomes:
> C = Y^-1 * D * Y
>
> Now, how do I solve this for Y? This form lookes strangely familiar, but I cannot figure out what to do from here (wish I knew how to Google this ;).
> Hopefully there's an analytic solution to this. Any ideas?
>
> Thanks,
>
>
>
> Andras

It has the form of a similarity transformation, if that helps.
http://mathworld.wolfram.com/SimilarityTransformation.html

Similarity transforms preserve eigenvalues and consequently the trace
and determinant of the matrix applied to, so if C and D don't have the
same trace and determinant, then your Y doesn't exist.

--bb

Re: [Algorithms] solving for multiple matrices

[Jon W. <jw...@gm...>]

Andras Balogh wrote:
>
> Then it becomes:
> C = Y^-1 * D * Y
>
> Now, how do I solve this for Y? This form lookes strangely familiar, but I
> cannot figure out what to do from here (wish I knew how to Google this ;).  
> Hopefully there's an analytic solution to this. Any ideas?
>
>   

That's the formula for applying a rotation in the reference frame of 
another rotation.

Do you know anything more about these matrices than that they are 
matrices? Are they supposed to contain no scale? No translation? If you 
can formulate them as quaternions, writing out the analytical answer is 
a lot simpler :-)

Sincerely,

jw



-- 

  Revenge is the most pointless and damaging of human desires.

Re: [Algorithms] solving for multiple matrices

[Andras B. <and...@gm...>]

Both X and Y matrices represent a simple translation and rotation. For the  
case of the Y matrix, the translation part will likely to be very small,  
so I could probably pretend it's only rotation.

What I would really like though, is to find a solution, where I could use  
more than two equations, eg:
A1 = X * B1 * Y
A2 = X * B2 * Y
A3 = X * B3 * Y
...
An = X * Bn * Y

And then compute a least squares solution from this over-constrained  
system.
BTW, when I said that I'm looking for an analytical solution, I just meant  
something that is not based on an iterative approach. As long as I can get  
to a part where I have to solve a large system of over-constrained linear  
equations, I'm home. Unfortunately, I don't know how to make this linear..


Andras




On Thu, 17 Sep 2009 16:32:25 -0600, Jon Watte <jw...@gm...> wrote:

> Andras Balogh wrote:
>>
>> Then it becomes:
>> C = Y^-1 * D * Y
>>
>> Now, how do I solve this for Y? This form lookes strangely familiar,  
>> but I
>> cannot figure out what to do from here (wish I knew how to Google this  
>> ;).
>> Hopefully there's an analytic solution to this. Any ideas?
>>
>>
>
> That's the formula for applying a rotation in the reference frame of
> another rotation.
>
> Do you know anything more about these matrices than that they are
> matrices? Are they supposed to contain no scale? No translation? If you
> can formulate them as quaternions, writing out the analytical answer is
> a lot simpler :-)
>
> Sincerely,
>
> jw
>
>
>

Re: [Algorithms] solving for multiple matrices

[Gino v. d. B. <gin...@gm...>]

If Y can be considered a rotation then Y is orthogonal and thus Y^-1 = 
Y^T,  in which case this equation can be solved through Cholesky 
decomposition:

For C = Y^T * D * Y, let's decompose

C = U^T * U, and
D = V^T * V

then

U^T U = Y^T * V^T * V * Y
            = (V * Y) ^T * (V * Y)

this gives U = V * Y

and thus Y = V^-1 * U

Basically you are taking the square root of a matrix.

Hope this helps,

Gino 



Andras Balogh wrote:
> Both X and Y matrices represent a simple translation and rotation. For the  
> case of the Y matrix, the translation part will likely to be very small,  
> so I could probably pretend it's only rotation.
>
> What I would really like though, is to find a solution, where I could use  
> more than two equations, eg:
> A1 = X * B1 * Y
> A2 = X * B2 * Y
> A3 = X * B3 * Y
> ...
> An = X * Bn * Y
>
> And then compute a least squares solution from this over-constrained  
> system.
> BTW, when I said that I'm looking for an analytical solution, I just meant  
> something that is not based on an iterative approach. As long as I can get  
> to a part where I have to solve a large system of over-constrained linear  
> equations, I'm home. Unfortunately, I don't know how to make this linear..
>
>
> Andras
>
>
>
>
> On Thu, 17 Sep 2009 16:32:25 -0600, Jon Watte <jw...@gm...> wrote:
>
>   
>> Andras Balogh wrote:
>>     
>>> Then it becomes:
>>> C = Y^-1 * D * Y
>>>
>>> Now, how do I solve this for Y? This form lookes strangely familiar,  
>>> but I
>>> cannot figure out what to do from here (wish I knew how to Google this  
>>> ;).
>>> Hopefully there's an analytic solution to this. Any ideas?
>>>
>>>
>>>       
>> That's the formula for applying a rotation in the reference frame of
>> another rotation.
>>
>> Do you know anything more about these matrices than that they are
>> matrices? Are they supposed to contain no scale? No translation? If you
>> can formulate them as quaternions, writing out the analytical answer is
>> a lot simpler :-)
>>
>> Sincerely,
>>
>> jw
>>
>>
>>
>>     
>
>
>
> ------------------------------------------------------------------------------
> Come build with us! The BlackBerry&reg; Developer Conference in SF, CA
> is the only developer event you need to attend this year. Jumpstart your
> developing skills, take BlackBerry mobile applications to market and stay 
> ahead of the curve. Join us from November 9&#45;12, 2009. Register now&#33;
> http://p.sf.net/sfu/devconf
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
> Archives:
> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list
>   

Re: [Algorithms] solving for multiple matrices

[Staffan L. <sta...@ep...>]

Hi there Gino,

As you most probably already know, Cholesky decomposition can only be
applied to a symmetric, PSD matrix. Even if the matrices only contain
rotational transformations, I don't believe Y^T * D * Y generally would
result in a symmetric, PSD matrix. In particular I don't believe the
assertion C = U^T * U and D = V^T * V is generally true for matrices
containing rotational transformations, since that implies that C and D are
symmetric and PSD.


Best regards,

Staffan Langin

-----Original Message-----
From: Gino van den Bergen [mailto:gin...@gm...] 
Sent: den 18 september 2009 09:59
To: Game Development Algorithms
Subject: Re: [Algorithms] solving for multiple matrices

If Y can be considered a rotation then Y is orthogonal and thus Y^-1 = 
Y^T,  in which case this equation can be solved through Cholesky 
decomposition:

For C = Y^T * D * Y, let's decompose

C = U^T * U, and
D = V^T * V

then

U^T U = Y^T * V^T * V * Y
            = (V * Y) ^T * (V * Y)

this gives U = V * Y

and thus Y = V^-1 * U

Basically you are taking the square root of a matrix.

Hope this helps,

Gino 



Andras Balogh wrote:
> Both X and Y matrices represent a simple translation and rotation. For the

> case of the Y matrix, the translation part will likely to be very small,  
> so I could probably pretend it's only rotation.
>
> What I would really like though, is to find a solution, where I could use

> more than two equations, eg:
> A1 = X * B1 * Y
> A2 = X * B2 * Y
> A3 = X * B3 * Y
> ...
> An = X * Bn * Y
>
> And then compute a least squares solution from this over-constrained  
> system.
> BTW, when I said that I'm looking for an analytical solution, I just meant

> something that is not based on an iterative approach. As long as I can get

> to a part where I have to solve a large system of over-constrained linear

> equations, I'm home. Unfortunately, I don't know how to make this linear..
>
>
> Andras
>
>
>
>
> On Thu, 17 Sep 2009 16:32:25 -0600, Jon Watte <jw...@gm...> wrote:
>
>   
>> Andras Balogh wrote:
>>     
>>> Then it becomes:
>>> C = Y^-1 * D * Y
>>>
>>> Now, how do I solve this for Y? This form lookes strangely familiar,  
>>> but I
>>> cannot figure out what to do from here (wish I knew how to Google this  
>>> ;).
>>> Hopefully there's an analytic solution to this. Any ideas?
>>>
>>>
>>>       
>> That's the formula for applying a rotation in the reference frame of
>> another rotation.
>>
>> Do you know anything more about these matrices than that they are
>> matrices? Are they supposed to contain no scale? No translation? If you
>> can formulate them as quaternions, writing out the analytical answer is
>> a lot simpler :-)
>>
>> Sincerely,
>>
>> jw
>>
>>
>>
>>     
>
>
>
>
----------------------------------------------------------------------------
--
> Come build with us! The BlackBerry&reg; Developer Conference in SF, CA
> is the only developer event you need to attend this year. Jumpstart your
> developing skills, take BlackBerry mobile applications to market and stay 
> ahead of the curve. Join us from November 9&#45;12, 2009. Register
now&#33;
> http://p.sf.net/sfu/devconf
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
> Archives:
> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list
>   


----------------------------------------------------------------------------
--
Come build with us! The BlackBerry&reg; Developer Conference in SF, CA
is the only developer event you need to attend this year. Jumpstart your
developing skills, take BlackBerry mobile applications to market and stay 
ahead of the curve. Join us from November 9&#45;12, 2009. Register now&#33;
http://p.sf.net/sfu/devconf
_______________________________________________
GDAlgorithms-list mailing list
GDA...@li...
https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
Archives:
http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list

Re: [Algorithms] solving for multiple matrices

[Andras B. <and...@gm...>]

Hmm, I just looked up Cholesky decomposition, and it says you can only do  
that if the matrix is symmetric and positive definite. Since the original  
definition of C = A1^-1 * A2, where A1 and A2 both contain arbitrary  
translation and rotation, I don't think C will be symmetric. Or am I  
missing something?

Andras


On Fri, 18 Sep 2009 01:58:41 -0600, Gino van den Bergen  
<gin...@gm...> wrote:

> If Y can be considered a rotation then Y is orthogonal and thus Y^-1 =
> Y^T,  in which case this equation can be solved through Cholesky
> decomposition:
>
> For C = Y^T * D * Y, let's decompose
>
> C = U^T * U, and
> D = V^T * V
>
> then
>
> U^T U = Y^T * V^T * V * Y
>             = (V * Y) ^T * (V * Y)
>
> this gives U = V * Y
>
> and thus Y = V^-1 * U
>
> Basically you are taking the square root of a matrix.
>
> Hope this helps,
>
> Gino
>
>
>
> Andras Balogh wrote:
>> Both X and Y matrices represent a simple translation and rotation. For  
>> the
>> case of the Y matrix, the translation part will likely to be very small,
>> so I could probably pretend it's only rotation.
>>
>> What I would really like though, is to find a solution, where I could  
>> use
>> more than two equations, eg:
>> A1 = X * B1 * Y
>> A2 = X * B2 * Y
>> A3 = X * B3 * Y
>> ...
>> An = X * Bn * Y
>>
>> And then compute a least squares solution from this over-constrained
>> system.
>> BTW, when I said that I'm looking for an analytical solution, I just  
>> meant
>> something that is not based on an iterative approach. As long as I can  
>> get
>> to a part where I have to solve a large system of over-constrained  
>> linear
>> equations, I'm home. Unfortunately, I don't know how to make this  
>> linear..
>>
>>
>> Andras
>>
>>
>>
>>
>> On Thu, 17 Sep 2009 16:32:25 -0600, Jon Watte <jw...@gm...> wrote:
>>
>>
>>> Andras Balogh wrote:
>>>
>>>> Then it becomes:
>>>> C = Y^-1 * D * Y
>>>>
>>>> Now, how do I solve this for Y? This form lookes strangely familiar,
>>>> but I
>>>> cannot figure out what to do from here (wish I knew how to Google this
>>>> ;).
>>>> Hopefully there's an analytic solution to this. Any ideas?
>>>>
>>>>
>>>>
>>> That's the formula for applying a rotation in the reference frame of
>>> another rotation.
>>>
>>> Do you know anything more about these matrices than that they are
>>> matrices? Are they supposed to contain no scale? No translation? If you
>>> can formulate them as quaternions, writing out the analytical answer is
>>> a lot simpler :-)
>>>
>>> Sincerely,
>>>
>>> jw
>>>
>>>
>>>
>>>
>>
>>
>>
>> ------------------------------------------------------------------------------
>> Come build with us! The BlackBerry&reg; Developer Conference in SF, CA
>> is the only developer event you need to attend this year. Jumpstart your
>> developing skills, take BlackBerry mobile applications to market and  
>> stay
>> ahead of the curve. Join us from November 9&#45;12, 2009. Register  
>> now&#33;
>> http://p.sf.net/sfu/devconf
>> _______________________________________________
>> GDAlgorithms-list mailing list
>> GDA...@li...
>> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
>> Archives:
>> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list
>>
>
>
> ------------------------------------------------------------------------------
> Come build with us! The BlackBerry&reg; Developer Conference in SF, CA
> is the only developer event you need to attend this year. Jumpstart your
> developing skills, take BlackBerry mobile applications to market and stay
> ahead of the curve. Join us from November 9&#45;12, 2009. Register  
> now&#33;
> http://p.sf.net/sfu/devconf
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
> Archives:
> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list

Re: [Algorithms] solving for multiple matrices

[Nguyen B. <ng...@gm...>]

You gotta be more precise about your definition of "transformation matrix" here.
Normally, we refer to them as "rotation matrix" which is a member of
SO(3) group. This type of group has been extensively studied and there
are many mathematical tools for you to use.

If you refer to them as homogeneous transformation which also contains
translation then they belong to the set SO(3)xR^3. I don't think you
can do a lot here.

Note that when talking about symmetry, people usually mean "rotation
matrix" as homogeneous matrix is not symmetry by definition.

--------------------------------------------------
Binh Nguyen
Computer Science Department
Rensselaer Polytechnic Institute
Troy, NY, 12180
--------------------------------------------------



On Fri, Sep 18, 2009 at 10:51 AM, Andras Balogh <and...@gm...> wrote:
> Hmm, I just looked up Cholesky decomposition, and it says you can only do
> that if the matrix is symmetric and positive definite. Since the original
> definition of C = A1^-1 * A2, where A1 and A2 both contain arbitrary
> translation and rotation, I don't think C will be symmetric. Or am I
> missing something?
>
> Andras
>
>
> On Fri, 18 Sep 2009 01:58:41 -0600, Gino van den Bergen
> <gin...@gm...> wrote:
>
>> If Y can be considered a rotation then Y is orthogonal and thus Y^-1 =
>> Y^T,  in which case this equation can be solved through Cholesky
>> decomposition:
>>
>> For C = Y^T * D * Y, let's decompose
>>
>> C = U^T * U, and
>> D = V^T * V
>>
>> then
>>
>> U^T U = Y^T * V^T * V * Y
>>             = (V * Y) ^T * (V * Y)
>>
>> this gives U = V * Y
>>
>> and thus Y = V^-1 * U
>>
>> Basically you are taking the square root of a matrix.
>>
>> Hope this helps,
>>
>> Gino
>>
>>
>>
>> Andras Balogh wrote:
>>> Both X and Y matrices represent a simple translation and rotation. For
>>> the
>>> case of the Y matrix, the translation part will likely to be very small,
>>> so I could probably pretend it's only rotation.
>>>
>>> What I would really like though, is to find a solution, where I could
>>> use
>>> more than two equations, eg:
>>> A1 = X * B1 * Y
>>> A2 = X * B2 * Y
>>> A3 = X * B3 * Y
>>> ...
>>> An = X * Bn * Y
>>>
>>> And then compute a least squares solution from this over-constrained
>>> system.
>>> BTW, when I said that I'm looking for an analytical solution, I just
>>> meant
>>> something that is not based on an iterative approach. As long as I can
>>> get
>>> to a part where I have to solve a large system of over-constrained
>>> linear
>>> equations, I'm home. Unfortunately, I don't know how to make this
>>> linear..
>>>
>>>
>>> Andras
>>>
>>>
>>>
>>>
>>> On Thu, 17 Sep 2009 16:32:25 -0600, Jon Watte <jw...@gm...> wrote:
>>>
>>>
>>>> Andras Balogh wrote:
>>>>
>>>>> Then it becomes:
>>>>> C = Y^-1 * D * Y
>>>>>
>>>>> Now, how do I solve this for Y? This form lookes strangely familiar,
>>>>> but I
>>>>> cannot figure out what to do from here (wish I knew how to Google this
>>>>> ;).
>>>>> Hopefully there's an analytic solution to this. Any ideas?
>>>>>
>>>>>
>>>>>
>>>> That's the formula for applying a rotation in the reference frame of
>>>> another rotation.
>>>>
>>>> Do you know anything more about these matrices than that they are
>>>> matrices? Are they supposed to contain no scale? No translation? If you
>>>> can formulate them as quaternions, writing out the analytical answer is
>>>> a lot simpler :-)
>>>>
>>>> Sincerely,
>>>>
>>>> jw
>>>>
>>>>
>>>>
>>>>
>>>
>>>
>>>
>>> ------------------------------------------------------------------------------
>>> Come build with us! The BlackBerry&reg; Developer Conference in SF, CA
>>> is the only developer event you need to attend this year. Jumpstart your
>>> developing skills, take BlackBerry mobile applications to market and
>>> stay
>>> ahead of the curve. Join us from November 9&#45;12, 2009. Register
>>> now&#33;
>>> http://p.sf.net/sfu/devconf
>>> _______________________________________________
>>> GDAlgorithms-list mailing list
>>> GDA...@li...
>>> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
>>> Archives:
>>> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list
>>>
>>
>>
>> ------------------------------------------------------------------------------
>> Come build with us! The BlackBerry&reg; Developer Conference in SF, CA
>> is the only developer event you need to attend this year. Jumpstart your
>> developing skills, take BlackBerry mobile applications to market and stay
>> ahead of the curve. Join us from November 9&#45;12, 2009. Register
>> now&#33;
>> http://p.sf.net/sfu/devconf
>> _______________________________________________
>> GDAlgorithms-list mailing list
>> GDA...@li...
>> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
>> Archives:
>> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list
>
>
>
> ------------------------------------------------------------------------------
> Come build with us! The BlackBerry&reg; Developer Conference in SF, CA
> is the only developer event you need to attend this year. Jumpstart your
> developing skills, take BlackBerry mobile applications to market and stay
> ahead of the curve. Join us from November 9&#45;12, 2009. Register now&#33;
> http://p.sf.net/sfu/devconf
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
> Archives:
> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list
>

Re: [Algorithms] solving for multiple matrices

[Bill B. <wb...@gm...>]

That was my first thought too, but you don't need to a *Cholesky*
decomp on C and D.  Another kind of factorization will do, like a
diagonalization --
http://en.wikipedia.org/wiki/Square_root_of_a_matrix

--bb

On Fri, Sep 18, 2009 at 7:51 AM, Andras Balogh <and...@gm...> wrote:
> Hmm, I just looked up Cholesky decomposition, and it says you can only do
> that if the matrix is symmetric and positive definite. Since the original
> definition of C = A1^-1 * A2, where A1 and A2 both contain arbitrary
> translation and rotation, I don't think C will be symmetric. Or am I
> missing something?
>
> Andras
>
>
> On Fri, 18 Sep 2009 01:58:41 -0600, Gino van den Bergen
> <gin...@gm...> wrote:
>
>> If Y can be considered a rotation then Y is orthogonal and thus Y^-1 =
>> Y^T,  in which case this equation can be solved through Cholesky
>> decomposition:
>>
>> For C = Y^T * D * Y, let's decompose
>>
>> C = U^T * U, and
>> D = V^T * V
>>
>> then
>>
>> U^T U = Y^T * V^T * V * Y
>>             = (V * Y) ^T * (V * Y)
>>
>> this gives U = V * Y
>>
>> and thus Y = V^-1 * U
>>
>> Basically you are taking the square root of a matrix.
>>
>> Hope this helps,
>>
>> Gino
>>
>>
>>
>> Andras Balogh wrote:
>>> Both X and Y matrices represent a simple translation and rotation. For
>>> the
>>> case of the Y matrix, the translation part will likely to be very small,
>>> so I could probably pretend it's only rotation.
>>>
>>> What I would really like though, is to find a solution, where I could
>>> use
>>> more than two equations, eg:
>>> A1 = X * B1 * Y
>>> A2 = X * B2 * Y
>>> A3 = X * B3 * Y
>>> ...
>>> An = X * Bn * Y
>>>
>>> And then compute a least squares solution from this over-constrained
>>> system.
>>> BTW, when I said that I'm looking for an analytical solution, I just
>>> meant
>>> something that is not based on an iterative approach. As long as I can
>>> get
>>> to a part where I have to solve a large system of over-constrained
>>> linear
>>> equations, I'm home. Unfortunately, I don't know how to make this
>>> linear..
>>>
>>>
>>> Andras
>>>
>>>
>>>
>>>
>>> On Thu, 17 Sep 2009 16:32:25 -0600, Jon Watte <jw...@gm...> wrote:
>>>
>>>
>>>> Andras Balogh wrote:
>>>>
>>>>> Then it becomes:
>>>>> C = Y^-1 * D * Y
>>>>>
>>>>> Now, how do I solve this for Y? This form lookes strangely familiar,
>>>>> but I
>>>>> cannot figure out what to do from here (wish I knew how to Google this
>>>>> ;).
>>>>> Hopefully there's an analytic solution to this. Any ideas?
>>>>>
>>>>>
>>>>>
>>>> That's the formula for applying a rotation in the reference frame of
>>>> another rotation.
>>>>
>>>> Do you know anything more about these matrices than that they are
>>>> matrices? Are they supposed to contain no scale? No translation? If you
>>>> can formulate them as quaternions, writing out the analytical answer is
>>>> a lot simpler :-)
>>>>
>>>> Sincerely,
>>>>
>>>> jw
>>>>
>>>>
>>>>
>>>>
>>>
>>>
>>>
>>> ------------------------------------------------------------------------------
>>> Come build with us! The BlackBerry&reg; Developer Conference in SF, CA
>>> is the only developer event you need to attend this year. Jumpstart your
>>> developing skills, take BlackBerry mobile applications to market and
>>> stay
>>> ahead of the curve. Join us from November 9&#45;12, 2009. Register
>>> now&#33;
>>> http://p.sf.net/sfu/devconf
>>> _______________________________________________
>>> GDAlgorithms-list mailing list
>>> GDA...@li...
>>> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
>>> Archives:
>>> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list
>>>
>>
>>
>> ------------------------------------------------------------------------------
>> Come build with us! The BlackBerry&reg; Developer Conference in SF, CA
>> is the only developer event you need to attend this year. Jumpstart your
>> developing skills, take BlackBerry mobile applications to market and stay
>> ahead of the curve. Join us from November 9&#45;12, 2009. Register
>> now&#33;
>> http://p.sf.net/sfu/devconf
>> _______________________________________________
>> GDAlgorithms-list mailing list
>> GDA...@li...
>> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
>> Archives:
>> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list
>
>
>
> ------------------------------------------------------------------------------
> Come build with us! The BlackBerry&reg; Developer Conference in SF, CA
> is the only developer event you need to attend this year. Jumpstart your
> developing skills, take BlackBerry mobile applications to market and stay
> ahead of the curve. Join us from November 9&#45;12, 2009. Register now&#33;
> http://p.sf.net/sfu/devconf
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
> Archives:
> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list
>

Re: [Algorithms] solving for multiple matrices

[Andras B. <and...@gm...>]

Well, I'm not sure how a different factorization will help, but I'll look  
into that. At the same time, I'm also starting to consider an iterative  
approach. What do you guys think? It seems to me that this is basically an  
inverse kinematics problem, right? Any pointers/advice, in case I'll  
decide to take that route?

Thanks,

Andras


On Fri, 18 Sep 2009 10:44:12 -0600, Bill Baxter <wb...@gm...> wrote:

> That was my first thought too, but you don't need to a *Cholesky*
> decomp on C and D.  Another kind of factorization will do, like a
> diagonalization --
> http://en.wikipedia.org/wiki/Square_root_of_a_matrix
>
> --bb
>
> On Fri, Sep 18, 2009 at 7:51 AM, Andras Balogh <and...@gm...>  
> wrote:
>> Hmm, I just looked up Cholesky decomposition, and it says you can only  
>> do
>> that if the matrix is symmetric and positive definite. Since the  
>> original
>> definition of C = A1^-1 * A2, where A1 and A2 both contain arbitrary
>> translation and rotation, I don't think C will be symmetric. Or am I
>> missing something?
>>
>> Andras
>>
>>
>> On Fri, 18 Sep 2009 01:58:41 -0600, Gino van den Bergen
>> <gin...@gm...> wrote:
>>
>>> If Y can be considered a rotation then Y is orthogonal and thus Y^-1 =
>>> Y^T,  in which case this equation can be solved through Cholesky
>>> decomposition:
>>>
>>> For C = Y^T * D * Y, let's decompose
>>>
>>> C = U^T * U, and
>>> D = V^T * V
>>>
>>> then
>>>
>>> U^T U = Y^T * V^T * V * Y
>>>             = (V * Y) ^T * (V * Y)
>>>
>>> this gives U = V * Y
>>>
>>> and thus Y = V^-1 * U
>>>
>>> Basically you are taking the square root of a matrix.
>>>
>>> Hope this helps,
>>>
>>> Gino
>>>
>>>
>>>
>>> Andras Balogh wrote:
>>>> Both X and Y matrices represent a simple translation and rotation. For
>>>> the
>>>> case of the Y matrix, the translation part will likely to be very  
>>>> small,
>>>> so I could probably pretend it's only rotation.
>>>>
>>>> What I would really like though, is to find a solution, where I could
>>>> use
>>>> more than two equations, eg:
>>>> A1 = X * B1 * Y
>>>> A2 = X * B2 * Y
>>>> A3 = X * B3 * Y
>>>> ...
>>>> An = X * Bn * Y
>>>>
>>>> And then compute a least squares solution from this over-constrained
>>>> system.
>>>> BTW, when I said that I'm looking for an analytical solution, I just
>>>> meant
>>>> something that is not based on an iterative approach. As long as I can
>>>> get
>>>> to a part where I have to solve a large system of over-constrained
>>>> linear
>>>> equations, I'm home. Unfortunately, I don't know how to make this
>>>> linear..
>>>>
>>>>
>>>> Andras
>>>>
>>>>
>>>>
>>>>
>>>> On Thu, 17 Sep 2009 16:32:25 -0600, Jon Watte <jw...@gm...>  
>>>> wrote:
>>>>
>>>>
>>>>> Andras Balogh wrote:
>>>>>
>>>>>> Then it becomes:
>>>>>> C = Y^-1 * D * Y
>>>>>>
>>>>>> Now, how do I solve this for Y? This form lookes strangely familiar,
>>>>>> but I
>>>>>> cannot figure out what to do from here (wish I knew how to Google  
>>>>>> this
>>>>>> ;).
>>>>>> Hopefully there's an analytic solution to this. Any ideas?
>>>>>>
>>>>>>
>>>>>>
>>>>> That's the formula for applying a rotation in the reference frame of
>>>>> another rotation.
>>>>>
>>>>> Do you know anything more about these matrices than that they are
>>>>> matrices? Are they supposed to contain no scale? No translation? If  
>>>>> you
>>>>> can formulate them as quaternions, writing out the analytical answer  
>>>>> is
>>>>> a lot simpler :-)
>>>>>
>>>>> Sincerely,
>>>>>
>>>>> jw
>>>>>
>>>>>
>>>>>
>>>>>
>>>>
>>>>
>>>>
>>>> ------------------------------------------------------------------------------
>>>> Come build with us! The BlackBerry&reg; Developer Conference in SF, CA
>>>> is the only developer event you need to attend this year. Jumpstart  
>>>> your
>>>> developing skills, take BlackBerry mobile applications to market and
>>>> stay
>>>> ahead of the curve. Join us from November 9&#45;12, 2009. Register
>>>> now&#33;
>>>> http://p.sf.net/sfu/devconf
>>>> _______________________________________________
>>>> GDAlgorithms-list mailing list
>>>> GDA...@li...
>>>> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
>>>> Archives:
>>>> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list
>>>>
>>>
>>>
>>> ------------------------------------------------------------------------------
>>> Come build with us! The BlackBerry&reg; Developer Conference in SF, CA
>>> is the only developer event you need to attend this year. Jumpstart  
>>> your
>>> developing skills, take BlackBerry mobile applications to market and  
>>> stay
>>> ahead of the curve. Join us from November 9&#45;12, 2009. Register
>>> now&#33;
>>> http://p.sf.net/sfu/devconf
>>> _______________________________________________
>>> GDAlgorithms-list mailing list
>>> GDA...@li...
>>> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
>>> Archives:
>>> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list
>>
>>
>>
>> ------------------------------------------------------------------------------
>> Come build with us! The BlackBerry&reg; Developer Conference in SF, CA
>> is the only developer event you need to attend this year. Jumpstart your
>> developing skills, take BlackBerry mobile applications to market and  
>> stay
>> ahead of the curve. Join us from November 9&#45;12, 2009. Register  
>> now&#33;
>> http://p.sf.net/sfu/devconf
>> _______________________________________________
>> GDAlgorithms-list mailing list
>> GDA...@li...
>> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
>> Archives:
>> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list
>>
>
> ------------------------------------------------------------------------------
> Come build with us! The BlackBerry&reg; Developer Conference in SF, CA
> is the only developer event you need to attend this year. Jumpstart your
> developing skills, take BlackBerry mobile applications to market and stay
> ahead of the curve. Join us from November 9&#45;12, 2009. Register  
> now&#33;
> http://p.sf.net/sfu/devconf
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
> Archives:
> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list

Re: [Algorithms] solving for multiple matrices

[Staffan L. <sta...@ep...>]

Hi there Andras,

C = Y^-1 * D * Y can be linearized by multiplying by Y (from the left).

<=>

Y*C=D*Y

The equation-system, Y*C=D*Y, is trivial to reformulate to the more common
form Ax=b.


Best regards,

Staffan Langin



-----Original Message-----
From: Andras Balogh [mailto:and...@gm...] 
Sent: den 17 september 2009 21:38
To: gda...@li...
Subject: [Algorithms] solving for multiple matrices

Hi, I have a chain of transformations with multiple unknown (but fixed!)
transforms. What I do know is the end result transformation and some of
the transformations in between, and I know these for multiple frames. So
  from here, I'd like to compute the unknowns. Here it is in more formal
version:

I'd like to find 2 unknown matrices X and Y. I have 4 known matrices A1,
A2, B1 and B2, and also know this:
A1 = X * B1 * Y
A2 = X * B2 * Y

I can compute X from the first equation:
X = A1 * Y^-1 * B1^-1

And substitute it into the second:
A2 = A1 * Y^-1 * B1^-1 * B2 * y

Assigning:
C = A1^-1 * A2
D = B1^-1 * B2

Then it becomes:
C = Y^-1 * D * Y

Now, how do I solve this for Y? This form lookes strangely familiar, but I
cannot figure out what to do from here (wish I knew how to Google this ;).  
Hopefully there's an analytic solution to this. Any ideas?

Thanks,



Andras

----------------------------------------------------------------------------
--
Come build with us! The BlackBerry&reg; Developer Conference in SF, CA
is the only developer event you need to attend this year. Jumpstart your
developing skills, take BlackBerry mobile applications to market and stay 
ahead of the curve. Join us from November 9&#45;12, 2009. Register now&#33;
http://p.sf.net/sfu/devconf
_______________________________________________
GDAlgorithms-list mailing list
GDA...@li...
https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
Archives:
http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list

Re: [Algorithms] solving for multiple matrices

[Andras B. <and...@gm...>]

Hah, you're right. I've never realized you could do that. While the  
operations required are indeed trivial, it doesn't seem like I can express  
it with simple matrix operations. So the code to do it will be somewhat  
non-trivial, but that's fine. Thanks!

Andras

On Sat, 19 Sep 2009 08:41:58 -0600, Staffan Langin
<sta...@ep...> wrote:

> Hi there Andras,
>
> C = Y^-1 * D * Y can be linearized by multiplying by Y (from the left).
>
> <=>
>
> Y*C=D*Y
>
> The equation-system, Y*C=D*Y, is trivial to reformulate to the more  
> common
> form Ax=b.
>
>
> Best regards,
>
> Staffan Langin
>
>
>
> -----Original Message-----
> From: Andras Balogh [mailto:and...@gm...]
> Sent: den 17 september 2009 21:38
> To: gda...@li...
> Subject: [Algorithms] solving for multiple matrices
>
> Hi, I have a chain of transformations with multiple unknown (but fixed!)
> transforms. What I do know is the end result transformation and some of
> the transformations in between, and I know these for multiple frames. So
>   from here, I'd like to compute the unknowns. Here it is in more formal
> version:
>
> I'd like to find 2 unknown matrices X and Y. I have 4 known matrices A1,
> A2, B1 and B2, and also know this:
> A1 = X * B1 * Y
> A2 = X * B2 * Y
>
> I can compute X from the first equation:
> X = A1 * Y^-1 * B1^-1
>
> And substitute it into the second:
> A2 = A1 * Y^-1 * B1^-1 * B2 * y
>
> Assigning:
> C = A1^-1 * A2
> D = B1^-1 * B2
>
> Then it becomes:
> C = Y^-1 * D * Y
>
> Now, how do I solve this for Y? This form lookes strangely familiar, but  
> I
> cannot figure out what to do from here (wish I knew how to Google this  
> ;).
> Hopefully there's an analytic solution to this. Any ideas?
>
> Thanks,
>
>
>
> Andras
>
> ----------------------------------------------------------------------------
> --
> Come build with us! The BlackBerry&reg; Developer Conference in SF, CA
> is the only developer event you need to attend this year. Jumpstart your
> developing skills, take BlackBerry mobile applications to market and stay
> ahead of the curve. Join us from November 9&#45;12, 2009. Register  
> now&#33;
> http://p.sf.net/sfu/devconf
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
> Archives:
> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list
>
>
> ------------------------------------------------------------------------------
> Come build with us! The BlackBerry&reg; Developer Conference in SF, CA
> is the only developer event you need to attend this year. Jumpstart your
> developing skills, take BlackBerry mobile applications to market and stay
> ahead of the curve. Join us from November 9&#45;12, 2009. Register  
> now&#33;
> http://p.sf.net/sfu/devconf
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
> Archives:
> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list