Тензорний скетч () — метод зменшення розмірності, що використовується у статистиці, машинному навчанні та алгоритмах обробки великих даних . Він особливо ефективний стосовно векторів з тензорною структурою. Тензорний скетч може бути використаний для прискорення білінійного поєднання в нейронних мережах і застосовується у багатьох алгоритмах чисельної лінійної алгебриWoodruff, David P. «Sketching as a Tool for Numerical Linear Algebra.» Theoretical Computer Science 10.1-2 (2014): 1–157..
Історія Термін тензорний скетч (ескіз) був придуманий у 2013 році й описаний як метод того ж року Расмусом Пегом.
Спочатку відповідний метод спирався на використання швидкого перетворення Фур'є, щоб зробити швидку згортку. Пізніші науково-дослідні роботи узагальнили його до значно більшого класу методів зменшення розмірності за допомогою випадкових тензорних проєкцій.
Тензорні проєкції В основі одного з ефективних варіантів тензорного скетча лежить використання торцевого добутку матриць, запропонованого Слюсарем В. І.Anna Esteve, Eva Boj & Josep Fortiana (2009): Interaction Terms in Distance-Based Regression, Communications in Statistics — Theory and Methods, 38:19, P. 3501 в 1996 р. ().
Торцевий добуток двох матриць з однаковою кількістю рядків та позначається і має вид:
Доцільність використання цього добутку полягає у його властивості:
де — поелементний добуток Адамара.
На цій основі довільний тензорний скетч виду можливо подати як , де матриці та мають менший розмір, і . Оскільки операції матрично-векторних добутків і обчислюються за лінійним часом та відповідно, перехід до представлення дозволяє виконати множення на вектори тензорної структури набагато швидше, чим формується вихідний вираз , а саме за час .
Для тензорів більш високого порядку, наприклад, , економія буде ще більш значною.
Подібне перетворення задовольняє лемі Джонсона-Лінденштрауса про малі викривлення вихідних даних великої розмірності.
Див. також Лема Джонсона-Лінденштрауса Торцевий добуток Відліковий скетч
Примітки