CROQuant: Complex Rank-One Quantization Algorithm

Abstract

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