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

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

Особенности

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

${\displaystyle \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}}}$,

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

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

${\displaystyle C(x\otimes x^{T})}$^[4]

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

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

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

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