REVISITING COLUMN-WISE VECTOR QUANTIZATION FOR MEMORY-EFFICIENT MATRIX MULTIPLICATION

摘要

Matrix multiplication is a fundamental operation for data analysis. Memory-efficient matrix multiplication is always essential, especially for problems involving large-scale datasets. We present PQMM, a column-wise product quantization for memory-efficinet matrix multiplication. A simple idea of column-wise vector quantization is revisited. Each column of a data matrix is quantized into an index and the matrix product is approximated by the sum of the outer products obtained from the codewords fetched by the indices. The empirical evaluation illustrates that, with the same amount of memory, PQMM outperforms the state-of-the-art sketch-based method with respect to the error. We further show that a combination of the sketch-based method and PQMM results in a slightly less accurate data representation, but which is significantly more memory-efficient.