Frame permutation quantization (Q544043)

The authors introduce a technique for vector quantization in redundant linear representations of finite-dimensional real Hilbert spaces. This technique is based on applying permutation source coding to the frame coefficients of each vector. The permutation source coding is presented in two variants: The first one encodes partial information about the ordering of frame coefficients, the second one specifies the sign of frame coefficients and information about the ordering of their magnitudes. The recovered vectors are obtained either by applying a permutation, possibly combined with sign changes, to a fixed sequence of frame coefficients in order to make it consistent with the ordering information, or by recursively projecting a random vector onto the convex sets specified by the encoded inequalities between frame coefficients. This step is followed by the usual linear reconstruction with a dual frame. The performance measure used here is the mean-squared error for uniformly distributed input vectors in a cube or for a Gaussian distribution. One of the main results is that consistent reconstruction (each recovered vector is invariant under repeated encoding and recovery) and reconstruction with the canonical dual frame can only be achieved by a frame having \(k+1\) vectors in a \(k\)-dimensional Hilbert space. This means that it is necessary to investigate alternate duals in order to gain flexibility. Another main result concerns the accuracy of the the iterated projections onto convex sets for a family of frames consisting of random unit-norm vectors. For a fixed input vector, as the size \(k\) of the family grows the squared reconstruction error norm decays faster than \(k^{-p}\) for any \(0<p<2\). An additional insight is of experimental nature. High-precision Monte-Carlo simulation shows evidence that frame permutation quantization is better than entropy-constrained scalar quantization for certain dimensions and prescribed bit rates. These experiments also indicate that the recursive reconstruction algorithm achieves a decay of the mean-squared error of order \(k^{-4}\), with \(k\) the number of frame vectors. Overall, this work presents an alternative to the literature on sigma-delta quantization for frame coefficients, which opens up a new avenue in the discussion of analog-digital conversion.