随机算法 (Fall 2011)/Verifying Matrix Multiplication
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 ,
- .
- 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 .