1
$\begingroup$

I have proposed an optimisation algorithm which I claim has improved upon the previous algorithm in a number of ways.

One of these claims is that my proposed solution requires no explicit SVD and psuedoinverse calculation which I claim is good, since in my case perturbations are important, and I believe these routines are traditionally unstable to perturbations.

My question is given the implementations in modern linear algebra computational libraries (such as LAPACK v3.0), how strong is this claim?

To summarise:

My method per iteration:

  • Only one solution of a generalized eigenvalue problem

Old method per iteration:

  • One solution of a generalized eigenvalue problem, AND,
  • One explicit SVD calculation for a Jacobian, $J = USV^{\intercal}$
  • Two explicit calculations of a pseudoinverse based on the Jacobian, $J$. That is, (1) $J^{\dagger}$ and (2) $V^{\dagger}$

Given that my algorithm will have input perturbations, and considering the stability of modern linear algebra routines, is my claim a strong selling point?

|cite|improve this question
$\endgroup$
  • 1
    $\begingroup$ For the same problem, how are the sizes of the generalized eigenvalue problem compared? Can you deduce anything about the condition number of those problems, respectively? $\endgroup$ – Anton Menshov♦ May 14 '19 at 14:46
  • $\begingroup$ So based on the information given alone it is it not conclusive whether one algorithm is better than the other? To ans your Qs: The gen. eig value problems are the same size in both algorithms. I cannot say anything with confidence about the condition numbers (I believe) as well. But if both systems are the same, they would have the same condition number anyway, I think? The only real difference is the additional steps in the "old method", which has the additinal SVD and pseudoinverse on a rectangular mxn Jacobean (n>m) $\endgroup$ – pche8701 May 14 '19 at 15:32
  • $\begingroup$ I kind of did not expect for them to be of the same size; otherwise, I am quite curious where the savings in the additional steps come from (which is not too relevant to this particular question). Usually, you do trade-offs, here I just see from the bird's view one algorithm (without any details) to be simply better. $\endgroup$ – Anton Menshov♦ May 14 '19 at 15:38
  • $\begingroup$ Sure. So even if modern LAPACK methods are optimized and very stable, would you say my innovation is a selling point? (Breifly, in the original algorithm the author inverts a jacobean due to a Newton step, but I stick just to gradient descent which does not require said inversion-admittedly the original paper was published in the 90s, but has not been innovated upon since). I criticize the original method for the unnecessary steps (modern grad descent works) and delve into some discussion on stability with the SVD etc... Im just wondering if this is still an issue for modern Lin. Alg. Solvers. $\endgroup$ – pche8701 May 14 '19 at 16:22
  • $\begingroup$ I give a simple example to demonstrate the SVD instability in my work, BUT i thought to myself in hindsight if this discussion is even warrented or valid, since modern linear algebra toolboxes are highly optimised and very stable. Please let me know what you think. $\endgroup$ – pche8701 May 14 '19 at 16:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.