CROQuant: Complex Rank-One Quantization Algorithm, with Application to Butterfly Factorizations

Abstract

This paper presents a quantization algorithm for complex-valued rank-one matrices that exploits rescaling-invariances of the problem to reach improved accuracy with the same number of mantissa bits compared to the usual round-to-nearest strategy. This work extends results previously established in the real-valued setting to the complex domain, and provides an algorithm with a complete theoretical convergence analysis. The proposed approach replaces the naive expression of the optimal quantization problem as the optimization over $m+n$ (quantized) complex entries by the optimization of a function of a single complex-valued scaling parameter. The resulting function is piecewise constant, and we show that, despite the infinite number of piecewise constant regions induced by quantization, the associated optimization problem admits a minimizer under mild non-degeneracy assumptions. This algorithm is also used as a building block for a heuristic strategy to quantize complex-valued butterfly-structured sparse matrices appearing for example in the fast Fourier transform. For butterfly matrices, the number of bits is reduced by 30% for a given precision by our algorithm, compared to element-wise round-to-nearest quantization.