Thursday, September 6, 2012

Randomized algorithm for Verification of Matrix Multiplication

Suppose you want to verify if AB = C and A is m by n and B is n by k then, the time taken for this is O(mnk + nk) = O(mnk)

What if you had a vector x, then ABx = Cx...  here x is a random vector.
x  is of dimensionality k by 1  and created by randomly sampling from a gaussian distribution.

Now the time taken to compute Bx is O(nk)  and is of dimentionaity n by 1 and time taken to compute ABx is O(mn). Similarly, time taken to compute Cx is O(mk)...

So the total time taken to verify is O(mn+nk+mk) and not O(mnk)

No comments:

Post a Comment