3 ms·

One quick comment: in general it is a bad idea to compute the inverse of a matrix (to solve a linear system). It's much better to compute the QR factorization o

by schmit 10y ago

One quick comment: in general it is a bad idea to compute the inverse of a matrix (to solve a linear system). It's much better to compute the QR factorization or SVD instead (or simply call least square solver). See for example: https://www.johndcook.com/blog/2010/01/19/dont-invert-that-matrix/ https://www.johndcook.com/blog/2010/01/19/dont-invert-that-m...

eriklindernoren 10y ago
Thank you for the feedback. :) I plan on fixing this soon!
- JustFinishedBSG 10y ago
  Not very important and for a learning project I find using cvxpy a better idea as it's more readable ( like you did ) but: Solving the full quadratic optimization problem for SVMs in basically impossible to do. You are forming an n^2 matrix, so I'm going to let you imagine what happens when n = 100 000. Using people use either approximation methods ( Incomplete Cholesky, Nystrom ) or do it exactly but iteratively ( SMO, Pegasos... ) I'm implementing them for class right now so it's still fresh in my head haha
JustFinishedBSG 10y ago
It's usually even better to use iterative methods
- thearn4 10y ago
  GMRES is definitely my go-to these days. Though it is worth noting that direct methods do have a benefit of letting you quickly solve many successive linear problems involving the same matrix, but different right-hand sides. But iterative methods scale very well for large sparse problems that they are very often the only tool to consider. Block Krylov methods are a thing , but I haven't experimented with them yet.
  - JustFinishedBSG 10y ago
    For solving linear systems there are recent mind-blowing methods by R. M. Gower and P. Richtarik: https://arxiv.org/abs/1506.03296 https://arxiv.org/abs/1506.03296 http://www.maths.ed.ac.uk/~richtarik/papers/SDA.pdf http://www.maths.ed.ac.uk/~richtarik/papers/SDA.pdf Plus R. M. Gower is fantastically nice and enthusiastic so there's that And thanks for the link !
    - zzleeper 10y ago
      Has anyone implemented them in production? I read their paper a while ago, but thought that the dual methods they showed might have practical limitations (like insane cache misses, compared to more standard methods)
    - stabbles 10y ago
      Only scrolled through it, but AFAIK if its results are comparable to Kaczmarz, then note that it is extremely slow. If your goal is to solve say a LS problem, why not go for CGLS? http://web.stanford.edu/group/SOL/software/cgls/ http://web.stanford.edu/group/SOL/software/cgls/
  - stabbles 10y ago
    These problems you sketch can already be overcome by using the approximate eigenspectrum info of the matrix obtained as a by-product of Krylov methods. This has been invented many times, and is used in 'thick restart', 'augmented Krylov subspace methods', 'deflation'. In particular this was developed for scattering problems with many electromagnetic incident waves hitting an object, changing only the rhs. Also, you can also use an approximate LU-decomp as a preconditioner for Krylov methods. Similarly, Tykhonov regularization (solving for a range of slightly perturbed matrices "A + labda I" where labda is a parameter) are easily tackled using Krylov subspace methods by noting that the Krylov subspace is invariant under shifts like these. So only once an orthonormal basis must be found for the Krylov subspace, which can then be used for every lamda of interest.
- stabbles 10y ago
  Depends on the number of unknowns, sparsity of the matrix, whether you want 3 correct digits or 16, etc. Direct methods as Gaussian elimination with pivoting are proven to be stable. Iterative methods are not but can be a lot cheaper in computational costs. Also they can stop when a certain relative residual is reached, unlike direct methods. If iterative methods like Krylov subspace methods where stable, then they could actually be seen as direct methods themselves, as the Krylov subspace has at most a dimension of N, where N is the number of unknowns; so after at most N iterations the solution could be extracted exactly from the search space. In practice this is not the case due to rounding errors.

by schmit 10y ago

eriklindernoren 10y ago

Thank you for the feedback. :) I plan on fixing this soon!

JustFinishedBSG 10y ago
Not very important and for a learning project I find using cvxpy a better idea as it's more readable ( like you did ) but: Solving the full quadratic optimization problem for SVMs in basically impossible to do. You are forming an n^2 matrix, so I'm going to let you imagine what happens when n = 100 000. Using people use either approximation methods ( Incomplete Cholesky, Nystrom ) or do it exactly but iteratively ( SMO, Pegasos... ) I'm implementing them for class right now so it's still fresh in my head haha

JustFinishedBSG 10y ago

It's usually even better to use iterative methods

thearn4 10y ago
GMRES is definitely my go-to these days. Though it is worth noting that direct methods do have a benefit of letting you quickly solve many successive linear problems involving the same matrix, but different right-hand sides. But iterative methods scale very well for large sparse problems that they are very often the only tool to consider. Block Krylov methods are a thing , but I haven't experimented with them yet.
- JustFinishedBSG 10y ago
  For solving linear systems there are recent mind-blowing methods by R. M. Gower and P. Richtarik: https://arxiv.org/abs/1506.03296 https://arxiv.org/abs/1506.03296 http://www.maths.ed.ac.uk/~richtarik/papers/SDA.pdf http://www.maths.ed.ac.uk/~richtarik/papers/SDA.pdf Plus R. M. Gower is fantastically nice and enthusiastic so there's that And thanks for the link !
  - zzleeper 10y ago
    Has anyone implemented them in production? I read their paper a while ago, but thought that the dual methods they showed might have practical limitations (like insane cache misses, compared to more standard methods)
  - stabbles 10y ago
    Only scrolled through it, but AFAIK if its results are comparable to Kaczmarz, then note that it is extremely slow. If your goal is to solve say a LS problem, why not go for CGLS? http://web.stanford.edu/group/SOL/software/cgls/ http://web.stanford.edu/group/SOL/software/cgls/
- stabbles 10y ago
  These problems you sketch can already be overcome by using the approximate eigenspectrum info of the matrix obtained as a by-product of Krylov methods. This has been invented many times, and is used in 'thick restart', 'augmented Krylov subspace methods', 'deflation'. In particular this was developed for scattering problems with many electromagnetic incident waves hitting an object, changing only the rhs. Also, you can also use an approximate LU-decomp as a preconditioner for Krylov methods. Similarly, Tykhonov regularization (solving for a range of slightly perturbed matrices "A + labda I" where labda is a parameter) are easily tackled using Krylov subspace methods by noting that the Krylov subspace is invariant under shifts like these. So only once an orthonormal basis must be found for the Krylov subspace, which can then be used for every lamda of interest.
stabbles 10y ago
Depends on the number of unknowns, sparsity of the matrix, whether you want 3 correct digits or 16, etc. Direct methods as Gaussian elimination with pivoting are proven to be stable. Iterative methods are not but can be a lot cheaper in computational costs. Also they can stop when a certain relative residual is reached, unlike direct methods. If iterative methods like Krylov subspace methods where stable, then they could actually be seen as direct methods themselves, as the Krylov subspace has at most a dimension of N, where N is the number of unknowns; so after at most N iterations the solution could be extracted exactly from the search space. In practice this is not the case due to rounding errors.