随机算法 (Fall 2011)/Verifying Matrix Multiplication

From EtoneWiki
Jump to: navigation, search

Verifying Matrix Multiplication

Consider the following problem:

  • Input: Three matrices and .
  • Output: return "yes" if and "no" if otherwise.

A naive way of checking the equality is first computing and then comparing the result with . The (asymptotically) fastest matrix multiplication algorithm known today runs in time . The naive algorithm will take asymptotically the same amount of time.

Freivalds Algorithm

The following is a very simple randomized algorithm, due to Freivalds, running in only time:

Algorithm (Freivalds)
  • pick a vector uniformly at random;
  • if then return "yes" else return "no";

The product is computed by first multiplying and then . The running time is because the algorithm does 3 matrix-vector multiplications in total.

If then for any , thus the algorithm will return a "yes" for any positive instance (). But if then the algorithm will make a mistake if it chooses such an that . However, the following lemma states that the probability of this event is bounded.

Lemma
If then for a uniformly random ,
.
Proof.
Let . The event is equivalent to that . It is then sufficient to show that for a , it holds that .

Since , it must have at least one non-zero entry. Suppose that .

We assume the event that . In particular, the -th entry of is

The can be calculated by

Once all where are fixed, there is a unique solution of . That is to say, conditioning on any , there is at most one value of satisfying . On the other hand, observe that is chosen from two values uniformly and independently at random. Therefore, with at least probability, the choice of fails to give us a zero . That is, .

When , Freivalds algorithm always returns "yes"; and when , Freivalds algorithm returns "no" with probability at least 1/2.

To improve its accuracy, we can run Freivalds algorithm for times, each time with an independent random , and return "yes" iff all running instances pass the test.

Freivalds' Algorithm (multi-round)
  • pick vectors uniformly and independently at random;
  • if for all then return "yes" else return "no";

If , then the algorithm returns a "yes" with probability 1. If , then due to the independence, the probability that all have is at most , so the algorithm returns "no" with probability at least . Choose . The algorithm runs in time and has a one-sided error (false positive) bounded by .