Timeline for Randomized algorithm to verify the uniqueness of non-negative solution to a linear system
Current License: CC BY-SA 3.0
14 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 6, 2017 at 18:08 | comment | added | Yauhen Yakimenka | And do you know some link to read about total complementarity problem? (I found only linear one and not sure how they are related). | |
| Jun 6, 2017 at 18:03 | comment | added | Yauhen Yakimenka | Hmm... maybe. Does it give a better/faster algorithm? | |
| Jun 6, 2017 at 16:15 | comment | added | Surb | This looks like a total complementarity problem. | |
| Jun 6, 2017 at 15:54 | history | edited | Yauhen Yakimenka | CC BY-SA 3.0 |
added 169 characters in body
|
| Apr 13, 2017 at 12:58 | history | edited | CommunityBot |
replaced http://mathoverflow.net/ with https://mathoverflow.net/
|
|
| Dec 13, 2016 at 9:07 | comment | added | Yauhen Yakimenka | No, $x^*$ is not a basic feasible solution (in simplex algorithm terminology). Well, to be precise we are not guaranteed that. | |
| Dec 13, 2016 at 7:39 | history | edited | Federico Poloni |
Tag matrix-equations is not for linear equations
|
|
| Dec 12, 2016 at 22:14 | comment | added | Rodrigo de Azevedo | Is $\rm x^*$ a basic feasible solution? If so, one has $m$ choices on which variable to leave the basis and $n-m$ choices on which to enter the basis. In total, $m (n-m)$ choices. One could sample from this set of choices. Each choice would produce a linear system to solve. We only need to find one linear system whose solution is nonnegative. | |
| Dec 12, 2016 at 21:30 | comment | added | Yauhen Yakimenka | Can you elaborate on probability of success and details of this walk? | |
| S Dec 12, 2016 at 19:38 | history | suggested | Henry.L | CC BY-SA 3.0 |
add tags, modify title
|
| Dec 12, 2016 at 19:20 | review | Suggested edits | |||
| S Dec 12, 2016 at 19:38 | |||||
| Dec 12, 2016 at 17:46 | comment | added | Rodrigo de Azevedo | If the system is underdetermined, then the null space of $\rm A$ is nontrivial. Using SVD, we can find a basis for the null space. Adding this null space to $\rm x^*$, we obtain an affine space. Lastly, we can do a random walk on this affine space until we find another nonnegative solution or we quit, whichever comes first. | |
| Dec 12, 2016 at 15:06 | history | edited | Yauhen Yakimenka | CC BY-SA 3.0 |
added 1 character in body
|
| Dec 12, 2016 at 14:59 | history | asked | Yauhen Yakimenka | CC BY-SA 3.0 |