Problem
There is a stream S S S ( t , Δ ) ∈ [ n ] × R (t, \Delta) \in [n] \times \mathbb{R} ( t , Δ ) ∈ [ n ] × R f ∈ R n f \in \mathbb{R}^n f ∈ R n S S S ∀ i ∈ [ n ] \forall i \in [n] ∀ i ∈ [ n ]
f i = ∑ ( t , Δ ) ∈ S ∧ t = i Δ .
f_i = \sum_{ (t, \Delta) \in S \wedge t = i} \Delta.
f i = ( t , Δ ) ∈ S ∧ t = i ∑ Δ. Given ϵ ∈ ( 0 , 1 ) \epsilon \in (0, 1) ϵ ∈ ( 0 , 1 ) ( 1 ± ϵ ) (1 \pm \epsilon) ( 1 ± ϵ ) ∥ f ∥ 2 2 \Vert f \Vert_2^2 ∥ f ∥ 2 2 1 − δ 1 - \delta 1 − δ O ( 1 ϵ 2 ln 1 δ ) O( \frac{1}{\epsilon^2 } \ln \frac{1}{\delta} ) O ( ϵ 2 1 ln δ 1 )
Solution
Based on Count-Sketch.
Algorithm
Count-Sketch
k ← O ( ln 1 δ ) ; m ← 3 ϵ 2 k \leftarrow O \left( \ln \frac{1}{ \delta} \right); m \leftarrow \frac{3}{\epsilon^2} k ← O ( ln δ 1 ) ; m ← ϵ 2 3 h 1 , h 2 , . . . , h k : [ n ] → [ m ] h_1, h_2, ..., h_k: [n] \rightarrow [m] h 1 , h 2 , ... , h k : [ n ] → [ m ] g 1 , g 2 , . . . , g k : [ n ] → { − 1 , 1 } g_1, g_2, ..., g_k: [n] \rightarrow \{-1, 1\} g 1 , g 2 , ... , g k : [ n ] → { − 1 , 1 } M ← { 0 } k × m M \leftarrow \{ 0 \}^{k \times m} M ← { 0 } k × m k × m k \times m k × m For ( t , Δ ) ∈ S : (t, \Delta) \in S: ( t , Δ ) ∈ S :
\qquad i ∈ [ k ] : i \in [k]: i ∈ [ k ] : \qquad\qquad M [ i , h i ( t ) ] ← M [ i , h i ( t ) ] + g i ( t ) ⋅ Δ M[i, h_i (t) ] \leftarrow M[i, h_i (t) ] + g_i(t) \cdot \Delta M [ i , h i ( t )] ← M [ i , h i ( t )] + g i ( t ) ⋅ Δ \qquad
Estimation of ∥ f ∥ 2 2 \Vert f \Vert_2^2 ∥ f ∥ 2 2
For i ∈ [ k ] : i \in [k]: i ∈ [ k ] :
\qquad M i M_i M i i i i M M M \qquad a i ← ∥ M i ∥ 2 a_i \leftarrow \Vert M_i \Vert_2 a i ← ∥ M i ∥ 2 Return the median of ( a i 2 ) i ∈ [ k ] (a_i^2)_{i \in [k] } ( a i 2 ) i ∈ [ k ]
Analysis
Theorem 1. ∀ i ∈ [ k ] , E [ a i 2 ] = ∥ f ∥ 2 2 \forall i \in [k], \mathbb{E}[ a_i^2 ] = \Vert f \Vert_2^2 ∀ i ∈ [ k ] , E [ a i 2 ] = ∥ f ∥ 2 2
Proof. Consider a fixed i ∈ [ k ] i \in [k] i ∈ [ k ] ∀ j ∈ [ m ] \forall j \in [m] ∀ j ∈ [ m ] h i − 1 [ j ] h_i^{-1}[j] h i − 1 [ j ] [ n ] [n] [ n ] j j j
h i − 1 [ j ] ≐ { t ∈ [ n ] : h ( t ) = j } .
h_i^{-1}[j] \doteq \{ t \in [n] : h(t) = j \}.
h i − 1 [ j ] ≐ { t ∈ [ n ] : h ( t ) = j } . Once h i h_i h i
M [ i , j ] = ∑ t ∈ h i − 1 [ j ] g i ( t ) ⋅ f t .
M[i, j] = \sum_{ t \in h_i^{-1}[j] } g_i (t) \cdot f_t.
M [ i , j ] = t ∈ h i − 1 [ j ] ∑ g i ( t ) ⋅ f t . By linearity of expectation and four-wise independence of g i g_i g i
E g i [ ( M [ i , j ] ) 2 ] = ∑ t , t ′ ∈ h i − 1 [ j ] E g i [ g i ( t ) ⋅ g i ( t ) ] ⋅ f t ⋅ f t ′ .
\underset{g_i}{ \mathbb{E} }[ (M[i, j])^2 ] = \sum_{ t, t' \in h_i^{-1}[j] } \underset{g_i}{ \mathbb{E} } [ g_i (t) \cdot g_i (t) ] \cdot f_t \cdot f_{t'}.
g i E [( M [ i , j ] ) 2 ] = t , t ′ ∈ h i − 1 [ j ] ∑ g i E [ g i ( t ) ⋅ g i ( t )] ⋅ f t ⋅ f t ′ . It holds that
E g i [ g i ( t ) ⋅ g i ( t ) ] = { 1 , if t = t ′ , 0 , otherwise .
\underset{g_i}{ \mathbb{E} } [ g_i (t) \cdot g_i (t) ] =
\begin{cases}
1, & \text{ if } t = t', \\
0, & \text{ otherwise }.
\end{cases}
g i E [ g i ( t ) ⋅ g i ( t )] = { 1 , 0 , if t = t ′ , otherwise . Therefore, E g i [ ( M [ i , j ] ) 2 ] = ∑ t ∈ h i − 1 [ j ] f t 2 \underset{g_i}{ \mathbb{E} }[ (M[i, j])^2 ] = \sum_{ t \in h_i^{-1}[j] } f_t^2 g i E [( M [ i , j ] ) 2 ] = ∑ t ∈ h i − 1 [ j ] f t 2
Remark. This is a rather deep result, which says that whatever elements are hashed to bucket j j j E g [ ( M [ i , j ] ) 2 ] \underset{g}{ \mathbb{E} } [ (M[i,j] )^2 ] g E [( M [ i , j ] ) 2 ]
By linearity of expectation, when h i h_i h i
E g [ a i 2 ] = ∑ j ∈ [ m ] E g [ ( M [ i , j ] ) 2 ] = ∑ j ∈ [ m ] ∑ t ∈ h i − 1 [ j ] f t 2 = ∥ f ∥ 2 2 .
\underset{g}{ \mathbb{E} } [ a_i^2 ] = \sum_{j \in [m] } \underset{g}{ \mathbb{E} } [ (M[i,j])^2 ] = \sum_{j \in [m] } \sum_{ t \in h_i^{-1}[j] } f_t^2 = \Vert f \Vert_2^2.
g E [ a i 2 ] = j ∈ [ m ] ∑ g E [( M [ i , j ] ) 2 ] = j ∈ [ m ] ∑ t ∈ h i − 1 [ j ] ∑ f t 2 = ∥ f ∥ 2 2 . It follows that E h [ E g [ a i 2 ] ] = ∥ f ∥ 2 2 \underset{h}{ \mathbb{E} } \left[ \underset{g}{ \mathbb{E} } [ a_i^2 ] \right] = \Vert f \Vert_2^2 h E [ g E [ a i 2 ] ] = ∥ f ∥ 2 2
Remark. The proof holds even for m = 1 m = 1 m = 1 ∥ f ∥ 2 2 \Vert f \Vert_2^2 ∥ f ∥ 2 2
□ \square □
Theorem 2. V a r [ a i 2 ] = ∥ x ∥ 2 4 m \mathbb{Var}[ a_i^2 ] = \frac{\Vert x \Vert_2^4 }{ m } V a r [ a i 2 ] = m ∥ x ∥ 2 4
Proof.
∀ t ∈ [ n ] \forall t \in [n] ∀ t ∈ [ n ] X t ≐ g i ( t ) ⋅ x t X_t \doteq g_i(t) \cdot x_t X t ≐ g i ( t ) ⋅ x t
∀ t ∈ [ n ] , j ∈ [ m ] \forall t \in [n], j \in [m] ∀ t ∈ [ n ] , j ∈ [ m ] Y t , j ≐ 1 [ h i [ t ] = j ] ⋅ X t Y_{t, j} \doteq \mathbb{1}[ h_i[t] = j ] \cdot X_t Y t , j ≐ 1 [ h i [ t ] = j ] ⋅ X t
M [ i , j ] = ∑ t ∈ [ n ] Y t , j ,
M[i,j] = \sum_{t \in [n] } Y_{t, j},
M [ i , j ] = t ∈ [ n ] ∑ Y t , j , and hence
V a r [ a i 2 ] = V a r [ ∑ j ∈ [ m ] ( M [ i , j ] ) 2 ] = V a r [ ∑ j ∈ [ m ] ( ∑ t ∈ [ n ] Y t , j ) 2 ] = V a r [ ∑ j ∈ [ m ] ∑ t , t ′ ∈ [ n ] Y t , j Y t ′ , j ] = V a r [ ∑ t , t ′ ∈ [ n ] ∑ j ∈ [ m ] Y t , j Y t ′ , j ] = V a r [ ∑ t , t ′ ∈ [ n ] ( ∑ j ∈ [ m ] 1 [ h i [ t ] = j ] ⋅ 1 [ h i [ t ′ ] = j ] ) ⋅ X t ⋅ X t ′ ] = V a r [ ∑ t , t ′ ∈ [ n ] 1 [ h i [ t ] = h i [ t ′ ] ] ⋅ X t ⋅ X t ′ ] = V a r [ ∑ t ∈ [ n ] f t 2 + ∑ t ≠ t ′ ∈ [ n ] 1 [ h i [ t ] = h i [ t ′ ] ] ⋅ X t ⋅ X t ′ ] = V a r [ ∑ t ≠ t ′ ∈ [ n ] 1 [ h i [ t ] = h i [ t ′ ] ] ⋅ X t ⋅ X t ′ ]
\begin{aligned}
\mathbb{Var}[a_i^2]
&= \mathbb{Var} \left[ \sum_{j \in [m] } (M[i, j])^2 \right] \\
&= \mathbb{Var} \left[ \sum_{j \in [m] } \left( \sum_{t \in [n] } Y_{t, j} \right)^2 \right] \\
&= \mathbb{Var} \left[ \sum_{j \in [m] } \sum_{t, t' \in [n]} Y_{t, j} Y_{t', j} \right] \\
&= \mathbb{Var} \left[ \sum_{t, t' \in [n]} \sum_{j \in [m] } Y_{t, j} Y_{t', j} \right] \\
&= \mathbb{Var} \left[ \sum_{t, t' \in [n]} \left( \sum_{j \in [m] } \mathbb{1}[ h_i[t] = j ] \cdot \mathbb{1}[ h_i[t'] = j ] \right) \cdot X_t \cdot X_{t'} \right] \\
&= \mathbb{Var} \left[ \sum_{t, t' \in [n]} \mathbb{1}[ h_i[t] = h_i[t'] ] \cdot X_t \cdot X_{t'} \right] \\
&= \mathbb{Var} \left[ \sum_{t \in [n] } f_t^2 + \sum_{t \neq t' \in [n]} \mathbb{1}[ h_i[t] = h_i[t'] ] \cdot X_t \cdot X_{t'} \right] \\
&= \mathbb{Var} \left[ \sum_{t \neq t' \in [n]} \mathbb{1}[ h_i[t] = h_i[t'] ] \cdot X_t \cdot X_{t'} \right]
\end{aligned}
V a r [ a i 2 ] = V a r j ∈ [ m ] ∑ ( M [ i , j ] ) 2 = V a r j ∈ [ m ] ∑ t ∈ [ n ] ∑ Y t , j 2 = V a r j ∈ [ m ] ∑ t , t ′ ∈ [ n ] ∑ Y t , j Y t ′ , j = V a r t , t ′ ∈ [ n ] ∑ j ∈ [ m ] ∑ Y t , j Y t ′ , j = V a r t , t ′ ∈ [ n ] ∑ j ∈ [ m ] ∑ 1 [ h i [ t ] = j ] ⋅ 1 [ h i [ t ′ ] = j ] ⋅ X t ⋅ X t ′ = V a r t , t ′ ∈ [ n ] ∑ 1 [ h i [ t ] = h i [ t ′ ]] ⋅ X t ⋅ X t ′ = V a r t ∈ [ n ] ∑ f t 2 + t = t ′ ∈ [ n ] ∑ 1 [ h i [ t ] = h i [ t ′ ]] ⋅ X t ⋅ X t ′ = V a r t = t ′ ∈ [ n ] ∑ 1 [ h i [ t ] = h i [ t ′ ]] ⋅ X t ⋅ X t ′ For t ≠ t ′ ∈ [ n ] t \neq t' \in [n] t = t ′ ∈ [ n ] Z t , t ′ = 1 [ h i [ t ] = h i [ t ′ ] ] ⋅ X t ⋅ X t ′ Z_{t, t'} = \mathbb{1}[ h_i[t] = h_i[t'] ] \cdot X_t \cdot X_{t'} Z t , t ′ = 1 [ h i [ t ] = h i [ t ′ ]] ⋅ X t ⋅ X t ′
E [ Z t , t ′ ] = E [ 1 [ h i [ t ] = h i [ t ′ ] ] ] ⋅ E [ X t ] ⋅ E [ x t ′ ] = 0.
\mathbb{E}[ Z_{t, t'} ] = \mathbb{E}[ \mathbb{1}[ h_i[t] = h_i[t'] ] ] \cdot \mathbb{E}[ X_t ] \cdot \mathbb{E}[ x_{t'} ] = 0.
E [ Z t , t ′ ] = E [ 1 [ h i [ t ] = h i [ t ′ ]]] ⋅ E [ X t ] ⋅ E [ x t ′ ] = 0. Consider t < t ′ ∈ [ n ] t < t' \in [n] t < t ′ ∈ [ n ] s < s ′ ∈ [ n ] s < s' \in [n] s < s ′ ∈ [ n ] ( t , t ′ ) ≠ ( s , s ′ ) (t, t') \neq (s, s') ( t , t ′ ) = ( s , s ′ ) t ≠ s t \neq s t = s t ′ ≠ s ′ t' \neq s' t ′ = s ′ t t t
Z t , t ′ Z s , s ′ = X t ⋅ ( X t ′ ⋅ X s ⋅ X s ′ ⋅ 1 [ h i [ t ] = h i [ t ′ ] ] ⋅ 1 [ h i [ s ] = h i [ s ′ ] ] ) .
Z_{t, t'} Z_{s, s'}
= X_t \cdot \left( X_{t'} \cdot X_s \cdot X_{s'} \cdot \mathbb{1}[ h_i[t] = h_i[t'] ] \cdot \mathbb{1}[ h_i[s] = h_i[s'] ] \right).
Z t , t ′ Z s , s ′ = X t ⋅ ( X t ′ ⋅ X s ⋅ X s ′ ⋅ 1 [ h i [ t ] = h i [ t ′ ]] ⋅ 1 [ h i [ s ] = h i [ s ′ ]] ) . As g i g_i g i t ≠ t ′ t \neq t' t = t ′ t ≠ s t \neq s t = s t ≠ s ′ t \neq s' t = s ′ g i ( t ) g_i(t) g i ( t ) ( g i ( t ′ ) ⋅ g i ( s ) ⋅ g i ( s ′ ) ⋅ 1 [ h i [ t ] = h i [ t ′ ] ] ⋅ 1 [ h i [ s ] = h i [ s ′ ] ] ) \left( g_i(t') \cdot g_i(s) \cdot g_i(s') \cdot \mathbb{1}[ h_i[t] = h_i[t'] ] \cdot \mathbb{1}[ h_i[s] = h_i[s'] ] \right) ( g i ( t ′ ) ⋅ g i ( s ) ⋅ g i ( s ′ ) ⋅ 1 [ h i [ t ] = h i [ t ′ ]] ⋅ 1 [ h i [ s ] = h i [ s ′ ]] )
E [ Z t , t ′ Z s , s ′ ] = 0.
\mathbb{E}[ Z_{t, t'} Z_{s, s'}] = 0.
E [ Z t , t ′ Z s , s ′ ] = 0. Therefore,
V a r [ ∑ t ≠ t ′ ∈ [ n ] Z t , t ′ ] = E [ ( ∑ t ≠ t ′ ∈ [ n ] Z t , t ′ ) 2 ] = E [ ∑ t ≠ t ′ ∈ [ n ] Z t , t ′ 2 ] = ∑ t ≠ t ′ ∈ [ n ] x t 2 x t ′ 2 m = ∥ x ∥ 2 4 m .
\begin{aligned}
\mathbb{Var} \left[ \sum_{t \neq t' \in [n]} Z_{t, t'} \right]
&= \mathbb{E} \left[ \left( \sum_{t \neq t' \in [n]} Z_{t, t'} \right)^2 \right] \\
&= \mathbb{E} \left[ \sum_{t \neq t' \in [n]} Z_{t, t'}^2 \right] \\
&= \sum_{t \neq t' \in [n]} \frac{ x_t^2 x_{t'}^2}{ m } \\
&= \frac{\Vert x \Vert_2^4 }{ m }.
\end{aligned}
V a r t = t ′ ∈ [ n ] ∑ Z t , t ′ = E t = t ′ ∈ [ n ] ∑ Z t , t ′ 2 = E t = t ′ ∈ [ n ] ∑ Z t , t ′ 2 = t = t ′ ∈ [ n ] ∑ m x t 2 x t ′ 2 = m ∥ x ∥ 2 4 . □ \square □
∀ i ∈ [ k ] , Pr [ ∣ a i 2 − ∥ x ∥ 2 2 ∣ ≥ ϵ ∥ x ∥ 2 2 ] ≤ 1 3 \forall i \in [k], \Pr [ | a_i^2 - \Vert x \Vert_2^2 | \ge \epsilon \Vert x \Vert_2^2] \le \frac{1}{3} ∀ i ∈ [ k ] , Pr [ ∣ a i 2 − ∥ x ∥ 2 2 ∣ ≥ ϵ ∥ x ∥ 2 2 ] ≤ 3 1
Proof. By Chebyshev's inequality.
□ \square □
Pr [ ∣ { i ∈ [ k ] : Pr [ ∣ a i 2 − ∥ x ∥ 2 2 ∣ ≤ ϵ ∥ x ∥ 2 2 ] } ∣ > k 2 ] ≥ 1 − δ \Pr \left[ \left| \{ i \in [k] : \Pr [ | a_i^2 - \Vert x \Vert_2^2 | \le \epsilon \Vert x \Vert_2^2] \} \right| > \frac{k}{2} \right] \ge 1 - \delta Pr [ { i ∈ [ k ] : Pr [ ∣ a i 2 − ∥ x ∥ 2 2 ∣ ≤ ϵ ∥ x ∥ 2 2 ]} > 2 k ] ≥ 1 − δ
Proof. By Chernoff bound.
□ \square □
Reference
[1] G. Cormode and K. Yi, Small Summaries for Big Data, 1st ed. Cambridge University Press, 2020.
← Back to all notes Back to top ↑