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

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

Особенности

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

$𝐚\otimes {𝐛}^{𝐓}\to \left[\begin{array}{c}{a}_1\\ a_2\\ a_3\\ a_4\end{array}\right]\left[\begin{array}{ccc}{b}_1& b_2& b_3\end{array}\right]=\left[\begin{array}{ccc}{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{array}\right]$,

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

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

$C(x\otimes x^T)$

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

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

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

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