Re: [eigen] Fast tall QR for least squares |

[ Thread Index | Date Index | More lists.tuxfamily.org/eigen Archives ]

*To*: eigen <eigen@xxxxxxxxxxxxxxxxxxx>*Subject*: Re: [eigen] Fast tall QR for least squares*From*: Gael Guennebaud <gael.guennebaud@xxxxxxxxx>*Date*: Sun, 24 Feb 2013 15:39:45 +0100*Dkim-signature*: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=x-received:mime-version:in-reply-to:references:from:date:message-id :subject:to:content-type; bh=3ILjWqKSafQtoJM4mlHJcuM7qIMs3oSDrXCAtJ0mM0M=; b=JLCfQPJkMpA7qUqckh7sD/xNcBIrDC1GDgIUn7zzoUJdkwnT5mxJ3QID/ug0OLeiRs /U2gRccGIDmh6mGYXKYGYEzP49YbHDl9HJlJ34VpBCRwdbGPEGOR6RAIskSCxn696+ED pthrw+x3xWDKhik/EKRc8c2CKlHZSK38VBtresi7u6/PBdHuERgExdb6eRmrIpjQK0Ak Gh41EM/SWpkinVj3MHNWj6L0yGcaDiX3Mu6x32gNps5InwdnR2N7Ns4+yPh+PjuIkCSz wEvHk8horoixU1Ra7m0hWUYREAz6eTa9MTuY+Rbrn42dNhKZlxIMHedRhnoIPm+9fBhZ a/yQ==

Hi, the best would be to "blockify" ColPivHouseholderQR on our side... In the meantime, one option might be to start with HouseholderQR (which should be an order of magnitude faster) and fallback to column pivoting only when needed, i.e., when two columns are (nearly) linearly dependent. I think that this situation can be detected from the diagonal entries of the resulting R factor, namely: if(qr.matrixQR().diagonal().maxCoeff() * NumTraits<Scalar>::dummy_precision() > qr.matrixQR().diagonal().minCoeff()) { // fallback to ColPivHouseholderQR } cheers, Gael. On Sun, Feb 24, 2013 at 12:03 AM, Keir Mierle <mierle@xxxxxxxxx> wrote: > Currently Ceres runs a QR decomposition for dense nonlinear solving in the > heart of the Levenberg-Marquardt loop is as follows: > > VectorRef(x, num_cols) = A->matrix().colPivHouseholderQr().solve(rhs_); > > This is the performance limiting step in Ceres for dense problems. The A > matrix tends to be very tall and not especially wide; in other words, it is > an overdetermined system. You might ask why not use Cholesky, and the answer > is that forming the A'A matrix is sufficiently expensive to make running > Cholesky slower than QR. > > Any ideas on how to make this solve faster than it is currently? > > Thanks! > Keir > >

**Follow-Ups**:**Re: [eigen] Fast tall QR for least squares***From:*Désiré NUENTSA WAKAM

**References**:**[eigen] Fast tall QR for least squares***From:*Keir Mierle

**Messages sorted by:**[ date | thread ]- Prev by Date:
**[eigen] Fast tall QR for least squares** - Next by Date:
**Re: [eigen] Fast tall QR for least squares** - Previous by thread:
**[eigen] Fast tall QR for least squares** - Next by thread:
**Re: [eigen] Fast tall QR for least squares**

Mail converted by MHonArc 2.6.19+ | http://listengine.tuxfamily.org/ |