Дискретное преобразование Фурье (ДПФ) — это абсолютный фундамент всей современной цифровой эры. Оно позволяет разложить любой сигнал (звук, изображение, радиоволну) на гармонические составляющие (спектр). С точки зрения линейной алгебры, ДПФ является не чем иным, как умножением вектора сигнала на квадратную матрицу Вандермонда, заполненную комплексными корнями из единицы. Однако прямое умножение вектора на плотную матрицу размера n на n требует O(n^2) арифметических операций. Для обработки аудиосигнала с частотой 44100 Гц компьютеру потребовались бы миллиарды вычислений в секунду, что сделало бы MP3 и стриминг невозможными. Изящное решение — алгоритм Быстрого преобразования Фурье (БПФ), алгебраическая структура которого основана на факторизации матриц.

Когда мы переходим от двумерных матриц к многомерным массивам чисел — тензорам, мы сталкиваемся с жестоким математическим феноменом, известным как «проклятие размерности». Если тензор имеет d измерений (мод), и по каждому измерению длина равна n, то общее количество элементов в нем составляет n^d. При n=10 и d=20 объем тензора превышает вместимость всех жестких дисков на планете. В физике квантовых многочастичных систем и при решении уравнений в частных производных высоких размерностей этот барьер казался непреодолимым. В 2011 году российский математик Иван Оселедец предложил блестящий формат разложения многомерных массивов — Тензорный поезд (Tensor Train, TT), который свел экспоненциальную сложность к полиномиальной, совершив революцию в многолинейной алгебре.

Традиционные алгоритмы вычислительной линейной алгебры (такие как сингулярное разложение или QR-факторизация) требуют кубического времени выполнения, что делает их абсолютно неприменимыми для обработки современных массивов данных петабайтного масштаба. В ответ на этот вызов математики создали совершенно новую парадигму — Рандомизированную вычислительную линейную алгебру (RandNLA). Вместо точных, детерминированных, но бесконечно долгих вычислений, этот подход использует законы теории вероятностей для нахождения потрясающе точных аппроксимаций за долю секунды. RandNLA лежит в основе алгоритмов машинного обучения корпоративного уровня, позволяя мгновенно сжимать матрицы, находить главные компоненты и решать переопределенные системы огромной размерности.