Count Sketch

Count sketch is a type of dimensionality reduction that is particularly efficient in statistics, machine learning and algorithms.
It was invented by
Moses Charikar, Kevin Chen and Martin Farach-Colton in an effort to speed up the AMS Sketch by Alon, Matias and Szegedy for approximating the frequency moments of streams.

The sketch is nearly identical to the Feature hashing algorithm by John Moody, but differs in its use of hash functions with low dependence, which makes it more practical.
In order to still have a high probability of success, the median trick is used to aggregate multiple count sketches, rather than the mean.

These properties allow use for explicit kernel methods, bilinear pooling in neural networks and is a cornerstone in many numerical linear algebra algorithms.Woodruff, David P. "Sketching as a Tool for Numerical Linear Algebra." Theoretical Computer Science 10.1-2 (2014): 1–157.

Mathematical definition

1. For constants $w$ and $t$ (to be defined later) independently choose $d=2t+1$ random hash functions
$h_1, \dots, h_d$ and $s_1,\dots,s_d$ such that
h_i : \to /math> and
s_i : \to \.
It is necessary that the hash families from which $h_i$ and $s_i$ are chosen be pairwise independent.

2. For each item $q_i$ in the stream, add $s_j(q_i)$ to the $h_j(q_i)$th bucket of the $j$th hash.

At the end of this process, one has $wd$ sums $(C_)$ where
:$C_ = \sum_s_i(k).$

To estimate the count of $q$s one computes the following value:
:$r_q = \text_^d\, s_i(q)\cdot C_.$

The values $s_i(q)\cdot C_$ are unbiased estimates of how many times $q$ has appeared in the stream.

The estimate $r_q$ has variance $O(\mathrm\)$, where
$m_1$ is the length of the stream and $m_2^2$ is \sum_q (\sum_i _i=q^2.

Furthermore, $r_q$ is guaranteed to never be more than $2m_2/\sqrt$ off from the true value, with probability $1-e^$.

Vector formulation

Alternatively Count-Sketch can be seen as a linear mapping with a non-linear reconstruction function.
Let $M^\in\^$, be a collection of $d=2t+1$ matrices, defined by
:$M^_ = s_i(j)$
for j\in /math> and 0 everywhere else.

Then a vector $v\in\mathbb^n$ is sketched by $C^ = M^ v \in \mathbb^w$.
To reconstruct $v$ we take $v^*_j = \text_i C^_j s_i(j)$.
This gives the same guarantees as stated above, if we take $m_1=\, v\, _1$ and $m_2=\, v\, _2$.

Relation to Tensor sketch

The count sketch projection of the outer product of two vectors is equivalent to the convolution of two component count sketches.

The count sketch computes a vector convolution

$C^x \ast C^x^T$, where $C^$ and $C^$ are independent count sketch matrices.

Pham and Pagh
show that this equals $C(x \otimes x^T)$ – a count sketch $C$ of the outer product of vectors, where $\otimes$ denotes Kronecker product.

The fast Fourier transform can be used to do fast convolution of count sketches.
By using the face-splitting product such structures can be computed much faster than normal matrices.

See also

* Count–min sketch
* Tensorsketch

References

Further reading

*Faisal M. Algashaam; Kien Nguyen; Mohamed Alkanhal; Vinod Chandran; Wageeh Boles. "Multispectral Periocular Classification WithMultimodal Compact Multi-Linear Pooling

''IEEE Access'', Vol. 5. 2017.
*{{Cite web , last1=Ahle , first1=Thomas , last2=Knudsen , first2=Jakob , date=2019-09-03 , title=Almost Optimal Tensor Sketch , url=https://www.researchgate.net/publication/335617805 , access-date=2020-07-11 , website=ResearchGate

Dimension reduction