Timeline for Efficient methods to solve large dense singular least square problem (linear system)
Current License: CC BY-SA 3.0
14 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Dec 17, 2016 at 9:15 | comment | added | Federico Poloni | Also, keep in mind that your original problem has no unique solution, in general. Are you fine with any $x$ that solves the problem? | |
| Dec 17, 2016 at 9:12 | comment | added | Federico Poloni | How is the original problem not convex? Maybe you mean "not strictly convex"? | |
| Dec 16, 2016 at 18:09 | answer | added | Michael Saunders | timeline score: 3 | |
| May 27, 2016 at 20:44 | history | edited | Christian Clason |
edited tags
|
|
| Mar 6, 2016 at 5:51 | answer | added | user1337732 | timeline score: 4 | |
| Mar 3, 2016 at 1:22 | comment | added | Brian Borchers | You won't in general be able to solve the constrained linear system of equations that you've asked about. You should start over and ask about how to solve the least squares problem with nonnegativity constraints- there are lots of approaches to that problem, but they don't use $A^{T}Ax=A^{T}b$. | |
| Mar 2, 2016 at 22:36 | comment | added | Kirill | I'm suspicious of your last comment: you introduce a linear change of variables, which cannot possibly turn a non-convex problem into a convex problem (linear map applied to a convex set gives a convex set, etc.). I think I see the issue: you assume that a solution for $z$ exists, i.e., the original problem attains minimum $0$ and it's feasible. If that's the case, you should just do as explained in the wikipedia article and take svd of $A$, not $A^\top A$, you'll get a linear problem without having to compute $m\times m$ svd. If not, then the second problem is not equivalent. | |
| Mar 2, 2016 at 22:02 | comment | added | JW Xing | The reason why I want to reformulate the original optimization to the latter one is because the latter is a convex optimization but the original is not. | |
| Mar 2, 2016 at 22:00 | comment | added | JW Xing | Thanks for your comments. Yes, it is not a linear system. It is a least square problem with constraints. I use the linear system to explain how I came up the idea of using SVD to convert the original optimization problem to the reformulated one. . | |
| Mar 2, 2016 at 21:41 | history | edited | JW Xing | CC BY-SA 3.0 |
added 1 character in body
|
| Mar 2, 2016 at 21:05 | comment | added | Kirill | I don't think this should be called a singular linear system. The top-most problem is a quadratic linear-constrained program, but if $Ax=b$ actually has a solution with $x\geq0$, then it's really just a linear program. I don't think you need to do svd on $A^\top A$, have a look at en.wikipedia.org/wiki/Moore%E2%80%93Penrose_pseudoinverse as described there for the under-determined, full row rank, case (the system with $A^\top A$ comes from the over-determined case). In your problem the solution isn't even necessarily unique. | |
| Mar 2, 2016 at 20:37 | history | edited | JW Xing | CC BY-SA 3.0 |
added 76 characters in body
|
| Mar 2, 2016 at 19:24 | history | edited | JW Xing | CC BY-SA 3.0 |
added 315 characters in body
|
| Mar 2, 2016 at 18:16 | history | asked | JW Xing | CC BY-SA 3.0 |