bugGNU Octave - Bugs: bug #33347, lsqnonneg should have tolerance...

 
 

bug #33347: lsqnonneg should have tolerance option for convergence

Submitter:  None
Submitted:  Thu 19 May 2011 05:30:19 AM UTC
   
 
Category:  Libraries Severity:  3 - Normal
Priority:  5 - Normal Item Group:  Performance
Status:  Fixed Assigned to:  None
Originator Name:  Sean Pieper Originator Email:  -email is unavailable-
Open/Closed:  * Closed Release:  * 3.4.0
Operating System:  * GNU/Linux Fixed Release:  None
Planned Release:  None
* Mandatory Fields

Add a New Comment Rich Markup
   

Thu 21 Jun 2012 03:27:28 PM UTC, comment #3: 

Thanks for the patch Axel.  I have applied it here (http://hg.savannah.gnu.org/hgweb/octave/rev/acb09716fc94).  Marking this report as fixed and closing it.  The original reporter can access the fix by building from Mercurial sources or waiting until the next stable release of Octave (3.8.0).

Rik <rik5>
Group administrator
Thu 21 Jun 2012 10:36:27 AM UTC, comment #2: 

Here is a little patch implementing this option.
Now the default tolerance value is the same as in MATLAB:

10*eps*norm (c, 1)*length (c)



(file #26075)

Axel Mathéi <amathei>
Mon 27 Feb 2012 05:46:26 PM UTC, comment #1: 

This is a good idea and probably easy to implement.  The Matlab equivalent function (http://www.mathworks.com/help/techdoc/ref/lsqnonneg.html) implements a TolX option which would probably be the correct approach.

Could the reporter attempt a solution?  Try looking at fzero.m for an easy way of setting the tolerance to the default or having it overriden by a supplied value.

Rik <rik5>
Group administrator
Thu 19 May 2011 05:30:19 AM UTC, original submission:  

running lsqnonneg using a matrix with a large range of exact solutions, I see that it takes about 20s to solve for points that should have 0 error and much less for points that have some error-- apparently the full 10000 iterations are used trying to get to exactly 0 distance (end result is ~10^26 distance). The worst case performance can be considerably reduced if we modify the code around here:



   144     ## compute the gradient.
   145     w = c'*(d - c*x);
   146     w(p) = [];
   147     if (! any (w > 0))
   148       if (useqr)
   149         ## verify the solution achieved using qr updating.


so that line 147 reads



   147     if (! any (w > 0.001))


Obviously, the right value for the tolerance isn't always going to be 0.001, but it should be easy enough to add a tolerance parameter to the option set, and possibly to additionally have some sort of auto tolerance calculation based on the max values of points, some static value of epsilon, etc.


Anonymous

 

(Note: upload size limit is set to 16384 kB, after insertion of the required escape characters.)

Attach Files:
   
   
Comment:
   

Attached Files
file #26075:  lsqnonneg.patch added by amathei (2KiB - text/x-patch)

 

Depends on the following items: None found

Items that depend on this one: None found

 

Carbon-Copy List
  • -email is unavailable- added by rik5 (Posted a comment)
  • -email is unavailable- added by None (Submitted the item)
  •  

    There are 0 votes so far. Votes easily highlight which items people would like to see resolved in priority, independently of the priority of the item set by tracker managers.

    Only group members can vote.

     

    Follow 4 latest changes.

    Date Changed by Updated Field Previous Value => Replaced by
    2012-06-21 rik5 StatusConfirmed Fixed
        Open/ClosedOpen Closed
    2012-06-21 amathei Attached File- Added lsqnonneg.patch, #26075
    2012-02-27 rik5 StatusNone Confirmed

    Back to the top

    Powered by Savane 3.13-caa5.
    Corresponding source code