Max Home IndustryБольшинство нематематиков могут подумать, что тензорные операции довольно сложны без каких-либо формальных доказательств, но новые результаты доказывают, что они NP Hard, что не является хорошей новостью, если вы пытаетесь что-то решить, используя их.
Тензор — это n-мерное обобщение матрицы. Матрица — это двумерный тензор, состоящий из строк и столбцов. Трехмерный тензор — это куб чисел со строками, столбцами и срезами. В матрице числа индексируются двумя переменными, например что-то вроде aij; в тензоре количество индексируемых переменных может быть больше двух, например aijk для тензора размерности или, точнее, ранга 3.
Мы очень часто используем матричную алгебру и матричные численные методы практически в любой числовой программе — это основа практически всей нашей обработки чисел. Мы решаем линейные системы уравнений, находим собственные значения, выполняем разложение по сингулярным числам и так далее. Некоторые программисты могут расценить это как сложную математику, но для большинства этих задач у нас есть алгоритмы с полиномиальным временем. То есть векторные и матричные вычисления выполняются в P.
Тензорная алгебра обобщает линейную алгебру, с которой мы все знакомы, на более высокие измерения — полилинейную алгебру. Это проявляется в продвинутой геометрии, теории гравитации — общей теории относительности, то есть численной механике и так далее. Он также используется в искусственном интеллекте и компьютерном зрении, а также в ряде передовых подходов ко всем видам тем. В тензорной алгебре хорошо то, что с алгоритмической точки зрения в ней нет ничего нового — в большинстве случаев нужно справиться лишь с несколькими индексами.
Конечно, алгоритмы, с которыми нам нужно работать, скажем, с тензорами 3-го ранга не сложнее, чем с тензорами 2-го ранга, то есть с матрицами? Он должен быть в P — верно?
Ну нет.
Согласно недавней статье, с тензорами 3-го ранга дела обстоят намного хуже. Кажется, что они отмечают разделительную линию между линейными выпуклыми задачами, которые можно решить, и более сложным нелинейным невыпуклым классом. В статье показано, что целый список обобщений решаемых матричных задач NP-труден в их формулировках ранга 3. К ним относятся поиск собственных значений, нахождение приближенных собственных значений, симметричных собственных значений, сингулярных значений, доказательство положительной определенности, аппроксимация тензора тензорами ранга 1 и т. Д. Есть даже упоминание об обобщенном вопросе о поиске матричной функции, которая оказывается неразрешимой для любого тензора 20x20x2 или больше. Это большой сюрприз, потому что эквивалентную матричную функцию можно легко найти, и еще один намек на то, что добавление всего одного дополнительного индекса к матричной проблеме значительно усложняет задачу. Как сказано в названии статьи, большинство тензорных задач NP-трудны.
Стоит ли отказываться от тензорных методов, потому что большинство из них не в P?
Вы должны иметь в виду, что такие виды анализа справедливы только асимптотически, когда размер тензора n в тензоре n x n x n становится очень большим. Вполне возможно, что для диапазона малых n мы сможем найти алгоритмы, которые выполнят работу в разумные сроки. Тот факт, что проблема NP-сложная, не означает, что она невозможна!
Работа завершается некоторыми открытыми вопросами, и, если вы разумны в математике, вам будет интересно ее прочитать.