|Re: [eigen] Re: Complete orthogonal decomposition rank computation corner case|
[ Thread Index |
| More lists.tuxfamily.org/eigen Archives
- To: eigen <eigen@xxxxxxxxxxxxxxxxxxx>
- Subject: Re: [eigen] Re: Complete orthogonal decomposition rank computation corner case
- From: Simon Rutishauser <simon.rutishauser@xxxxxxxxx>
- Date: Mon, 27 Jun 2016 10:14:39 +0200
- Dkim-signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=pix4d.com; s=google; h=from:to:subject:date:message-id:user-agent:in-reply-to:references :mime-version:content-transfer-encoding; bh=ogZf9lNhycaxRLLlRdI08oaYUYQRbj/ILn75rPwUsbs=; b=h7qo2JEBVvWazlXCLbeMvJitssOIOEJ7jZEYevp2mxXimvS2lT11kzUd4Dd7ZPeqRe BbrWv7EP87ewlMdq20/5xedG0djjjZwpHc8XpJeZr+fBVRWG2b5Cr1lIMP5OOTttim97 P5qd2VRA41U2s3ymelFh8Ae8oSVlilRP7kR2s=
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.
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
> 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.
> On Fri, Jun 24, 2016 at 1:01 AM, Gael Guennebaud <gael.guennebaud@xxxxxxxxx>
> > 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.
EPFL Innovation Park - D
1015 Lausanne - Switzerland
t: +41 (0) 21 552 05 94