Near-Optimal Encoding for Sigma-Delta Quantization of Finite Frame Expansions

作者：Iwen Mark^*; Saab Rayan

来源：Journal of Fourier Analysis and Applications, 2013, 19(6): 1255-1273.

DOI：10.1007/s00041-013-9295-0

• Vector quantization
• Frame theory
• Rate-distortion theory
• Random matrices
• Overdetermined systems
• Pseudoinverses

In this paper we investigate encoding the bit-stream resulting from coarse Sigma-Delta quantization of finite frame expansions (i.e., overdetermined representations) of vectors. We show that for a wide range of finite-frames, including random frames and piecewise smooth frames, there exists a simple encoding algorithm-acting only on the Sigma-Delta bit stream-and an associated decoding algorithm that together yield an approximation error which decays exponentially in the number of bits used. The encoding strategy consists of applying a discrete random operator to the Sigma-Delta bit stream and assigning a binary codeword to the result. The reconstruction procedure is essentially linear and equivalent to solving a least squares minimization problem.

• 出版日期2013-12