Timeline for How to find a good preconditioner to the system $(A^T A + \lambda I) x = A^T b$?
Current License: CC BY-SA 4.0
22 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Feb 15, 2020 at 8:54 | answer | added | Abdullah Ali Sivas | timeline score: 2 | |
| Oct 26, 2018 at 16:52 | comment | added | Richard Zhang | @Integral As someone who works in this field, I would say this is basically an open research question. With a good preconditioner for the trust-region subproblem of an outer tensor decomposition, you will give all the SGD people a run for their money. Good luck! | |
| Oct 25, 2018 at 21:01 | history | tweeted | twitter.com/StackSciComp/status/1055564907050090496 | ||
| Oct 25, 2018 at 17:06 | history | edited | Integral | CC BY-SA 4.0 |
deleted 27 characters in body
|
| Oct 25, 2018 at 16:57 | history | edited | Integral | CC BY-SA 4.0 |
edited body
|
| Oct 25, 2018 at 16:51 | comment | added | Integral | @ChristianClason Thank you for clarifying. I'll give a read at MINRES right now. But I suppose I still need a preconditioner anyway, since the LSMR implementation is using the max number of iterations all the time. | |
| Oct 25, 2018 at 16:50 | comment | added | Integral | @GoHokies I just update the question with more information about the structure of the matrix. Thank you for your suggestions. | |
| Oct 25, 2018 at 16:48 | history | edited | Integral | CC BY-SA 4.0 |
added 2176 characters in body
|
| Oct 25, 2018 at 16:35 | comment | added | Christian Clason | @Rzu Note that Integral mentioned they were using LSMR, not CG for the normal equation, which avoids the numerical issues with the squared condition number. (@Integral: LSMR is equivalent to MINRES applied to the normal equations, not CG -- that's a different method.) | |
| Oct 25, 2018 at 16:30 | comment | added | GoHokies | also, it would be good to include more information about the origin and (block-)structure of $A$. good preconditioners are often built from such domain knowledge. | |
| Oct 25, 2018 at 16:25 | comment | added | GoHokies | have you tried the "usual suspects", i.e. diagonal preconditioning or incomplete Cholesky? other, less known preconditioning strategies for sparse LS are evaluated in this recent ACM TOMS paper by Gould. | |
| Oct 25, 2018 at 16:06 | comment | added | Integral | @AntonMenshov This minimization problem indeed comes from a regularization, the Tikhonov regularization. It is part of a bigger problem which needs to solve $\min \|Ax - b\|$ at each step, and at each step the factor $\lambda$ is updated in order to accelerate the overall convergence. | |
| Oct 25, 2018 at 15:59 | comment | added | Anton Menshov♦ | This looks like a problem coming from regularization (say, Tikhonov with identity regularization operator). Cause if you are able to play with $\lambda$, it essentially leads to L-curve methods. (this comment has not a lot to do with preconditioners themselves). | |
| Oct 25, 2018 at 15:52 | comment | added | R zu | What does the sparsity pattern look like? I was reading Wolfgang Bangerth's answer at scicomp.stackexchange.com/questions/20402/… He says the diagonal pre-conditioner is only good for simple problems ... | |
| Oct 25, 2018 at 15:41 | comment | added | Integral | You can't avoid preconditioning at all these days. It is the most important part of you algorithm, supposing you are dealing with a real difficult problem. This is my case. | |
| Oct 25, 2018 at 15:39 | comment | added | Integral | Your comment is valid since I didn't mention the size of my matrix and I wrote the original problem as being $Ax = b$ where it should be $\min \|Ax - b\|$. Stil, I would prefer to have a good preconditioner instead of losing the SPD property, the damping factor and the CG method. | |
| Oct 25, 2018 at 15:33 | history | edited | Integral | CC BY-SA 4.0 |
added 10 characters in body
|
| Oct 25, 2018 at 15:32 | comment | added | Integral | @R zu if the matrix is huge and sparse, using iterative methods is mandatory. One of the best ones is the conjugate gradient. Squaring the condition number means nothing if you have a good preconditioner to compensate it. | |
| Oct 25, 2018 at 15:10 | comment | added | R zu | Normal equation squares the condition number. Other methods are better if the matrix is ill-condition. (see: eigen.tuxfamily.org/dox/group__LeastSquares.html) I haven't studied how to combine preconditioning with the other methods though. | |
| Oct 25, 2018 at 15:08 | history | edited | Integral | CC BY-SA 4.0 |
added 16 characters in body
|
| Oct 25, 2018 at 14:55 | review | First posts | |||
| Oct 25, 2018 at 16:00 | |||||
| Oct 25, 2018 at 14:54 | history | asked | Integral | CC BY-SA 4.0 |