A Simplified Reduction for Error Correcting Matrix Multiplication Algorithms

The problem of efficiently multiplying two $n\times n$ matrices is one of the most fundamental problems in computer science. The naive approach for Matrix Multiplication takes $O(n^3)$ time, and there is a lot of ongoing research attempting to improve the running time. Strassen [29] first gave a well-known and widely adopted algorithm, with the running time of $O(n^{2.8074})$. Since then, a long line of work ([24, 5, 26, 25, 28, 8, 27, 31, 22, 3, 9, 32]) has achieved improvement in the exponent, with the current best known algorithm having the runtime of $O(n^{2.3713})$ [2]. It is still an open problem to find the optimal running time for Matrix Multiplication.

A natural and relaxed version of the above question is to come up with an algorithm which outputs the product of two matrices, but is allowed to have some incorrect entries. In this work, we address the problem of correcting the output of such an algorithm. Assume that we have an algorithm for matrix multiplication which gets two matrices and outputs a matrix which has a fraction of its entries correct, is it possible to correct the incorrect entries efficiently, i.e., without significantly increasing the running time? For two $n\times n$ matrices $A$ and $B$, define their agreement, denoted by $\mathrm{agr}(A,B)$ as

Hence, the problem can be stated as correcting the output of the matrix multiplication algorithm which has some agreement with the correct product. It is perhaps more convenient to view this question as the problem of getting a worst-case to average-case approximate reduction for matrix multiplication. Worst-case to Average-case reductions could help us to get fast algorithms which work in the worst-case, if we could come up with fast average-case algorithms. On the opposite side, such reductions allow us to show that if a problem is known to be worst-case hard, then it is also average-case hard. So our problem could be restated as – Given an algorithm which gets two matrices $A,B\in {𝔽}_p^{n\times n}$, and outputs a matrix $C\in {𝔽}_p^{n\times n}$ such that $C$ has a non-trivial agreement with $AB$ in expectation, can we efficiently transform it into an algorithm which outputs the correct matrix product for all possible inputs?

We begin by recalling some basic coding theory terminology. A code $C$ over the Finite Field ${𝔽}_p$ is a subset $C\subseteq {𝔽}_p$. If $C$ is a linear subspace of ${𝔽}_p$, it is called a linear code. When the field is ${𝔽}_2$, we call it a binary code. Elements of the code are referred to as codewords. A code can be equivalently described by an encoding, which is an injective mapping $\mathrm{Enc}:{𝔽}_p^n\to {𝔽}_p^N$, whose range gives the code $C$. For a linear code, the encoding $\mathrm{Enc}:{𝔽}_p^n\to {𝔽}_p^N$ can be expressed as $\mathrm{Enc}(x)=Gx$, where $G\in {𝔽}_p^{N\times n}$ is called a generator matrix. The rate of the code $C\subseteq {𝔽}_p^N$ is given by ${\log }_p(|C|)/N$, or equivalently as $n/N$. The distance of the code $C$ is defined as $\underset{c_1,c_2\in C}{\min }\mathrm{\Delta }(c_1,c_2)$, where $\mathrm{\Delta }(c_1,c_2)=|\{i|{(c_1)}_i\ne {(c_2)}_i\}|/n$. ¹¹1Strictly speaking, it is called the relative distance of the code. However, we shall simply refer to it as distance in this work. We refer the reader to [15] for further details on this subject.

A well-known linear code which we use in this work is the Reed-Solomon code.

We now define the notion of list-decoding.

Next we define the notion of full-rank partition. This notion is a special case of the notion of $(m,\delta )$ full-rank partition used in [16]. Our definition corresponds to $m=n$ and $\delta =0$, which (in our opinion) is the most natural choice of parameters.

We proceed to mention the linear list-decodable code which we crucially use in our reduction.

We are certain that such codes are already known (see, e.g., [13]), however we could not find the exact statement in the literature. In particular, the notion of full-rank partition is a standard notion studied in the literature. We refer the reader to Appendix A for the proof of Lemma 7.

We now state a variant of Markov’s inequality which we use repeatedly in this work.

In this section, we present a reduction of matrix multiplication over the binary field to the one-sided error case of Lemma 11, using a binary linear code whose generating matrix has a full-rank partition. Specifically, we prove the following lemma.

The reduction is outlined in Algorithm 1. We now describe the steps of the reduction.

Let $G\in {𝔽}_2^{N\times n}$ be the generator matrix representing the binary linear code $BLC:{𝔽}_2^n\to {𝔽}_2^N$. For a matrix $M\in {𝔽}_2^{n\times n}$, define $\mathrm{Enc}(M)=M{G}^T$, i.e. $Enc$ is a function $\mathrm{Enc}:{𝔽}_2^{n\times n}\to {𝔽}_2^{n\times N}$ applying the binary linear code $BLC$ to every row of $M$.

Since $G$ has a full-rank partition, its rows can be partitioned into sets $P_1,P_2,\mathrm{\dots }{P}_t$, such that for every $i$ between $1$ and $t$, $|P_i|=n$ and the sub matrix ${G|}_{P_i}$ is full rank.

Now, for $A,B\in {𝔽}_2^{n\times n}$, we construct a matrix $C\in {𝔽}_2^{n\times N}$ such that $\mathrm{agr}(C,\mathrm{Enc}(AB))\ge 1/2+ϵ$ in expectation. To this end, we note that if $B\in {𝔽}_2^{n\times n}$ is chosen uniformly at random, then the matrix given by ${B{G}^T|}_{P_i}\in {𝔽}_2^{n\times m}$ will also be a uniformly random matrix, since ${G^T|}_{P_i}$ is full-rank. Our idea is to apply the encoding given by the sub-matrices ${G^T|}_{P_i}$ and then constructing $C$ by concatenating the columns of all the resultant matrices. Formally, we write C as:

where $\circ$ denotes the column concatenation. Now, we observe that

where the last inequality follows from the fact that for every $1\le i\le t$, ${B\cdot G^T|}_{P_i}$ is a uniformly random matrix. In other words, all the columns are generated by taking the product of two uniformly random matrices, for which $ALG$ has an agreement of $1/2+ϵ$.

Since ${𝔼}_{A,B}[\mathrm{agr}(C,\mathrm{Enc}(AB))]>1/2+ϵ$, by Markov’s inequality (Lemma 8), there must exist at least $ϵ$ fraction of rows of $C$ such that their agreement with the corresponding rows of $Enc(AB)$ is at least $1/2+ϵ/2$ in expectation. Formally, there is a set $R\subseteq [n]$ of rows of size $\left|R\right|\ge ϵn$ such that ${𝔼}_{A,B}[\mathrm{agr}(c_i,BLC(d_i))]>1/2+ϵ/2$ for all $i\in R$, where $c_i^T$ is the row indexed by $i$ in $C$ and $d_i^T$ is the row indexed by $i$ in $AB$.

Now, for each row $i\in R$, by another application of Markov’s inequality (Lemma 8) we can imply that there exists a subset of good inputs $GOO{D}_i$ of density at least $ϵ/2$ such that if $(A,B)\in GOO{D}_i$, $\mathrm{agr}(c_i,BLC(d_i))]>1/2+ϵ/4$. Therefore, with probability at least $ϵ\cdot ϵ/2$, the distance of the row $i$ of $C$ from the encoding of the row $i$ of the correct product $AB$ is at most $1/2-ϵ/4$.

Hence, for random choices of A and B, we can list decode these rows in nearly linear time and identify the correct row using an efficient Matrix-Vector product verification algorithm. Furthermore, the verification algorithm (Lemma 10) also lets us identify these good rows.

The Matrix-Vector product verification algorithm gets each vector $s\in {𝔽}_2^n$ from the list obtained by decoding the row $i$, and checks whether $s=B^T{A}_i$, where $A_i^T$ is the vector representing the row indexed by $i$ in $A$. If the output is YES, it implies that $s^T$ is the row $i$ of the correct matrix product $AB$.

Finally, fixing all entries in the undecoded rows by $0$ takes us to the one-sided error setting of [12], as stated in Lemma 11. That is,

• $\mathrm{■}$

  If ${(AB)}_{(i,j)}=0$, then $M_{(i,j)}=0$, and

• $\mathrm{■}$

  For at least $ϵ/2$ fraction of inputs $A,B\in {𝔽}_2^{n\times n}$, there are $ϵn$ rows $R\subseteq [n]$ such that ${(AB)}_{(i,j)}=M_{(i,j)}$ holds for all $(i,j)\in R\times [n]$.

This implies the following.

We now use Lemma 12 and Lemma 11 to obtain a worst case to average case reduction. In particular, we provide the proof of Theorem 1.

In this section, we show that our reduction can be generalized to any finite field ${𝔽}_p$, where $p$ is a prime.

This can be achieved by extending the one-sided error model of [12] to a zero-error model over ${𝔽}_p$. In the one sided error condition of Lemma 11, the output $1$ can be viewed as corresponding to the correct entry, while $0$ can be viewed as corresponding to $\perp$ or “Don’t know”.

The proof of Lemma 11 relied on the techniques from Additive Combinatorics. The reduction given by [12] for the one-sided error model proceeded by defining the good coordinates, which output $1$ with a significant probability on random input matrices. Thereafter, they expressed the input matrices as the sum of random matrices, and used the Probabilistic Bogolyubov Lemma to retrieve all the $1$ entries in the correct output. Although they proved the Probabilistic Bogolyobuv lemma for the binary field ${𝔽}_2$, their proof can be extended through similar techniques for Fourier analysis over $F_p$. Hence, the worst-case algorithm ${\mathrm{ALG}}^{\ast }$ in Lemma 14 can be obtained in the same way as the reduction for the one-sided error model, by tweaking the definition of good coordinates to be the coordinates which are not $\perp$ with a significant probability.

Hence, the lemma can be generalized as follows.

Below we sketch the proof of the lemma, mostly referencing the reduction analyzed in [12].