Timeline for Minimizing total variation under constraint
Current License: CC BY-SA 4.0
15 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Aug 22 at 13:55 | history | edited | Daniele Tampieri | CC BY-SA 4.0 |
Minor formatting (norm brackets)
|
| Aug 22 at 11:42 | history | edited | Aryeh Kontorovich | CC BY-SA 4.0 |
added 210 characters in body
|
| Aug 16 at 8:38 | comment | added | Aryeh Kontorovich | Induction -- as well as all other "local" methods seem to fail badly here. I can prove the minimizer claim for $n=2$, but not that it's unique. The minimizer for odd $n$ has all $p_i$s equal and all $q_i$s too but otherwise doesn't have the nice, simple form that even $n$ does. | |
| Aug 15 at 18:25 | comment | added | Thomas Steinke | I'm tempted to try proving this by induction on $n$, but the fact that it only applies to even $n$ seems like a big barrier. Is there a form of the conjecture that holds for all $n$? Can you at least prove it for $n=2$? | |
| Aug 13 at 18:02 | history | edited | Aryeh Kontorovich | CC BY-SA 4.0 |
deleted 43 characters in body
|
| Aug 13 at 17:41 | comment | added | Yury | Let us continue this discussion in chat. | |
| Aug 13 at 17:25 | history | edited | Aryeh Kontorovich | CC BY-SA 4.0 |
deleted 176 characters in body
|
| Aug 13 at 17:25 | comment | added | Aryeh Kontorovich | you're right -- it's not convex! but the claim about the minimum still appears to be true | |
| Aug 13 at 16:56 | comment | added | Yury | My plot shows that it is not a convex function of $x$ even when all $p_i = x + 0.1$ and $q_i = x$, $n = 3$. | |
| Aug 13 at 16:48 | comment | added | Aryeh Kontorovich | Actually now less sure. | |
| Aug 13 at 16:45 | comment | added | Yury | Are you sure that the objective is convex? | |
| Aug 13 at 15:58 | comment | added | Aryeh Kontorovich | Note that this is false for odd n, so where does your argument fail there? | |
| Aug 13 at 15:49 | comment | added | Yury | Once we prove that the objective is convex, the rest follows easily from symmetry. The optimal solution must be invariant under the permutation group (acting on the indices of $p_i$ and $q_i$) and "reflections": $(p, q) \mapsto (1 - q, 1- p)$. The only fixed point is your solution. | |
| Aug 13 at 14:57 | history | edited | Aryeh Kontorovich | CC BY-SA 4.0 |
added 94 characters in body
|
| Aug 13 at 11:29 | history | asked | Aryeh Kontorovich | CC BY-SA 4.0 |