Timeline for Efficient algorithm for solving a convex quadratic program
Current License: CC BY-SA 3.0
9 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 17, 2018 at 14:30 | comment | added | Federico Poloni | @RodrigodeAzevedo Good point --- the $\sigma_i$ are defined up to $m$ only; the rest can be taken to be zeros. The $c_i$ go up to $n$, though, and in particular there is no minimum if $c_i \neq 0$ for some $i>m$ (or whenever $\sigma_i=0$). This is more or less equivalent to what user35593 said in a comment above: $b$ must be in the range of $A$ for the minimum to exist finite. | |
| Apr 17, 2018 at 13:27 | comment | added | Rodrigo de Azevedo | Since you square $S$, I assume you're using the economy SVD. However, shouldn't the quadratic terms be summed till $i=m$ only? After all, $A$ is tall. | |
| Apr 16, 2018 at 17:06 | comment | added | Federico Poloni | @O.Richard No, it's not optimal, but almost, in practice. It can't be less than $O(mn)$ anyway, because that's the time you need to read the matrix $A$. I think that using for the SVD the various nontrivial (and very impractical) algorithms for fast matrix multiplication you can lower it to $O(nm^{1.37})$, and it's an open problem whether it can go down to $O(nm^{1+\varepsilon})$. But on a real-world problem, I doubt they will give any improvement. | |
| Apr 16, 2018 at 17:01 | comment | added | O. Richard | Is such complexity optimal in any sense? | |
| Apr 16, 2018 at 16:58 | vote | accept | O. Richard | ||
| Apr 16, 2018 at 16:39 | history | edited | Federico Poloni | CC BY-SA 3.0 |
added 72 characters in body
|
| Apr 16, 2018 at 16:34 | history | edited | Federico Poloni | CC BY-SA 3.0 |
added 72 characters in body
|
| Apr 16, 2018 at 16:33 | comment | added | O. Richard | Thank you very much for your answer! What is the complexity of computing SVD in this case? | |
| Apr 16, 2018 at 16:30 | history | answered | Federico Poloni | CC BY-SA 3.0 |