Online Frequent Directions

Problem

One scenario is to approximate $A \in \mathbb{R}^{n \times d}$ in an online fashion, i.e., the rows of $A$ comes on by one (no missing values). Denote the $i$ -th row of $A$ as $a_i$ . We need to maintain a smaller matrix $B \in \mathbb{R}^{\ell \times d}$ ( $\ell \ll n$ ), termed the matrix sketch of $A$ , trying to minimize

\begin{aligned} \max_{x \in \mathbb{R}^d, \Vert x \Vert_2 = 1} \Big| \Vert A x \Vert_2^2 - \Vert B x \Vert_2^2 \Big| &= \max_{x \in \mathbb{R}^d, \Vert x \Vert_2 = 1} \Big| x^T (A^T A - B^T B) x \Big| = \Vert A^T A - B^T B \Vert_2. \end{aligned}

Algorithm

We will present an algorithm, which achieves an error of

\Vert A^T A - B^T B \Vert_2 \le \min_{k \in [\ell]} \frac{\Vert A - A_{[k]} \Vert _F^2}{ \ell - k },

where $\Vert A \Vert _F \doteq \sqrt{ \sum_{ i \in [n], j \in [d] } A_{i,j}^2 }$ is the Frobenius norm of $A$ .

Algorithm [1]

$B \leftarrow$ empty matrix.

For $i \in [n]$ :

$\qquad$ $B \leftarrow [B ; a_i]$ matrix obtained by inserting $a_i$ after the last row $B$

$\qquad$ $B$ has $\ell$ rows:

$\qquad$ $\qquad$ $U_i, \Sigma_i, V_i \leftarrow \text{SVD} (B)$ , such that $B = U_i \Sigma_i V_i^T$ .

$\qquad$ $\qquad$ $\overline{\Sigma_i} \leftarrow \sqrt{ \max \{ \Sigma_i^2 - \sigma_{i, \ell}^2 I, 0 \} }$

$\qquad$ $\qquad$ $B \leftarrow \overline{\Sigma_i} V_i^T$

Here $\sigma_{i, \ell}$ is the $\ell$ -th largest singular value of $\Sigma_i$ . The line 6 throws away all singular values that are less than $\sigma_{i, \ell}$ , and then subtract the squares of all singular values that are greater by $\sigma_{i, \ell}^2$ .

For the convenience of discussion, at each iteration, if $B$ has less than $\ell$ rows after insertion, we still define

U_i, \Sigma_i, V_i \leftarrow \text{SVD} (B) , \, \text{ and } \, \overline{\Sigma_i} = \Sigma_i.

To analyze the error, first observe that, when the algorithm stops,

\begin{aligned} A^T A - B^T B &= \sum_{i \in [n]} \left( A_i^T A_i + B_{i - 1}^T B_{i - 1} - B_i^T B_i \right). \end{aligned}

Therefore, for an arbitrary unit vector $x \in \R^d$ ,

\begin{aligned} x^T A^T A x - x ^T B^T B x &= \sum_{i \in [n]} \left( x^T A_i^T A_i x + x^T B_{i - 1}^T B_{i - 1} x - x^T B_i^T B_i x \right) \\ &= \sum_{i = 1}^j \left( \left\langle A_i, x \right\rangle ^2 + \Vert B_{i - 1} x \Vert_2^2 - \Vert B_{i} x \Vert_2^2 \right) \\ &= \sum_{i = 1}^n \left( \Vert \Sigma_i V_i^T v \Vert_2^2 - \Vert \overline{\Sigma_i} V_i^T v \Vert_2^2 \right) \\ &\le \sum_{i = 1}^n \sigma_{i, \ell }^2. \end{aligned}

The last inequality holds since $V_i^T x$ is a unit vector, and $\Sigma_i^T \Sigma_i - \overline{\Sigma_i}^T \overline{\Sigma_i}$ is a diagonal matrix whose elements are bounded by $\sigma_{i, \ell}^2$ .

It is left to bound the size of $\sum_{i = 1}^n \sigma_{i, \ell }^2$ :

\begin{aligned} \ell \cdot \sum_{i = 1}^n \sigma_{i, \ell }^2 &\le \sum_{i = 1}^n \left( \Vert \Sigma_i \Vert^2_F - \Vert \overline{\Sigma_i} \Vert^2 _F \right) \\ &= \sum_{i = 1}^n \left( \Vert C_i \Vert_F^2 - \Vert B_{i} \Vert^2_F \right) \\ &= \sum_{i = 1}^n \left( \Vert a_i \Vert_2^2 + \Vert B_{i - 1} \Vert^2_F - \Vert B_{i} \Vert^2_F \right) \\ &= \Vert A \Vert^2_F - \Vert B \Vert^2_F. \end{aligned}

Finally, let $u_1, \ldots, u_d \in \mathbb{R}^d$ be the right singular vectors of $A$ . Then for each $k \in [\ell]$ , it holds that

\begin{aligned} \Vert A \Vert^2_F - \Vert B \Vert^2_F &= \sum_{i = 1}^k \Vert A u_i \Vert_2^2 + \sum_{i = k + 1}^d \Vert A u_i \Vert_2^2 - \Vert B \Vert^2_F \\ &= \sum_{i = 1}^k \Vert A u_i \Vert_2^2 + \Vert A - A_{[k]} \Vert_2^2 - \Vert B \Vert^2_F \\ &\le \sum_{i = 1}^k \big( \Vert A u_i \Vert_2^2 - \Vert B u_i \Vert_2^2 \big) + \Vert A - A_{[k]} \Vert_2^2 & \qquad \Vert B \Vert^2_F = \Vert B V\Vert^2_F \ge \sum_{i = 1}^k \Vert B u_i \Vert_2^2 \\ &\le \sum_{i = 1}^k \big( \Vert A u_i \Vert_2^2 - \Vert B u_i \Vert_2^2 \big) + \Vert A - A_{[k]} \Vert_2^2 \\ &\le k \cdot \Vert A^T A - B^T B \Vert_2 + \Vert A - A_{[k]} \Vert_2^2. \end{aligned}

In conclusion, we have

\ell \cdot \Vert A^T A - B^T B \Vert_2 \le k \cdot \Vert A^T A - B^T B \Vert_2 + \Vert A - A_{[k]} \Vert_2^2,

which proves the theorem.

Remark: In the proof we apply the fact that the squared Frobenius norm of a matrix $M$ equals the sum of the squares of its singular values. Let $M = \sum_{j = 1}^d \sigma_j u_j v_j^\top$ , then

\begin{align} \Vert M \Vert_{\mathrm{F}}^2 = \Vert U \Sigma V^T \Vert_{\mathrm{F}}^2 = \Vert \Sigma \Vert_{\mathrm{F}}^2. \end{align}

The last inequality holds since $U$ and $V^T$ are rotations which does not change the Frobenius norm.

In conclusion,

\begin{aligned} \frac{ \Vert A^T A - B^T B \Vert_2 }{ \Vert A \Vert^2_F} \le \frac{ \Vert A^T A - B^T B \Vert_2 }{ \Vert A \Vert^2_F - \Vert B \Vert^2_F} \le \frac{2}{k}. \end{aligned}

$\square$

A Counterpart For Heavy Hitters

We apply similar idea for the heavy hitter problem in streaming model.

Problem

There is a streaming $S = \{ a_1, ..., a_m \}$ of $m$ elements each from a finite domain $[d]$ . Given a parameter $k$ , we want to find the elements in $[d]$ whose frequencies, i.e., the number of times they appear in $S$ , are at least $k$ .

Algorithm

The following algorithm will provide under-estimates of elements' frequencies, with space usage $2k$ and error $m / k$ .

Processing Stream

$B_0 \leftarrow$ an empty (element, frequency) list of capacity $2k$ .

For $t \in [m]$ :

$\qquad$ $C_t \leftarrow$ list obtained by inserting $\{ a_t, 1 \}$ into $B_{t - 1}$ .

$\qquad$ If $C_t$ has size $2k$ :

$\qquad$ $\qquad$ $B_t \leftarrow$ list obtained from $C_t$ by merging frequencies.

$\qquad$ $\qquad$ // each element in $[d]$ now appears in $B_t$ at most once.

$\qquad$ $\qquad$ $\sigma_t \leftarrow$ the $k$ -th largest frequency in $B_t$ .

$\qquad$ $\qquad$ Subtract the frequency of each element in $B_t$ by $\sigma_t$ .

$\qquad$ $\qquad$ Remove elements with non-positive frequencies.

$\qquad$ Else

$\qquad$ $\qquad$ $\sigma_t \leftarrow 0;$

$\qquad$ $\qquad$ $B_t \leftarrow C_t$ .

QUERY
Input: $B_t$ for some $t \in [m]$ , $v \in [d].$
Output: frequency estimation of $v$ in $\{a_1, ...., a_t \}$

$\hat f_{B_t}[v] \leftarrow 0;$

for $(v_i, f_i) \in B_t$ do

$\qquad$ if $v_i = v$ then

$\qquad$ $\qquad$ $\hat f_{B_t} [ v ] \leftarrow \hat f_{B_t} [v] + f_i;$

Return $\hat f_{B_t} [v]$ .

Observe that for $v \in [d]$ , if $v$ does not appears in $B_t$ , then the algorithm returns 0.

Time

The amortized time for each update is $O(1)$ .

Inserting $\{a_i, 1\}$ into $B_{i - 1}$ takes $O(1)$ time.
Merging $C_i$ , subtracting elements' frequencies by $\sigma_i$ and removing non-positive elements take $O(k)$ time. But this happens only every $k / 2$ updates. Hence the amortized time is $O(1)$ .

Error

Theorem 1. $\forall t \in [m], v \in [d]$ , $\hat f_{B_t} [v]$ is an underestimate of $v$ 's frequency in $\{a_1, ... a_t \}$ .

Proof. Obviously true by how the algorithm works.

Theorem 2. $\forall v \in [d], t \in [m]$ , let $f_t [v]$ be the number of times $v$ appears in $\{a_1, ..., a_t \}$ . We have that
$f_t[v] - \hat f_{B_t} [v] < \frac{t}{k}.$

Proof. For each $i \in \{0, 1, ..., m \}$ , define $\Vert B_i \Vert_1 = \left( \sum_{ (v_j, f_j) \in B_i } f_j \right)$ and for each $i \in [m]$ , let $\Vert C_i \Vert_1 = \left( \sum_{ (v_j, f_j) \in C_i } f_j \right)$ . Observe that

\begin{aligned} f_t[v]- \hat f_{B_t} [v] \le \sum_{i \in [t] } \sigma_i. \end{aligned}

On the other hand,

\begin{aligned} t - \Vert B_m \Vert_1 &= \sum_{i \in [t] } \left( 1 + \Vert B_{i - 1} \Vert_1 - \Vert B_i \Vert_1 \right) \\ &= \sum_{i \in [t] } \left( \Vert C_i \Vert_1 - \Vert B_i \Vert_1 \right) \\ &\ge k \cdot \sum_{i \in [t] } \sigma_i. \end{aligned}

Combined, we get $f_t[v]- \hat f_{B_t} [v] \le \frac{t - \Vert B_t \Vert_1}{k}$ .

Reference

[1]. Edo, Liberty. "Simple and deterministic matrix sketching." In Proceedings of the 19th ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 581-588. ACM, 2013.