Constraints are not strictly satisfied.

[g9nkn]

I found that estimated essential matrices are not strictly constrained. For example, Eigen::JacobiSVD returns the singular values of an E-matrix are like [0.9999999997904632, 0.9999999965792381, 8.520915197261778e-05], which cannot be said as an approximation of [1.0, 1.0, 0.0]. Neither det(E)=0 nor E*E^T*E - 1/2*trace(E*E^T)*E = 0 is not satisfied. So I have two questions.

1. Do you replace the singular values with [1.0, 1.0, 0.0] to recover the rotation R and translation t?
2. I think this is caused by that the rank-1 constraint, rank(Xe)=rank(Xt)=1, is not satisfied enough. I tried smaller threshold of epsilonDash and epsilonStar , from 10^-10 to 10^-15, in the SDPA options to make the duality gap smaller, however, I still got rank(Xe)=9 and rank(Xt)=3. Do you have a quick remedy or an extra regularization term for enforcing the rank-1 constraint?

Thanks.

[jizhaox]

First of all, your results should be reasonable. We have discussed the pose recovery in Sec. 4.1 of the paper. It is widely used to set the rank of a matrix as the number of singular values larger than a threshold. Ideally, this threshold should be zero. In practice, the smallest singular value of the recovered essential matrix cannot be zero, and usually it is larger than the default threshold in rank determination functions. When the relaxation is tight, the rank problem is a computational issue caused by the numerical accuracy and termination conditions of SDP solvers.

1. If we only care about application aspects, we can replace the singular values of E-matrix with [1, 1, 0] to recover the rotation and translation. The influence is negligible because the exact optima under the algebraic error do not mean the recovered pose is also optimal for performance evaluation.

2. To reduce the duality gap, a straightforward method is adjusting parameters as you did. But the gap can hardly vanish in this way. To achieve the exact optima, I have two suggestions. First, we can post-process the results to find the exact optima. Recall that the formulation of this method is trying to minimize the algebraic error. And this method can find a solution that is globally optimal with certain theoretical guarantee, and is sufficiently near the optima in practice. So we can apply a local minimization method, such as [Kneip & Lynen, Direct Optimization of Frame-to-Frame Rotation. ICCV’2013] with code [https://github.com/laurentkneip/opengv], to refine the results. I found this method works well. Second, we may develop a customized SDP solver. Since we know the rank of optimal Xe and Xt, we can strictly enforce these constraints during internal iterations of SDP solvers. This method is more complex than post-processing. I saw a related work that might be of inspiration [Yang, et al. STRIDE along Spectrahedral Vertices for Solving Large-Scale Rank-One Semidefinite Relaxations. 2021]

[g9nkn]

Thank you for the explanation. Let me ask for a bit more details.

1. Did you just apply "the standard method in literature [1]" to recover the relative motion in the experiment in Sec. 7? I think it is equivalent to the singular value enforcement by replacing with [1,1,0], is it correct? The paper doesn't mention a solution refinement by a local minimization such as OpenGV.
2. (Just a comment) I implemented your method in MATLAB with SeDuMi to calculate solutions until reaching a duality gap in the machine epsilon, 1e-16 to 1e-20. Unfortunately, even with achieving such a very tight gap, the rank-1 constraint was not satisfied well. The second-largest eigenvalue of Xe is 1e-13, almost rank(Xe)=1, but that of Xt is around 1e-4, still rank(Xt)=3. I'm not sure this is the limitation of the SDP solvers, but your two suggestions may be promising in practice.

Thanks.

[jizhaox]

1. Yes, your understanding is correct. The results reported in the paper are without post-processing, so I did not mention it. In our later work [A Certifiably Globally Optimal Solution to Generalized Essential Matrix Estimation, CVPR, 2020], we did apply post-processing for generalized camera cases. The combination of global and local optimizations is similar to the Suggest-and-Improve framework [Park & Boyd, General Heuristics for Nonconvex Quadratically Constrained Quadratic Programming, 2017].

2. I think the issue is caused by SDP solvers. To verify this point, you can perform an experiment with the following steps. First, generate synthetic data with small or zero noise. The relaxation should be tight for these cases. Second, construct a valid solution using the ground truth or enforce the resulted solution to satisfy the rank-1 constraints. Third, substitute the solutions into the objective. You can find that the constructed solutions strictly satisfy all the necessary constraints and sometimes they have smaller objective values than the resulted solutions.

[g9nkn]

Now I understand the paper well. Thank you very much for the discussion.