From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 7797 invoked by alias); 26 Feb 2014 22:44:11 -0000 Mailing-List: contact gsl-discuss-help@sourceware.org; run by ezmlm Precedence: bulk List-Id: List-Subscribe: List-Archive: List-Post: List-Help: , Sender: gsl-discuss-owner@sourceware.org Received: (qmail 7780 invoked by uid 89); 26 Feb 2014 22:44:09 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-0.3 required=5.0 tests=AWL,BAYES_50,RP_MATCHES_RCVD,SPF_PASS autolearn=ham version=3.3.2 X-HELO: ipmx6.colorado.edu Received: from ipmx6.colorado.edu (HELO ipmx6.colorado.edu) (128.138.128.246) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Wed, 26 Feb 2014 22:44:08 +0000 From: Patrick Alken Received: from bonanza.ngdc.noaa.gov ([140.172.179.41]) by smtp.colorado.edu with ESMTP/TLS/DHE-RSA-AES256-SHA; 26 Feb 2014 15:44:05 -0700 Message-ID: <530E6E34.1050102@colorado.edu> Date: Wed, 26 Feb 2014 22:44:00 -0000 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:24.0) Gecko/20100101 Thunderbird/24.3.0 MIME-Version: 1.0 To: "gsl-discuss@sourceware.org" Subject: Changes in nonlinear least squares module Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit X-SW-Source: 2014-q1/txt/msg00025.txt.bz2 Hello all, I've been working a lot on the nonlinear least squares module lately, and wanted to inform everyone of some changes. 1) There is a brand new Levenberg-Marquardt solver called 'lmniel' based on a smoother updating procedure for the damping parameter proposed by Nielsen 1999. This is the algorithm implemented in the popular 'levmar' library. This algorithm is not as robust as the current 'lmsder' algorithm, since it does not use a trust region approach and has a simpler method of rescaling to deal with badly scaled problems. However there are two significant advantages in lmniel: a) The algorithm is much simpler than the lmsder/MINPACK algorithm and will be very easy to maintain going forward. Despite its simplicity, it has proven very effective on a large class of problems. b) The most important reason I wanted to include this is that in each iteration, the method solves the normal equation system: (J^T J + \mu I) dx = -J^T f and so it does a QR decomposition of the p-by-p matrix J^T J instead of the full n-by-p matrix J, which lmsder operates on. This means that for problems with a huge number of residuals (ie: n >> p), the method is far more efficient than lmsder, which can sit there for hours trying to QR decompose the n-by-p Jacobian which could have millions of rows. The drawback of this approach is that the normal equations solution could be significantly error-prone if the Jacobian matrix is near-singular, since forming J^T J would make the matrix much closer to singular. In these cases lmsder would be preferable. In principle, lmsder could be modified to solve the normal equations also, however the lmsder algorithm is rather complex and I haven't taken the time to fully understand it. And of course for smaller systems where efficiency is not a big concern lmsder is more accurate and will converge more quickly in many cases. 2) There is now direct support for weighted nonlinear least squares, via the _wset functions. Previously, the user had to take care of weighting themselves in their f and df evaluation functions. 3) There is a new interface fdfridge for adding ridge regularization to nonlinear least squares problems. 4) There is now an extensive test suite for the nonlinear least squares module. Previously there existed 3 tests and now there are around 40. These tests helped to identify a bug in the scaling procedure of lmsder, and they also demonstrate that lmsder is an extremely robust implementation. There were some questions about this on the mailing list and bug tracker (ie: switching to the ALGLIB or levmar algorithms). Levmar is now implemented as the lmniel solver for big systems, but I can't find any reason to doubt the quality of the lmsder solver; it converges on many of the test suite problems which levmar/lmniel cannot. Patrick