Timeline for Rounding to minimise the sum of errors in pairwise distances
Current License: CC BY-SA 3.0
6 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Aug 29, 2012 at 18:25 | comment | added | vzn | oops! you answered before I had a chance to delete that comment after realizing that.. anyway it still seems to reduce to some almost linear matrix optimization problem? also with a term $V * V^T$ where $V$ is a column vector...? | |
| Aug 29, 2012 at 18:02 | comment | added | Marzio De Biasi | @vzn: if you use the $((y'_i - y'_j) - (x'_i - x'_j))^2$ error to eliminate the absolute value function, then you get terms like $- 2*D_i * D_j * v_i * v_j$; how do you handle them in the minimization? | |
| Aug 29, 2012 at 17:51 | comment | added | vzn | ok nevertheless new idea. consider $e'(i,j)$ again. expand the summation. it will reduce to many terms with $v_i$ and also $v_i^2$. but the latter is equal to $v_i$! therefore it reduces to a problem in the form of minimizing $X*D$ where $X$ is a 0/1 row vector and $D$ is a constant column vector. true? then that is trivial, and just select the $X$ such that it is 1 if the corresponding element in $D$ is negative and 0 if it is positive.... QED? | |
| Aug 29, 2012 at 16:16 | comment | added | Marzio De Biasi | @vzn: I think this is a counterexample. If we round $(0, 1.4, 8.7)$ using rounding $x_i$ criteria we get $(0, 1, 9)$ that has an error of $1.4$, but $(0,2,9)$ has an error of $1.2$ (the result is the same if we eliminate the rationals multiplying by the LCM). | |
| Aug 29, 2012 at 15:38 | comment | added | vzn | expanding your last summation using the $e'(i,j)$ error fn idea above, could it be shown the optimum is actually just the choice where each binary variable floor/ceil is closer to $x_n$? so that leaves only the case of how to round for $x_n$ in the form $m_n + {1 \over 2}$ where $m$ is an integer. | |
| Aug 29, 2012 at 13:31 | history | answered | Marzio De Biasi | CC BY-SA 3.0 |