|[eigen] Fast tall QR for least squares|
[ Thread Index |
| More lists.tuxfamily.org/eigen Archives
- To: eigen <eigen@xxxxxxxxxxxxxxxxxxx>
- Subject: [eigen] Fast tall QR for least squares
- From: Keir Mierle <mierle@xxxxxxxxx>
- Date: Sat, 23 Feb 2013 15:03:15 -0800
- Dkim-signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:x-received:date:message-id:subject:from:to :content-type; bh=Zfa6GPTOWLDcR5vD+lt1B4BBD0vl9CaACCXrC+WjGOI=; b=IBjmJos1cK4RdhOMbtyfbyQd/VfWcLZiGLaAbSno07MxP77gFyCrQBM1R6Q2/Qr5cr rOALhRlbB49W2e0vGZsuS5shZRJfv71J9pLc0dMHLuKgst+S8eZm8E8Vkk6HnUuWZclt xBxzyQlp5YVTMDzt3UntVWDKIxZYQJwqSR0WfZCSRoe3rTzV0fwSiSlpx6vgH/Qnacck gsWbIU+0EMvq5umz/Isfmyf6YeU0HdKqq5E662UMfU7VZoGBU7Y/2TocbYLH9fv/nTiw YDas5rAJmxU6NCR0GQzAtzGu42P88ZpTUxufThxVnbJvFwmLSkSrVYMLzJ3gDRP7Tslm 9SSQ==
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?