| The classical theory of lossy source coding focuses on the performance, in terms of rate and distortion, of quantization. However, there is little understanding of the fundamental relationship between performance and complexity. In this dissertation, this relationship is investigated in the high-rate domain from three different angles.;The first part of this dissertation studies the optimal achievable performance of the "least complex" quantizers, namely uniform scalar quantizers, with the goal of quantifying the ultimate performance penalty for reducing complexity to a minimum. Asymptotic formulas for the optimal step size and the optimal mean-squared distortion are derived for symmetric source densities with infinite support. For the class of generalized Gamma densities, the overload distortion is asymptotically negligible, and the maximum Signal-to-Noise Ratio (SNR) increases at about 6 decibels per bit. But there exist source densities whose maximum SNR increases with an asymptote of zero decibel per bit. For such sources, the performance penalty for using simple uniform quantization is enormous.;In the second part, a Turing-machine framework is developed for studying the rate of increase of quantization complexity as rate increases. The goal is to investigate the possibility of nearly optimal quantization for a given dimension with relatively low encoding complexity. The main result shows that for scalar quantization, the complexity of asymptotically optimal quantization is polynomially bounded if the complexity of the optimal distribution of quantization points for the source is polynomially bounded. It follows that a class of generalized Gaussian densities, which includes Laplacian, is asymptotically optimally quantizable with polynomial complexity.;The third part introduces practical methods for reducing the storage complexity of quantization. A low-storage quantizer, called a secondary quantizer, is used to compress the codevectors of the (primary) unstructured vector quantizer in a lossy fashion. Design algorithms for optimizing the primary and secondary codebooks are presented. These methods are also applied to tree-structured vector quantization. By exploiting the correlation among the testvectors in the tree, both encoder and decoder storage can be significantly reduced, relative to the conventional method of storing testvectors (or test hyperplanes), with little increase in distortion. |
