Is the MMA algorithm a faithful implementation of Conway and Sloane's algorithm? The MMA algorithm is O(n log n) due to Ordering[], but there's a well-known linear-time algorithm; certainly Conway and Sloane's algorithm is linear-time? -tom On Tue, Feb 2, 2016 at 4:00 PM, Veit Elser <ve10@cornell.edu> wrote:
On Feb 2, 2016, at 6:22 PM, Dan Asimov <asimov@msri.org> wrote:
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
I wonder what you were watching last night ...
The squared distance measure is standard when quantizing signals:
J.H. Conway and N.J.A. Sloane, Fast quantizing and decoding algorithms for lattice quantizers and codes, IEEE Trans. Inf. Theory 28, 227-232 (1982).
The lattice for your problem is called A_(n-1). The quantization algorithm for this lattice is given in the Conway-Sloane paper. Here’s a Mma implementation:
proj[x_, c_] := Module[{y, z, d, p, ip, zp}, y = c x/Total[x]; z = Round[y]; d = Total[z] - c; If[d == 0, Return[z]];
p = Ordering[y - z]; ip = InversePermutation[p]; zp = z[[p]]; If[d > 0, Join[Take[zp, d] - 1, Drop[zp, d]][[ip]], Join[Drop[zp, d], Take[zp, d] + 1][[ip]]] ]
x = {Pi, E, GoldenRatio};
proj[x, 100] {42, 36, 22}
-Veit _______________________________________________ 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] --