Quantization of rank-$r$ matrices, with Application to Discrete Cosine Transform

Abstract

This work addresses the problem of quantizing a product of rank-r matrices based on a recently proposed optimal algorithm with r = 1, which exploits a rescaling-invariance property of the problem. We first show that the rescaling-invariance characterization used in the rank-one case extends to the general case, but leads to a NP-hard problem. Therefore, we propose two heuristics that use the optimal rank-one quantization algorithm as a building block. We further analyze the rescaling-invariance of both heuristics to alleviate the impact of overflow and underflow that arise in low-precision formats. We apply our framework to the quantization of the Discrete Cosine Transform and to the compression of images. In the first application, our heuristics outperform the naive round-to-nearest strategy, and in the second application, we provide a compression algorithm that achieves a better reconstruction than a similar and competing method, but with a larger compression ratio.