Re: [eigen] Re: Complete orthogonal decomposition rank computation corner case

[Simon Rutishauser <simon.rutishauser@xxxxxxxxx>]

Hello,

I tried 3.2.8 (+ COD backport), no difference in the results to 3.2.6. Next I backported 9da6c621 and 6901ee728 to my branch, as suggested by Rasmus. That fixes the issue for the specific data where I observed it (hardly surprising, considering it is a corner case in rank detection and those commits change how the rank detection works). 

I'll run with this for now and then we'll see if I observe such issues again.

In general I agree that this is a valid corner case that may appear every once in a while for numerical reasons.

- Simon

On Friday 24 June 2016 08.33:12 Rasmus Larsen wrote:
> Yes, I am going to investigate this issue. The 3.2.x version you patched it
> into does not have the improvements to the norm updating formula (and thus
> rank determination) in CPQR I submitted in
> https://bitbucket.org/eigen/eigen/commits/9da6c621d055e425605362c92c5dd1f7768e9681.
> You should first try backporting that to your codebase (or even better to
> the Eigen 3.2 branch). That being said, I can envision corner cases where
> applying the final orthogonal transformation in COD (which mathematically
> do not affect the rank) could push a close value across the threshold.
> 
> Rasmus
> 
> On Fri, Jun 24, 2016 at 1:01 AM, Gael Guennebaud <gael.guennebaud@xxxxxxxxx>
> wrote:
> 
> > Hi,
> >
> > In my opinion this is hiding a more fundamental issue, and this patch
> > would just hide it for eternity... We should rather try to understand why
> > the rank does change, but since the issue does not occur with 3.3, maybe
> > the problem comes from 3.2.6's ColPivHouseholderQR or from a shortcoming in
> > your backport. What if you upgrade to 3.2's head?
> >
> > gael
> >
> > On Fri, Jun 24, 2016 at 12:43 AM, Rasmus Larsen <rmlarsen@xxxxxxxxxx>
> > wrote:
> >
> >> Hi Simon,
> >>
> >> Thanks for the patch. I've just gotten back from vacation, but it seems
> >> reasonable to me. I'll look more carefully shortly.
> >>
> >> Rasmus
> >>
> >> On Wed, Jun 15, 2016 at 11:41 PM, Simon Rutishauser <
> >> simon.rutishauser@xxxxxxxxx> wrote:
> >>
> >>> Hi list and Rasmus,
> >>>
> >>> I have been playing around with the complete orthogonal decomposition
> >>> that was recently added to Eigen,
> >>> and I think I have ran into a corner case:
> >>>
> >>> I have a matrix of size 70 where the rank() in the
> >>> CompleteOrthogonalDecomposition::compute() method is 69,
> >>> it thus performs the additional Householder reflections. After those
> >>> reflections, the rank() method returns 70.
> >>>
> >>> Next I run the pseudoInverse() method, which in consequence skips the
> >>> applyZAdjointOnTheLeftInPlace() step.
> >>> The resulting matrix is completely wrong.
> >>>
> >>> The solution, as far as I can see it, would be to the rank() obtained
> >>> directly after the QR decomposition
> >>> and then stick with it.
> >>>
> >>> What do you think? I have attached a proposed patch.
> >>>
> >>> Simon
> >>>
> >>> P.S. I'd love to provide an example matrix that triggers this behaviour,
> >>> but unfortunately I only observe
> >>> this corner-case on Eigen 3.2.6 with a backported
> >>> CompleteOrthogonalDecomposition. So the issues I am
> >>> observing may also have other origins.
> >>
> >>
> >>
> >

-- 
Simon Rutishauser

Pix4D SA
EPFL Innovation Park - D
1015 Lausanne - Switzerland
t: +41 (0) 21 552 05 94
Email: simon.rutishauser@xxxxxxxxx
www.pix4d.com