In answer to (1), defining "good" as "fast", the appropriate algorithm is "round, determine total error (say, +e), "e" values to round the other way selecting those with the least individual error". This is a linear-time algorithm. Did you have another idea for what "good" might mean here? In this case minimizing sum of absolute error and minimizing sum of squared error is the same. On Tue, Feb 2, 2016 at 3:22 PM, Dan Asimov <asimov@msri.org> wrote:
Suppose we have a finite sum of nonnegative numbers that equals 1:
(*) x_1 + ... + x_n = 1
.
Because TV viewers are so easily confused by several digits beyond the decimal point, we want to convert (*) to a sum of integer percentages P_j in the most felicitous, or the least infelicitous, way:
P_1 + ... + P_n = 100%
For example let n = 3. Then we want to map the points on the triangle
{(x,y,z) in (R_0)^3 | x + y + z = 1}
to the discrete set of 5151 points
{(M,N,P) in (Z_0)^3 | M + N + P = 100}
(where R_0 and Z_0 denote the nonnegative reals and integers, respectively).
One obvious thing to try is to minimize the sum of squared error:
So let
(**) E(M,N,P) = (x-M)^2 + (y-N)^2 + (z-P)^2
and pick (M,N,P) such that E(M,N,P) is minimized.
For the sake of this question, let's ignore the measure 0 of cases where the (M,N,P) minimizing (**) is not unique.
Questions: ----------
1. Let n > 0 be arbitrary. Is there a good algorithm for applying (**) in practice, to get the quantization (x_1,...,x_n) |—> (P_1,...,P_n) ???
2. Is there a better or more useful measure of error than sum of squared differences? If so, why is it better?
—Dan _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- -- http://cube20.org/ -- [ <http://golly.sf.net/>Golly link suppressed; ask me why] --