KDL svd_eigen_HH algorithm

Hi,

We're using the svd_eigen_HH algorithm of KDL
https://github.com/orocos/orocos_kinematics_dynamics/blob/master/orocos_...
Which should do a singular value decomposition of eigenmatrices using
the Householder transformations.

One of the properties of singular values is that the values are always
positive.
However, the algorithm does output sometimes negative values!
Typically a 1 becomes a -1.
The returned result does make some sense (U*S*V' does return the
original matrix),
hence we ruled out that the algorithm was interrupted somehow, or used
bad data.

However, we are unable to recreate the problem in a small subset,
even with exact the same inputs as given at runtime.

There is very little documentation on input and output, only the
required size of matrices,
and variable names in the code are not descriptive...
Does anyone have an idea whether the algorithm can return negative S values?
Line 174 mentions (and does) 'Singular value is made nonnegative.',
although the values are manipulated further on...
Does anyone could give us possible causes or a hint on how to recreate
the problem?

example:
if you run the algorithm on the matrix Jf below, you would normally get:
Sf: (the singular values)
1.16694
1.16694
1
1
0.856941
0.856941

However now it returns:
Sf:
1.16694
1.16694
1
0.856941
0.856941
-1

the algorithm:
svd_eigen_HH(Jf, Uf, Sf, Vf, temp)

input:
temp:
0
7.52316e-36
0
0
1.24602e-35
0

Jf: 1 0 0 0 -0.31
-1.70024e-33
0 -1 -1.22461e-16 -0.31 0 0
0 1.22461e-16 -1 3.79628e-17 0 0
0 0 0 1 0 0
0 0 0 0 -1
-1.22461e-16
0 0 0 0
1.22461e-16 -1
(The matrix is negative definite, hence you would expect negative
_eigenvalues_...)

output:
Uf: -0.759332 1.84585e-17 -1.86641e-32 0.638111 -0.127391
-3.05582e-32
-9.69548e-17 -0.759332 -8.91122e-17 -0.127391 -0.638111 6.88099e-17
-8.71483e-33 -3.58457e-16 -0.797647 6.76459e-17 3.38842e-16 0.603124
5.50775e-17 0.650703 -2.8027e-16 -0.148658 -0.744638
2.17033e-16
-0.650703 1.33574e-16 7.3859e-17 -0.744638 0.148658
9.76804e-17
7.96855e-17 -4.55151e-32 0.603124 9.11889e-17 -1.82048e-17 0.797647

Sf:
1.16694
1.16694
1
0.856941
0.856941
-1
Vf:
-0.650703 -3.14419e-18 -1.86641e-32 0.744638 -0.148658 3.05582e-32
1.14627e-16 0.650703 8.65715e-17 0.148658 0.744638
6.51196e-17
1.6563e-32 1.79184e-16 0.797647 -5.36816e-17 -2.68894e-16 0.603124
7.48371e-17 0.759332 -3.01999e-16 -0.127391 -0.638111
-2.27218e-16
0.759332 -1.53333e-16 9.24941e-33 0.638111 -0.127391
3.99573e-35
2.73502e-32 -6.13455e-32 -0.603124 5.50262e-32 3.956e-31 0.797647
temp:
0
2.26598e-17
0
-5.50571e-21
0
3.90313e-17

Nick

Ruben Smits's picture

KDL svd_eigen_HH algorithm

What was the return value of svd_eigen_HH, maybe the computation failed and
the results should not be trusted? (This is a long shot I know ;)

R.

On Thu, May 21, 2015 at 7:02 PM, Dominick Vanthienen <
nick [dot] vanthienen [..] ...> wrote:

> Hi,
>
> We're using the svd_eigen_HH algorithm of KDL
>
> https://github.com/orocos/orocos_kinematics_dynamics/blob/master/orocos_...
> Which should do a singular value decomposition of eigenmatrices using
> the Householder transformations.
>
> One of the properties of singular values is that the values are always
> positive.
> However, the algorithm does output sometimes negative values!
> Typically a 1 becomes a -1.
> The returned result does make some sense (U*S*V' does return the
> original matrix),
> hence we ruled out that the algorithm was interrupted somehow, or used
> bad data.
>
> However, we are unable to recreate the problem in a small subset,
> even with exact the same inputs as given at runtime.
>
> There is very little documentation on input and output, only the
> required size of matrices,
> and variable names in the code are not descriptive...
> Does anyone have an idea whether the algorithm can return negative S
> values?
> Line 174 mentions (and does) 'Singular value is made nonnegative.',
> although the values are manipulated further on...
> Does anyone could give us possible causes or a hint on how to recreate
> the problem?
>
> example:
> if you run the algorithm on the matrix Jf below, you would normally get:
> Sf: (the singular values)
> 1.16694
> 1.16694
> 1
> 1
> 0.856941
> 0.856941
>
> However now it returns:
> Sf:
> 1.16694
> 1.16694
> 1
> 0.856941
> 0.856941
> -1
>
> the algorithm:
> svd_eigen_HH(Jf, Uf, Sf, Vf, temp)
>
> input:
> temp:
> 0
> 7.52316e-36
> 0
> 0
> 1.24602e-35
> 0
>
> Jf: 1 0 0 0 -0.31
> -1.70024e-33
> 0 -1 -1.22461e-16 -0.31 0 0
> 0 1.22461e-16 -1 3.79628e-17 0 0
> 0 0 0 1 0 0
> 0 0 0 0 -1
> -1.22461e-16
> 0 0 0 0
> 1.22461e-16 -1
> (The matrix is negative definite, hence you would expect negative
> _eigenvalues_...)
>
> output:
> Uf: -0.759332 1.84585e-17 -1.86641e-32 0.638111 -0.127391
> -3.05582e-32
> -9.69548e-17 -0.759332 -8.91122e-17 -0.127391 -0.638111
> 6.88099e-17
> -8.71483e-33 -3.58457e-16 -0.797647 6.76459e-17 3.38842e-16 0.603124
> 5.50775e-17 0.650703 -2.8027e-16 -0.148658 -0.744638
> 2.17033e-16
> -0.650703 1.33574e-16 7.3859e-17 -0.744638 0.148658
> 9.76804e-17
> 7.96855e-17 -4.55151e-32 0.603124 9.11889e-17 -1.82048e-17 0.797647
>
> Sf:
> 1.16694
> 1.16694
> 1
> 0.856941
> 0.856941
> -1
> Vf:
> -0.650703 -3.14419e-18 -1.86641e-32 0.744638 -0.148658 3.05582e-32
> 1.14627e-16 0.650703 8.65715e-17 0.148658 0.744638
> 6.51196e-17
> 1.6563e-32 1.79184e-16 0.797647 -5.36816e-17 -2.68894e-16 0.603124
> 7.48371e-17 0.759332 -3.01999e-16 -0.127391 -0.638111
> -2.27218e-16
> 0.759332 -1.53333e-16 9.24941e-33 0.638111 -0.127391
> 3.99573e-35
> 2.73502e-32 -6.13455e-32 -0.603124 5.50262e-32 3.956e-31 0.797647
> temp:
> 0
> 2.26598e-17
> 0
> -5.50571e-21
> 0
> 3.90313e-17
>
>
> Nick
>
>
> --
> Orocos-Users mailing list
> Orocos-Users [..] ...
> http://lists.mech.kuleuven.be/mailman/listinfo/orocos-users
>

KDL svd_eigen_HH algorithm

On 06/03/2015 10:12 AM, Ruben Smits wrote:
> What was the return value of svd_eigen_HH, maybe the computation
> failed and the results should not be trusted? (This is a long shot I
> know ;)
The return value was/is OK, also the result is numerically ok, just not
for the convention of no negative singular values.
It seems that the algorithm only checks for negative singular values
half-way, so doing this again at the end should solve the problem.
I'll test and make a patch.

Nick

>
> R.
>
> On Thu, May 21, 2015 at 7:02 PM, Dominick Vanthienen
> <nick [dot] vanthienen [..] ... <mailto:nick [dot] vanthienen [..] ...>> wrote:
>
> Hi,
>
> We're using the svd_eigen_HH algorithm of KDL
> https://github.com/orocos/orocos_kinematics_dynamics/blob/master/orocos_...
> Which should do a singular value decomposition of eigenmatrices using
> the Householder transformations.
>
> One of the properties of singular values is that the values are always
> positive.
> However, the algorithm does output sometimes negative values!
> Typically a 1 becomes a -1.
> The returned result does make some sense (U*S*V' does return the
> original matrix),
> hence we ruled out that the algorithm was interrupted somehow, or used
> bad data.
>
> However, we are unable to recreate the problem in a small subset,
> even with exact the same inputs as given at runtime.
>
> There is very little documentation on input and output, only the
> required size of matrices,
> and variable names in the code are not descriptive...
> Does anyone have an idea whether the algorithm can return negative
> S values?
> Line 174 mentions (and does) 'Singular value is made nonnegative.',
> although the values are manipulated further on...
> Does anyone could give us possible causes or a hint on how to recreate
> the problem?
>
> example:
> if you run the algorithm on the matrix Jf below, you would
> normally get:
> Sf: (the singular values)
> 1.16694
> 1.16694
> 1
> 1
> 0.856941
> 0.856941
>
> However now it returns:
> Sf:
> 1.16694
> 1.16694
> 1
> 0.856941
> 0.856941
> -1
>
> the algorithm:
> svd_eigen_HH(Jf, Uf, Sf, Vf, temp)
>
> input:
> temp:
> 0
> 7.52316e-36
> 0
> 0
> 1.24602e-35
> 0
>
> Jf: 1 0 0 0 -0.31
> -1.70024e-33
> 0 -1 -1.22461e-16 -0.31 0 0
> 0 1.22461e-16 -1 3.79628e-17 0 0
> 0 0 0 1 0 0
> 0 0 0 0 -1
> -1.22461e-16
> 0 0 0 0
> 1.22461e-16 -1
> (The matrix is negative definite, hence you would expect negative
> _eigenvalues_...)
>
> output:
> Uf: -0.759332 1.84585e-17 -1.86641e-32 0.638111 -0.127391
> -3.05582e-32
> -9.69548e-17 -0.759332 -8.91122e-17 -0.127391 -0.638111
> 6.88099e-17
> -8.71483e-33 -3.58457e-16 -0.797647 6.76459e-17 3.38842e-16
> 0.603124
> 5.50775e-17 0.650703 -2.8027e-16 -0.148658 -0.744638
> 2.17033e-16
> -0.650703 1.33574e-16 7.3859e-17 -0.744638 0.148658
> 9.76804e-17
> 7.96855e-17 -4.55151e-32 0.603124 9.11889e-17 -1.82048e-17
> 0.797647
>
> Sf:
> 1.16694
> 1.16694
> 1
> 0.856941
> 0.856941
> -1
> Vf:
> -0.650703 -3.14419e-18 -1.86641e-32 0.744638 -0.148658 3.05582e-32
> 1.14627e-16 0.650703 8.65715e-17 0.148658 0.744638
> 6.51196e-17
> 1.6563e-32 1.79184e-16 0.797647 -5.36816e-17 -2.68894e-16
> 0.603124
> 7.48371e-17 0.759332 -3.01999e-16 -0.127391 -0.638111
> -2.27218e-16
> 0.759332 -1.53333e-16 9.24941e-33 0.638111 -0.127391
> 3.99573e-35
> 2.73502e-32 -6.13455e-32 -0.603124 5.50262e-32 3.956e-31
> 0.797647
> temp:
> 0
> 2.26598e-17
> 0
> -5.50571e-21
> 0
> 3.90313e-17
>
>
> Nick
>
>
> --
> Orocos-Users mailing list
> Orocos-Users [..] ...
> <mailto:Orocos-Users [..] ...>
> http://lists.mech.kuleuven.be/mailman/listinfo/orocos-users
>
>
>
>