Fully Connected Networks on a Diet With the Mediterranean Matrix Multiplication

Abstract

This article proposes the Mediterranean matrix multiplication, a new, simple and practical randomized algorithm that samples angles between the rows and columns of two matrices with sizes <inline-formula> <tex-math notation="LaTeX">$m, n, $ </tex-math></inline-formula> and <inline-formula> <tex-math notation="LaTeX">$p$ </tex-math></inline-formula> to approximate matrix multiplication in <inline-formula> <tex-math notation="LaTeX">$O(k(mn+np+mp))$ </tex-math></inline-formula> steps, where <inline-formula> <tex-math notation="LaTeX">$k$ </tex-math></inline-formula> is a constant only related to the precision desired. The number of instructions carried out is mainly bounded by bitwise operators, amenable to a simplified processing architecture and compressed matrix weights. Results show that the method is superior in size and number of operations to the standard approximation with signed matrices. Equally important, this article demonstrates a first application to machine learning inference by showing that weights of fully connected layers can be compressed between <inline-formula> <tex-math notation="LaTeX">$30\times $ </tex-math></inline-formula> and <inline-formula> <tex-math notation="LaTeX">$100\times $ </tex-math></inline-formula> with little to no loss in inference accuracy. The requirements for pure floating-point operations are also down as our algorithm relies mainly on simpler bitwise operators.