Randomized Matrix Multiplication

• categories: Linear algebra, Algorithm

Definition

Randomized matrix multiplication approximates the product of two large matrices $A\in {\mathbb{R}}^{m\times n}$ and $B\in {\mathbb{R}}^{n\times p}$ by sampling columns (or rows) of $A$ and rows (or columns) of $B$ according to a probability distribution. This reduces the computational cost while maintaining an acceptable approximation error.

The aim is to compute an approximation $\tilde{C}$ of the exact product $C=AB$:

$$C\approx \tilde{C}.$$

Steps in Randomized Matrix Multiplication

1. Input:
   Matrices $A\in {\mathbb{R}}^{m\times n}$ and $B\in {\mathbb{R}}^{n\times p}$, and the number of samples $k\ll n$.

2. Probability Distribution:
   Define probabilities $p_i$ for selecting the $i$-th column of $A$ and the corresponding $i$-th row of $B$:

   $$p_i=\frac{\Vert A_{:,i}{\Vert }_2\cdot \Vert B_{i,:}{\Vert }_2}{{\sum }_{j=1}^n\Vert A_{:,j}{\Vert }_2\cdot \Vert B_{j,:}{\Vert }_2}.$$

3. Sampling:
   Sample $k$ indices $\{i_1,i_2,\dots ,i_k\}$ from $\{1,2,\dots ,n\}$ according to $p_i$ (with replacement).

4. Rescale:
   Form reduced matrices $\tilde{A}$ and $\tilde{B}$ by selecting and rescaling the sampled columns of $A$ and rows of $B$:

   $${\tilde{A}}_{:,j}=\frac{A_{:,i_j}}{\sqrt{k{p}_{i_j}}},{\tilde{B}}_{j,:}=\frac{B_{i_j,:}}{\sqrt{k{p}_{i_j}}}.$$

5. Approximate Product:
   Compute the approximation:

   $$\tilde{C}=\tilde{A}\tilde{B}.$$

Key Properties

1. Reduction in Complexity:

   • Exact multiplication costs $O(mnp)$.
   • Randomized multiplication costs $O(k(m+p))$, where $k\ll n$.

2. Error Bounds: The Frobenius Norm error is bounded with high probability:

   $$\Vert C-\tilde{C}{\Vert }_F\le ϵ\Vert A{\Vert }_F\Vert B{\Vert }_F,$$

   for $ϵ\in (0,1)$, given enough samples $k$.

3. Trade-Off: Increasing $k$ improves the accuracy of $\tilde{C}$ but increases computational cost.

4. Unbiased Estimation: The expectation of the approximation is equal to the exact product:

   $$\mathbb{E}[\tilde{C}]=C.$$