An Asymptotic Analysis Of Two-stage Vector Quantization
D.H. Lee, David L. Neuhoff · 2005
Two-stage vector quantization is a structured quantization technique having much less complexity and somewhat larger distortion than conventional unstructured single-stage vector quantization. In this paper, we present an asymptotic analysis that quantifies how much larger is its distortion than single-stage VQ, when the first and second stage codebooks are large. summarv Two-stage vector quantization [l] (abbreviated 2VQ applies a kdimensional fiist-stage quantizer to a source vector X = (XI, ...&). producing Ql(X), and then applies a kdimensional second stage quantizer to the error U = X - Ql(x), producing &(U). The final quantized output is Y = Qi(W + Q(W. The encoded rate is the sum of those of the two stages, i.e. RI+ R2 = (loglNl)/k + (log2 N2)k where N1 and N2 denote, respectively, the number of code points in the first and second sta The mean squared error (MSE) resulting from 2VQ is D = IIX-YII2 = EHIUQ(U)II2, where Ilx-yll denotes Euclidean distance. Using a generalized form of Bennett's integral [2] and an asymptotic formula for the probability density of the error from a vector quantizer [3], an approximate formula for the MSE of 2VQ was given in [4]. However, it did not clearly show the effect of the size, NI, of the first-stage quantizer, nor did it show how much larger is the distortion of 2VQ than that attainable with single-stage VQ. To remedy this, we consider two-stage quantization in which the first stage Q1 is characterized by a point density hl(x). a shape profile gl(x,r), an inertial profile ml(x) (derivable from gl) and a size N1 . The second stage is a scaled version of a quantizer Qt . (The point density hl(x) is a function that approximately equals the reciprocal of N1 times the volume of the quantizing cells in the vicinity of x; for fixed x, the shape profile gl(x,r) is a function that partially characterizes the shape of the cells in the vicinity of x; and the inertial profile ml(x) is the normalized moment of inertia of the cells in the vicinity of x.) Specifically, Q2(u) = 6 Qt(uX>, where Qt is a template quantizer with size N2, point density ht(x) and inertial profile mt(x). and where 1 gr