Re: [eigen] request for comments / help

[Helmut Jarausch <jarausch@xxxxxxxxxxxxxxxxxxx>]

On 06/13/2012 07:06:24 PM, Gael Guennebaud wrote:
> Well, I have no doubt that in most cases QR-Cholesky works fine and is
> pretty efficient, however Cholesky involves squaring thus reducing
> numerical accuracy. So I'm tempted to favor a full orthogonalization
> method. This is also the approach followed by Lapack (dgelsy).
>
> Nevertheless your approach has the advantage of simplicity and being
> already implemented! So if you're ok I propose in a first step to add
> it in unsupported/, I'm sure it might be useful to many users.

Yes, of course, it's fine to add it to unsupported.
Just for the record:

Ake Björck, Numerical Methods for Least Squares Problems, SIAM 1996
mentions this method in chap 2.7. He cites an example from Kahan

A = R = diag(1,s,s^2,s^3,...,s^{n-1}) *   ( 1 -c  .  .  .  . -c )
                                            0  1 -c  .  .  .  .
                                            0  0  1 -c  .  .  .
                                                     1  .  .  .
                                                        1  . -c
                                                           1 -c )
For n=100 und c=0.2 the smallest singular value is 0.368E-8  while
the lower right element of R is 0.133
Column pivoting with this matrix doesn't permute any columns.
Therefore the near singularity of this matrix is not recognized.
The method has been analyzed by
Deuflhard / Sautter
"On rank-deficient pseudoinverses"
Lin. Alg. Appl. 29 (1980), pp 91-111

For an improved but more expensive version see
chapter 2.7.5 in Ake Björck's book.

Helmut.