AMS Sketch For Inner Product Estimation

Problem

Let $\vec x = (x_1, ..., x_n)$ , $\vec y = (y_1, ..., y_n) \in \mathbb{R}^n$ . Given $\delta \in (0, 1)$ , construct a data structure with space usage $O \left( \frac{1}{\epsilon^2} \log \frac{1}{\delta} \right)$ , such that with failure probability at most $\delta \in (0, 1)$ ,

it returns an estimate of the inner product $\left< \vec x, \vec y \right>$ with error $O( \epsilon \cdot \Vert \vec x \Vert_2 \cdot \Vert \vec y \Vert_2 )$ .

Remark: If we have $\vec x = \vec y$ , we get an estimator of $\Vert \vec x \Vert_2^2$ with $\epsilon$ -relative error.

Prototype

Let $\vec \sigma = (\sigma_1, ..., \sigma_n) \in \{ - 1, 1 \}^n$ a sequence of $n$ independent Rademachers.

Define

X \doteq \left< \vec x, \vec \sigma \right>, \qquad Y \doteq \left< \vec y, \vec \sigma \right>.

Theorem. $X \cdot Y$ is an unbiased estimator of $\left< \vec x, \vec y \right>$ .

Proof. Observe $\forall i, j \in [n]$ , if entries of $\sigma$ are pairwise independent, then

\mathbb{E} [ \sigma_i \sigma_j ] = \begin{cases} 1, & i = j \\ 0, & i \neq j \end{cases}.

Hence,

\begin{aligned} \mathbb{E} [ X \cdot Y ] &= \mathbb{E} \left[ \left( \sum_{i \in [n] } \sigma_i x_i \right) \left( \sum_{j \in [n] } \sigma_j y_j \right) \right] \\ &= \sum_{i, j \in [n] } \mathbb{E} [ \sigma_i \sigma_j ]x_i y_j \\ &= \sum_{i \in [n] } x_i y_i. \end{aligned}

$\square$

Theorem. $\mathbb{Var}[ X \cdot Y ] \le \Vert \vec x \Vert_2^2 \cdot \Vert \vec y \Vert_2^2$ .

Proof. If entries of $\sigma$ are four-wise independent, then

\begin{aligned} \mathbb{Var} [ X \cdot Y ] &= \mathbb{Var} \left[ \left( \sum_{i \in [n] } \sigma_i x_i \right) \left( \sum_{j \in [n] } \sigma_j y_j \right) \right] \\ &= \mathbb{Var} \left[ \sum_{i \neq j \in [n] } \sigma_i \sigma_j x_i y_j \right] \\ &= \sum_{i \neq j } \mathbb{Var} \left[ \sigma_i \sigma_j x_i y_j \right] + \sum_{i \neq j, k \neq \ell, (i, j) \neq (k, \ell) } \mathbb{Cov} [ \sigma_i \sigma_j x_i y_j, \sigma_k \sigma_\ell x_k y_\ell ]\\ &= \sum_{i \neq j } x_i^2 y_j^2 \\ &\le \Vert \vec x \Vert_2^2 \cdot \Vert \vec y \Vert_2^2 \end{aligned}

$\square$

If we have $m$ independent copies of $X$ and $Y$ , denoted as $X_1, ..., X_m$ , and $Y_1, ..., Y_m$ , then we can compute the average $(1 / m) \cdot \sum_{i \in [m] } X_i \cdot Y_i$ , whose variance is bounded by $(1 / m) \cdot \Vert \vec x \Vert_2^2 \cdot \Vert \vec y \Vert_2^2$ . If we set $m = 1 / \epsilon^2$ , then it becomes $\epsilon^2 \cdot \Vert \vec x \Vert_2^2 \cdot \Vert \vec y \Vert_2^2$ and by Chebyshev's inequality $|(1 / m) \cdot \sum_{i \in [m] } X_i \cdot Y_i - \left< \vec x , \vec y \right> |$ is bounded by $\epsilon \cdot \Vert \vec x \Vert_2 \cdot \Vert \vec y \Vert_2$ with constant probability.

By Chernoff bound, we can boost the probability to $1 - \delta$ , by repeating the experiment $O(\log \frac{1}{\delta})$ times and taking the median of the estimation.

Computing $(1 / m) \cdot \sum_{i \in [m] } X_i \cdot Y_i$ takes $O( 1 / \epsilon^2 )$ time. Repeating this $O(\log \frac{1}{ \delta})$ times and taking the median results in time complexity $O( \frac{\log (1 / \delta) }{\epsilon^2} )$ .

On the other hand, we construct $O ( \epsilon^2 \cdot \log \frac{1}{\delta} )$ copies of $X$ , which takes time

O ( n \cdot \epsilon^2 \cdot \log \frac{1}{\delta} ).

Algorithm

In this section, we show how to reduce the construction time to

O ( n \cdot \log \frac{1}{\delta} ).

Given $m \in \mathbb{N}^+$ , let $h : [n] \rightarrow [m]$ be a pairwise independent hash function.

Let $\vec X = (X_1, ..., X_m), \vec Y = (Y_1, ..., Y_m) \in \mathbb{R}^m$ be random vectors, such that $\forall t \in [m]$ ,

X_t = \sum_{ i \in [n] : h(i) = t } \sigma_i x_i, \\ Y_t = \sum_{ i \in [n] : h(i) = t } \sigma_i y_i.

Theorem. $\left< \vec X, \vec Y \right>$ is an unbiased estimator of $\left< \vec x, \vec y \right>$ .

Proof.

If entries of $\sigma$ are pairwise independent, then

\begin{aligned} \mathbb{E} \left[ \left< \vec X, \vec Y \right> \right] &= \sum_{ t \in [m] } \mathbb{E}[ X_t Y_t ] \\ &= \sum_{ t \in [m] } \mathbb{E} \left[ \sum_{ i, j \in [n] : h(i) = h(j) = t } \sigma_i \sigma_j x_i y_j \right] \\ &= \sum_{ t \in [m] } \mathbb{E} \left[ \sum_{ i \in [n] } \frac{1}{m} x_i y_i + \sum_{ i \neq j } \frac{1}{m^2} \sigma_i \sigma_j x_i y_j\right] \\ &= \sum_{ i \in [n] } x_i y_i \end{aligned}

$\square$

Theorem. $\mathbb{Var} \left[ \left< \vec X, \vec Y \right> \right] \le \frac{1}{m} \cdot \Vert \vec x \Vert_2^2 \cdot \Vert \vec y \Vert_2^2$ .

Proof. If entries of $\sigma$ are four-wise independent, then

\begin{aligned} \mathbb{Var} \left[ \left< \vec X, \vec Y \right> \right] &= \mathbb{Var} \left[ \sum_{ t \in [m] } X_t Y_t \right] \\ &= \mathbb{Var} \left[ \sum_{ i, j \in [n] : h(i) = h(j) } \sigma_i \sigma_j x_i y_j \right] \\ &= \mathbb{Var} \left[ \sum_{ i \neq j, h(i) = h(j) } \sigma_i \sigma_j x_i y_j \right] \\ &= \sum_{i \neq j } \mathbb{Var} \left[ 1_{ [ h(i) = h (j) ] } \cdot \sigma_i \sigma_j x_i y_j \right] \\ &\quad+ \sum_{i \neq j, k \neq \ell, (i, j) \neq (k, \ell) } \mathbb{Cov} [ 1_{ [ h(i) = h (j) ] } \cdot \sigma_i \sigma_j x_i y_j, 1_{ [ h(k) = h (\ell ) ] } \cdot \sigma_k \sigma_\ell x_k y_\ell ] \\ &= \sum_{i \neq j } \mathbb{E} \left[ \left( 1_{ [ h(i) = h (j) ] } \cdot \sigma_i \sigma_j x_i y_j \right)^2 \right] \\ &= \sum_{i \neq j } \frac{1}{m} \cdot x_i^2 y_j^2 \\ &\le \frac{1}{m} \cdot \Vert \vec x \Vert_2^2 \cdot \Vert \vec y \Vert_2^2 \end{aligned}

$\square$

By setting $m = 1/ \epsilon^2$ , repeating the procedure $O(\log \frac{1}{\delta})$ times and taking the median as our estimation, we can obtained the desired result.

Reference

[1] G. Cormode and K. Yi, Small Summaries for Big Data, 1st ed. Cambridge University Press, 2020.