If speed is not a factor, why not do the best thing and calculate the eigenvalue decomposition and then form a moore-penrose inverse. The inversion will never fail (unless all eigenvalues are zero). You will also have an immediate diagnostic of the stability of the system (through the condition or inverse condition number).
On Thu, Sep 8, 2011 at 2:41 AM, Phil Steitz <phil.ste...@gmail.com> wrote: > On 9/7/11 9:26 PM, Greg Sterijevski wrote: > > I thought that QR is of O(n^3) complexity, while LU is probably in the > > vicinity of O(n^2.5). While this is not a barn burning improvement, it is > an > > improvement. Consider that if you are using the covariance of the > parameters > > in deciding how to make the next step (some kind of inverse hessian > rule), > > the repeated calls to inverse add up? > > Sounds a little contrived. I can't see the speed difference as > really material given that we are talking about parameter covariance > matrices. I would be fine with any of the three - LU, Cholesky > (which may also be fastest, btw) or QR. > > Phil > > > > Would it be a terrific eyesore to include a constructor with a boolean > > argument that says bUseQR? The call to LU is localized, so there is > minimal > > refactoring. One could also pass the boolean into the getCovariances > > method. > > > > > > > > > > On Wed, Sep 7, 2011 at 4:48 PM, Ted Dunning <ted.dunn...@gmail.com> > wrote: > > > >> It shouldn't be all that different from QR (at most about 2x different). > >> > >> On Wed, Sep 7, 2011 at 1:16 PM, Greg Sterijevski < > gsterijev...@gmail.com > >>> wrote: > >>> It is also my recollection that LU is very quick to calculate. Would it > >> be > >>> possible to allow users to choose? > >>> > >>> On Wed, Sep 7, 2011 at 3:07 PM, Ted Dunning <ted.dunn...@gmail.com> > >> wrote: > >>>> Does the LUDecomposition not use pivots? LU should always do so since > >> it > >>>> is > >>>> numerically unstable otherwise. I would be surprised if it doesn't > >> given > >>>> the normal level of quality in commons math. > >>>> > >>>> QR is, of course, almost always preferable to LU as you note. But I > >>> would > >>>> be surprised at radically different answers. > >>>> > >>>> Perhaps the only real difference between the two methods in this one > >> case > >>>> is > >>>> a difference in threshold. > >>>> > >>>> What is the condition number of your matrix? > >>>> > >>>> On Wed, Sep 7, 2011 at 6:34 AM, Gilles Sadowski < > >>>> gil...@harfang.homelinux.org> wrote: > >>>> > >>>>> Hi. > >>>>> > >>>>>>>>> In class "AbstractLeastSquaresOptimizer" (in > >>>>> "o.a.c.m.optimization.general"), > >>>>>>>>> the method "getCovariances()" uses "LUDecompositionImpl" to > >>> compute > >>>>> the > >>>>>>>>> inverse of a matrix. > >>>>>>>>> In my application, this leads to a "SingularMatrixException". If > >> I > >>>>> change > >>>>>>>>> "LUDecompositionImpl" to "QRDecompositionImpl", no exception is > >>>>> raised. > >>>>>>>>> Also, keeping "LUDecompositionImpl" but passing a much lower > >>>>> singularity > >>>>>>>>> threshold, does not raise the exception either. > >>>>>>>>> > >>>>>>>>> Thus, I wonder whether there was a reason for using "LU", and if > >>>> not, > >>>>>>>>> whether I could change the decomposition solver to "QR" (as this > >>> is > >>>> a > >>>>>>>>> cleaner solution than guessing a good value for the threshold). > >>>>>>>> There are no reason for LU decomposition, and QR decomposition is > >>>>>>>> known to be more stable. So I would also consider switching to > >> this > >>>>>>>> algorithm is a cleaner solution. > >>>>>>> Fine. I'll open a JIRA issue. > >>>>>>> > >>>>>>> A unit test "testNonInvertible" in > >> "LevenbergMarquardtOptimizerTest" > >>>>> fails > >>>>>>> with the change to "QRDecomposition" because no > >>>>> "SingularMatrixException" > >>>>>>> is raised anymore. > >>>>>>> What was the purpose of that test? > >>>>>> The purpose was to check that impossible problems were detected > >>>> properly. > >>>>> My question should have been clearer: Was the previous behaviour > >>> correct > >>>>> (i.e. an exception *must* be raised somehow)? > >>>>> The switch to "QR" seems to imply that a previously impossible > >> problem > >>> is > >>>>> now quite possible. So, is the problem really impossible or was the > >>> test > >>>>> actually testing a fragile implementation of "getCovariances()"? > >>>>> > >>>>> > >>>>> Regards, > >>>>> Gilles > >>>>> > >>>>> --------------------------------------------------------------------- > >>>>> To unsubscribe, e-mail: dev-unsubscr...@commons.apache.org > >>>>> For additional commands, e-mail: dev-h...@commons.apache.org > >>>>> > >>>>> > > > --------------------------------------------------------------------- > To unsubscribe, e-mail: dev-unsubscr...@commons.apache.org > For additional commands, e-mail: dev-h...@commons.apache.org > >
