Singular Value Decomposition (cv::SVD::compute(A, w, u, vt)) may generate incorrect calculated left singular vectors(u).

[xvvzhang]

System information (version)

• OpenCV => 4.5.4-dev
• Operating System / Platform => Ubuntu
• Compiler => g++

Detailed description

Singular Value Decomposition (cv::SVD::compute(A, w, u, vt)) may generate incorrect calculated left singular vectors(u).

For example, when the input matrix A =
[0, 0, 0;
1, 0, 0;
0, 0, 0]

The calculated left singular vectors, u, should be
[0, -1, 0;
-1, 0, 0;
0, 0, 1]

However, the actual output is
[0, -0.70710677, -0.70710677;
1, 0, 0;
0, 0.70710677, -0.70710677]

Another example:
Input matrix A =
[0, 0, 0;
1, 0, 1;
0, 0, 0]

Expected output u =
[0, -1, 0;
-1, 0, 1;
0, 0, 1]

The actual output u =
[0, -0.70710677, -0.70710677;
1, 0, 0 ;
0, 0.70710677, -0.70710677]

Steps to reproduce

#include <iostream>
#include <opencv2/opencv.hpp>

using namespace std;
using namespace cv;

int main() {

    cv::Mat A = cv::Mat(3, 3, CV_32F)
    = (cv::Mat_<float>(3, 3, CV_32F)
       <<
       0, 0, 0,
       1, 0, 0,
       0, 0, 0);
    
    Mat u, w, vt;
    SVD::compute(A, w, u, vt);

    cout << "u:" << endl;
    cout << u << endl << endl;

    return 0;
}

Issue submission checklist

• I report the issue, it's not a question
• I checked the problem with documentation, FAQ, open issues,
  forum.opencv.org, Stack Overflow, etc and have not found solution
• I updated to latest OpenCV version and the issue is still there
• There is reproducer code and related data files: videos, images, onnx, etc

[xvvzhang]

I found this problem when I tried to sample inside hyperellipsoids uniformly. I followed the method described in Informed RRT*: Optimal Incremental Path Planning Focused through an Admissible Ellipsoidal Heuristic. However, with cv::SVD::compute(), the minor axes I got are .5^.5 of the correct value. Sometimes minor axes collapse into zero.
Then I tied Numpy, Eigen, Octave. They work well to produce the correct result.

[alalek]

The calculated left singular vectors, u, should be

The SVD is not unique in general.

Which property or equation of SVD is broken?

[xvvzhang]

The calculated left singular vectors, u, should be

The SVD is not unique in general.

Which property or equation of SVD is broken?

Sorry for my imprecise description. The SVD is not unique. But, for singular values equal to zero, their singular vectors may contain some strange things like 0.70710677(.5^.5). These values don't matter for pseudo-inverse or matrix recovery because the singular values are zero. However, they are not negligible for independent u and v operations. I suppose the problem is from JacobiImpl_. The Eigen::JacobiSVD also works well for me.

[AleksandrPanov]

The calculated left singular vectors, u, should be

The SVD is not unique in general.
Which property or equation of SVD is broken?

Sorry for my imprecise description. The SVD is not unique. But, for singular values equal to zero, their singular vectors may contain some strange things like 0.70710677(.5^.5). These values don't matter for pseudo-inverse or matrix recovery because the singular values are zero. However, they are not negligible for independent u and v operations. I suppose the problem is from JacobiImpl_. The Eigen::JacobiSVD also works well for me.

Indeed, there are no problems in recovering matrix A.
cv::Mat recoveredA = u * W * vt;
recoverA.cpp.txt

Why is the value 0.70710677(.5^.5) strange? What is the problem in your opinion?

[xvvzhang]

The calculated left singular vectors, u, should be

The SVD is not unique in general.
Which property or equation of SVD is broken?

Sorry for my imprecise description. The SVD is not unique. But, for singular values equal to zero, their singular vectors may contain some strange things like 0.70710677(.5^.5). These values don't matter for pseudo-inverse or matrix recovery because the singular values are zero. However, they are not negligible for independent u and v operations. I suppose the problem is from JacobiImpl_. The Eigen::JacobiSVD also works well for me.

Indeed, there are no problems in recovering matrix A. cv::Mat recoveredA = u * W * vt; recoverA.cpp.txt

Why is the value 0.70710677(.5^.5) strange? What is the problem in your opinion?

The result of SVD::compute cannot reproduce a unique rotation matrix mentioned in the paper by u and v.

The matrix is C = U * diag { 1, . . . , 1, det (U) det (V) } * V.t().

I also calculated the SVD of the [0,0,0;1,0,0;0,0,0] manually and got the same result as Eigen's. I think the value is strange because the vectors haven't cleaned for zero singular values. I guess the developer might find a shortcut to avoid Jacobi iterations of singular vectors which position corresponding to zero singular values but finally forgot to clean it. I just skimmed through the source code. I am going to review it.

I will post my sampling code and its visualization if needed.