Sigma-delta quantization errors and the traveling salesman problem (Q2476998): Difference between revisions

From MaRDI portal
RedirectionBot (talk | contribs)
Changed an Item
ReferenceBot (talk | contribs)
Changed an Item
 
(2 intermediate revisions by 2 users not shown)
Property / MaRDI profile type
 
Property / MaRDI profile type: MaRDI publication profile / rank
 
Normal rank
Property / full work available at URL
 
Property / full work available at URL: https://doi.org/10.1007/s10444-006-9016-1 / rank
 
Normal rank
Property / OpenAlex ID
 
Property / OpenAlex ID: W2076812785 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q5729634 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Finite normalized tight frames / rank
 
Normal rank
Property / cites work
 
Property / cites work: Sigma-delta (/spl Sigma//spl Delta/) quantization and finite frames / rank
 
Normal rank
Property / cites work
 
Property / cites work: Second-order sigma-delta (\(\Sigma \Delta\)) quantization of finite frame expansions / rank
 
Normal rank
Property / cites work
 
Property / cites work: Equal-norm tight frames with erasures / rank
 
Normal rank
Property / cites work
 
Property / cites work: Approximating a bandlimited function using very coarsely quantized data: a family of stable sigma-delta modulators of arbitrary order / rank
 
Normal rank
Property / cites work
 
Property / cites work: A Class of Nonharmonic Fourier Series / rank
 
Normal rank
Property / cites work
 
Property / cites work: Generation of finite tight frames by Householder transformations / rank
 
Normal rank
Property / cites work
 
Property / cites work: The shortest path and the shortest road through <i>n</i> points / rank
 
Normal rank
Property / cites work
 
Property / cites work: Sums of Squares of Edge Lengths and Spacefilling Curve Heuristics for the Traveling Salesman Problem / rank
 
Normal rank
Property / cites work
 
Property / cites work: Quantizers ad the worst case Euclidean traveling salesman problem / rank
 
Normal rank
Property / cites work
 
Property / cites work: Quantized frame expansions with erasures / rank
 
Normal rank
Property / cites work
 
Property / cites work: Quantized overcomplete expansions in IR/sup N/: analysis, synthesis, and algorithms / rank
 
Normal rank
Property / cites work
 
Property / cites work: Approximating a bandlimited function using very coarsely quantized data: Improved error estimates in sigma-delta modulation / rank
 
Normal rank
Property / cites work
 
Property / cites work: White Noise Hypothesis for Uniform Quantization Errors / rank
 
Normal rank
Property / cites work
 
Property / cites work: Peano curves and smoothness of functions / rank
 
Normal rank
Property / cites work
 
Property / cites work: On the length of optimal TSP circuits in sets of bounded diameter / rank
 
Normal rank
Property / cites work
 
Property / cites work: A problem seminar / rank
 
Normal rank
Property / cites work
 
Property / cites work: A Priori Bounds on the Euclidean Traveling Salesman / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q5691080 / rank
 
Normal rank

Latest revision as of 18:17, 27 June 2024

scientific article
Language Label Description Also known as
English
Sigma-delta quantization errors and the traveling salesman problem
scientific article

    Statements

    Sigma-delta quantization errors and the traveling salesman problem (English)
    0 references
    0 references
    12 March 2008
    0 references
    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.
    0 references
    frame
    0 references
    sigma-delta quantization
    0 references
    traveling salesman problem
    0 references

    Identifiers