The following question is inspired with approximation of matrix multiplication computations occurring in numerical simulations and machine learning algorithms with a use of efficient integer arithmetic.

There are many possible variants of the question. For concreteness I'll propose one particular, but I am not very attached to this particular formulation.

How well can we approximate real matrix multiplication operation: $$ \_ \cdot \_ : \mathbb{R}_{\geq 0}^{I\times J} \times \mathbb{R}_{\geq 0}^{J\times K} \longrightarrow \mathbb{R}_{\geq 0}^{I\times K} $$

using matrix multiplication on a given (by $k$) finite prefix of natural numbers:

$$ \_ \odot \_ : \mathbb{N}_{\leq k}^{I\times J} \times \mathbb{N}_{\leq k}^{J\times K} \longrightarrow \mathbb{N}^{I\times K} $$

where: $$\mathbb{N}_{\leq k} = \{i \in \mathbb{N} \mid i \leq k \}$$

Of course in order to be precise we need to constrain the "remaining computation" that we might be allowed to do. One way to do it is to specify all allowed operations, another is to limit computational complexity. I'd like to avoid doing that explicitly and hope that the spirit of the question is clear.

The family of solutions I am thinking about is the family of approximations:

$$ A \cdot B \approx r ([ r^{-1} A s] \odot [s^{-1} B t]) t^{-1} $$

where $r, s, t$ are diagonal matrices that scale rows and columns of $A$ and $B$ and

$$[\_] : \mathbb{R}_{\geq 0} \longrightarrow \mathbb{N}_{\leq k}$$

is some projection operator e.g. round (or floor) and clip. I have a hard time defining a metric to minimize and finding optimal $r,s,t$.

Some questions:

Is my formulation generic enough to capture the problem?

How to more precisely model the problem to find suitable $r, s, t$?

Are there any references that might help with the task?

I'll be grateful for all and any help. Thank you.

  • $\begingroup$ I posted this question has been also on stackexchange 2 weeks ago. $\endgroup$ Oct 11, 2020 at 19:06


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.