Sigma-delta quantization errors and the traveling salesman problem (Q2476998)

This work concerns errors for reconstruction from sigma-delta quantized frame expansions. Starting with a normalized tight frame \(\mathcal{F}=\{{\mathbf{w}}_1,\dots,{\mathbf{w}}_N\}\) for \(\mathbb{R}^d\) (that is, the matrix \(F\) with columns \({\mathbf{w}}_j\) satisfies \(F F^{T}=\lambda I_d\) for some fixed \(\lambda>0\)), the \textit{standard} quantized frame expansion of \({\mathbf{x}}\in \mathbb{R}^d\) is \(\widehat{\mathbf{x}}={1\over \lambda }\sum_{j=1}^N Q_\Delta ({\mathbf{x}}\cdot {\mathbf{w}}_j){\mathbf{w}}_j\) where \(Q_\Delta (t)\in \Delta {\mathbb{Z}}\) rounds \(t\) to the closest multiple of \(\Delta\). The \textit{sigma-delta} method instead reconstructs an estimate \(\tilde{{\mathbf{x}}}=\sum q_k {\mathbf{v}}_k\) where \(\{{\mathbf{v}}_1,\dots,{\mathbf{v}}_N\}\) is, in general, the canonical dual frame of \(\mathcal{F}\) and \(q_k=Q_\Delta(S_k)-Q_\Delta(S_{k-1})\) with \(S_k=\sum_{j=1}^k {\mathbf{x}}\cdot {\mathbf{w}}_j\). In contrast to the case of orthonormal basis expansions, the sigma-delta frame approximations will depend on the particular ordering of the frame elements. Wang investigates the dependence of the approximation errors on the frame order based on the notion of {\textit{frame variation}}, \[ \sigma_r(\mathcal{S},p) =\sum_{j=1}^{N-1} \| {\mathbf{w}}_{p(j)}-{\mathbf{w}}_{p(j+1)}\| ^r +\| {\mathbf{w}}_{p(N)}\| ^r \] where \(p\in {\mathbf{S}}_N\) (the permutations of \(\{1,\dots,N\}\)). Among the main results Wang shows that if \(\mathcal{F}=\{{\mathbf{w}}_1,\dots,{\mathbf{w}}_N\}\) is a normalized tight frame for \(\mathbb{R}^d\) where \(d\geq 2\) then there is a constant \(C\) depending only on \(d\) such that for each \({\mathbf{x}}\in \mathbb{R}^d\) there is a \(p\in {\mathbf{S}}_N\) such that \[ \| {\mathbf{x}}-\widetilde{{\mathbf{x}}}_p \| \leq \Delta N^{-1/d}. \] Here, \(\widetilde{{\mathbf{x}}}_p\) is the quantized frame approximation in which the frame elements are ordered according to the permutation \(p\). The traveling salesman problem provides the heuristic for this estimate. Importantly, Wang also considers the problem of how to find a good permutation for a given \({\mathbf{x}}\) (analogous to finding a good route for the salesman). In this vein Wang provides a constructive proof of the estimates \[ \sigma_1(\mathcal{S},p)\leq 2\sqrt{d+3} ( N^{1-{1\over d}} -1);\qquad \sigma_2\leq (\mathcal{S},p)\leq 4(d+3) ( N^{1-{2\over d}} -1). \] Here \(\mathcal{S}\) is any \(N\)-element subset of \([-1/2,1/2]^d\) -- not necessarily a frame. Some separate estimates for expected errors for sigma-delta approximations using (complex valued) harmonic frames are also provided.