CROQuant: Complex Rank-One Quantization Algorithm

Abstract

This work presents a quantization algorithm for complex-valued rank-one matrices that exploits rescaling-invariances of the problem to obtain better results than round-to-nearest strategy. This algorithm is also used as a building block for an heuristic strategy to quantize complex-valued butterfly-structured sparse matrices appearing for example in the fast Fourier transform. Compared to element-wise round-to-nearest quantization, the number of bits is reduced by 30% for a given precision on butterfly matrices, while maintaining a polynomial time complexity in the dimension of the matrices.