Отсчётный скетч

Отсчётный скетч (англ. Count sketch) — метод уменьшения размерности, используемый в статистике, машинном обучении и алгоритмах обработки больших данных. Может быть использован для ускорения ядерного метода и билинейного пулинга в нейронных сетях, а также в численных алгоритмах линейной алгебры.

Особенности

В отличие от тензорного скетча отсчётный скетч оперирует так называемым внешним произведением векторов:

$\mathbf {a} \otimes \mathbf {b^{T}} \rightarrow {\begin{bmatrix}a_{1}\\a_{2}\\a_{3}\\a_{4}\end{bmatrix}}{\begin{bmatrix}b_{1}&b_{2}&b_{3}\end{bmatrix}}={\begin{bmatrix}a_{1}b_{1}&a_{1}b_{2}&a_{1}b_{3}\\a_{2}b_{1}&a_{2}b_{2}&a_{2}b_{3}\\a_{3}b_{1}&a_{3}b_{2}&a_{3}b_{3}\\a_{4}b_{1}&a_{4}b_{2}&a_{4}b_{3}\end{bmatrix}}$,

где $\otimes$ означает произведение Кронекера.

Существенно, что отсчётный скетч от такого произведения двух векторов

$C(x\otimes x^{T})$

эквивалентен векторной свёртке

$C^{(1)}x\ast C^{(2)}x^{T}$,

гдe $C^{(1)}$ и $C^{(2)}$ являются независимыми матрицами.

Для сокращения вычислительных затрат на реализацию свёртки нескольких отсчётных скетчей может быть использовано быстрое преобразование Фурье.