Skip to article frontmatterSkip to article content

Approximate matrix-multiplication is the quintessential example of a sampling-based RandNLA algorithm Drineas et al., 2006. Consider the matrix-matrix product

ABT=i=1naibiT,A=[a1an],B:=[b1bn].\vec{A}\vec{B}^\T = \sum_{i=1}^{n} \vec{a}_i \vec{b}_i^\T ,\qquad \vec{A} = \begin{bmatrix} | & & | \\ \vec{a}_1 & \cdots & \vec{a}_n \\ | & & | \end{bmatrix} ,\quad \vec{B}:= \begin{bmatrix} | & & | \\ \vec{b}_1 & \cdots & \vec{b}_n \\ | & & | \end{bmatrix}.

We can approximate (7.1) by sampling. In particular, consider a probability distribution P:=(p1,,pn)\mathcal{P} := (p_1, \ldots, p_n) on the indices {1,,n}\{1, \ldots, n\} such that if sPs\sim \mathcal{P} then P[s=i]=pi\PP[s=i] = p_i. Then clearly,

E[1psasbsT]=ABT.\EE\left[ \frac{1}{p_s}\vec{a}_s \vec{b}_s^\T \right] = \vec{A}\vec{B}^\T.

This suggests a simple estimator.

Variance Bound

One can directly compute the variance of the approximate matrix multiplication estimator.

Proof

Clearly the estimator is unbiased, and by basic properties of the expectation,

E[ABAMMm(A,B)F2]=m1E[ABAMM1(A,B)F2]=m1(E[AMM1(A,B)F2]ABF2).\begin{aligned} \EE[ \| \vec{A}\vec{B} - \Call{AMM}_m(\vec{A},\vec{B}) \|_\F^2] &= m^{-1} \EE[ \| \vec{A}\vec{B} - \Call{AMM}_1(\vec{A},\vec{B}) \|_\F^2] \\&= m^{-1} (\EE[ \Call{AMM}_1(\vec{A},\vec{B}) \|_\F^2] - \|\vec{A}\vec{B}\|_\F^2). \end{aligned}

Now, by direct computation,

E[AMM1(A,B)F2]=E[ps1asbsTF2]=i=1npipi1aibiTF2=i=1npi1ai2bi2.\begin{aligned} \EE[ \Call{AMM}_1(\vec{A},\vec{B}) \|_\F^2] &= \EE\left[ \left\| p_s^{-1}\vec{a}_s \vec{b}_s^\T \right\|_\F^2\right] \\&= \sum_{i=1}^{n} p_i \left\| p_i^{-1}\vec{a}_i \vec{b}_i^\T \right\|_\F^2 \\&= \sum_{i=1}^{n} p_i^{-1} \| \vec{a}_i \|^2 \| \vec{b}_i \|^2. \end{aligned}

In particular, note that if piai2p_i \propto \|\vec{a}_i\|^2 (or pibi2p_i \propto \|\vec{b}_i\|^2), then

E[ABAMMm(A,B)F2]=1m(AF2BF2ABF2).\EE\left[ \| \vec{A}\vec{B} - \Call{AMM}_m(\vec{A},\vec{B}) \|_\F^2 \right] = \frac{1}{m}\left( \|\vec{A}\|_\F^2\|\vec{B}\|_\F^2 - \|\vec{A}\vec{B}\|_\F^2\right).
References
  1. Drineas, P., Kannan, R., & Mahoney, M. W. (2006). Fast Monte Carlo Algorithms for Matrices I: Approximating Matrix Multiplication. SIAM Journal on Computing, 36(1), 132–157. 10.1137/s0097539704442684