Proof:
The same proof as for \(L_1\)  sampling holds except for computing exactly the norm \(\Vert \mathbf {w}_u^k\Vert _2\) . Instead we will estimate it using CountSketch [1]}. This is a linear data structure that maintains an array with counters. The critical property of linear sketches is that for each node it holds
\(sketch(\sum _{v \in N_k(u)} \mathbf {f}_v) = \sum _{v \in N_k(u)} sketch(\mathbf {f}_v)\) 
