The memory and computational costs of an exhaustive search vector quantizer (ESVQ) increase exponentially with the product of vector dimension and rate. This exponential increase in costs limits practical VQ code book and vector sizes; and hence, also limits VQ performance below that achievable with large vectors or limits that maximum rate at which VQ can operate. Juang and Gray proposed a multistage vector quantizer, which we call a residual quantizer (RQ), that reduces both the memory and computational costs of VQ. We determine conditions necessary for the optimality of scalar and vector RQs. The condition necessary for optimal encoding requires in general an exhaustive search of the RQ tree structure; hence, only memory savings are possible with exhaustive search RQs. We give a monotonically convergent design algorithm that yields exhaustive search RQs for sources characterized by either analytic or training set descriptions. Residual quantizers designed by this algorithm yield a joint optimization between all RQ stages instead of an independent optimization obtained with sequential use of the Generalized Lloyd Algorithm.
Exhaustive search RQs are tested extensively on memoryless Gaussian, memoryless Laplacian, Gaus-Markov and intensity imagery sources. For sources with memory, exhaustive search RQs may give memory saving of 4 to 16 times that required of ESVQs for a normalized SQNR performance at rates of 2, 1 and 0.5 bps.
We impose additional structure on RQs that does not invalidate the necessary RQ optimality conditions but which allows computationally efficient searches of the RQ tree structure. This additional structure forces a "reflecting" or "folding" symmetry on the tree structure that gives simple hyperplane partition boundaries between equivalence classes. We call these residual quantizers reflected RQs or origami RQs are demonstrated to give both memory and computational savings over that required by ESVQs for normalized SQNR performance.
The M-algorithm is also evaluated as an efficient but suboptimal search strategy in the implementation and design of RQ codes. We test several RQs designed with the use of the M-algorithm.