Сложность тензорного ранга над бесконечным полем

Тензор является обобщение векторов и матриц на более высокие размеры и ранг тензора также обобщает ранг матрицы. А именно, ранг тензора является минимальным числом ранга один тензоров этой суммы . Вектор и матрица являются тензорами степени 1 и 2 соответственно. $T$ $T$

Элементы в происходят из поля . Если конечно, то Хостад доказал, что решение о том, является ли ранг тензора степени 3 не более , NP-полон, но когда является бесконечным полем, таким как рациональные числа он не дает (или цитирует) верхнюю границу. $T$ $\mathbb{F}$ $\mathbb{F}$ $r$ $\mathbb{F}$ $\mathbb{Q}$

Вопрос: Что является наиболее известной верхней оценкой сложности принятия решения , если ранг степени 3 тензор над не превосходит ? $T$ $\mathbb{Q}$ $r$

ds.algorithms reference-request computability tensor-rank Тайсон Уильямс
источник

Является ли ранг тензора степени три над same таким же, как ранг того же тензора над ℝ? Если это так, то проблема может быть сформулирована как частный случай экзистенциальной теории истин и поэтому лежит в PSPACE.

Цуёси Ито

Идея в моем предыдущем комментарии не будет работать, потому что ранг тензора степени три над sometimes иногда отличается от ранга того же тензора над ℝ. Пусть {x, y} - базис двумерного векторного пространства, и рассмотрим тензор 2x⊗x⊗x + x⊗y⊗y + y⊗x⊗y + y⊗y⊗x. Нетрудно видеть, что его ранг над ℝ равен двум, но его ранг над greater больше двух. (Этот пример был получен путем изменения примера, показывающего, что ранг над ℝ может отличаться от ранга над ℂ в Крускале в 1989 году .)

Цуёси Ито

@ Tsuyoshi Ito Я полностью согласен. Я также не могу найти верхнюю границу.

Тайсон Уильямс

Я думаю, что лучше спросить вычислимость, чем сложность.

Цуёси Ито

Тривиальный UpperBound является то , что се Håstad также доказывает , в той же статье , что проблема

над

. Следующая более общая задача является ce-полной: если есть частично заполненный тензор, есть ли его завершение с рангом

N P - h a r d

$\mathsf{NP\text{-}hard}$

Q

$\mathbb{Q}$

\leq r

$\leq r$

Каве

Ответы:

Существует недавний препринт по этому поводу: http://galton.uchicago.edu/~lekheng/work/np.pdf . Это показывает , что большинство ранга вопросов , связанный с тензорами NP трудно над и . (Также упоминается, что определение ранга над - трудный NP.) $\mathbb{R}$ $\mathbb{C}$ $\mathbb{Q}$

Барт
источник

Барт, этот препринт (Хиллар и Лим) потрясающий ... большое спасибо.

Джон Сидлес

Ницца. Тем не менее, я не понимаю это предложение: «Хотя результат Хостада относится к

, этот выбор полей не имеет смысла для всех, кроме одной из вышеперечисленных проблем (исключение составляет билинейная система уравнений), так как они аналитические задачи четко определены только для полного поля характеристики 0 с абсолютным значением. Среди таких полей

являются наиболее распространенными в приложениях, поэтому мы ограничимся нашими обсуждениями этими областями ».

Q

$\mathbb{Q}$

F_{q}

$\mathbb{F}_q$

R

$\mathbb{R}$

C

$\mathbb{C}$

Тайсон Уильямс

Одной из проблем, упомянутых в приведенной выше цитате, является ранг. Говорят ли эти авторы, что ранг тензора не определен над

Q

$\mathbb{Q}$

Тайсон Уильямс

@Tyson: Я думаю , что авторы просто хотят сказать , что для многих численных приложений (дифференциальных уравнений, обработки сигнала), что вы хотите сделать вычисление в

или

. Будучи числовым аналитиком себя, я не вижу много приложений , определенных на

. Они не означают , что ранг не корректно определен на

R

$\mathbb{R}$

C

$\mathbb{C}$

Q

$\mathbb{Q}$

Q

$\mathbb{Q}$

Барт

Хотя это был действительно единственный ответ (так как Джон имел в виду его, чтобы быть комментарием), я все еще считаю, что этот ответ заслуживает награды, так как он предоставил ссылку, которая показала твердость по другим важным бесконечным полям (действительным и комплексным). Как видно из названия моего вопроса, мне любопытно, что такое бесконечные поля, но я решил спросить об рациональных значениях, чтобы задать вопрос с конкретным ответом. Я по-прежнему выберу другой вопрос в качестве принятого ответа, если кто-то может указать верхнюю границу (или покажет, что она не вычислима).

Тайсон Уильямс

Книга « Перспективы в вычислительной сложности: Юбилейный том Somenath Biswas», опубликованный этим летом (июль 2014 года), в значительной степени согласуется с консенсусом, которого мы достигли здесь. На странице 199 написано:

Насколько мне известно, даже неизвестно, разрешима ли [проблема вычисления тензорного ранга] над Над ситуация несколько лучше ... Проблема разрешима и даже в PSPACE, поскольку ее можно свести к экзистенциальной теории действительных чисел. $\mathbb{Q}$ $\mathbb{R}$

Тайсон Уильямс
источник

Недавний препринт также подтверждает это: arxiv.org/pdf/1612.04338v1.pdf . (См. Таблицу на стр. 3.)

Гек Беннетт

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

Мы очень заинтересованы в расширении, углублении и объединении этого понимания, и поэтому мы надеемся, что другие люди будут публиковать дальнейшие ответы / комментарии по этому вопросу.

Наш практический вычислительный опыт показал, что оценка ранга над

в общем случае трактуется методами наискорейшего спуска ... как мы понимаем, эта робастность возникает по геометрической причине, а именно по теореме Голомберга и Кобаяши о голоморфной бисекционной кривизне. Это далеко от строгого доказательства, само собой разумеется.

C

$\mathbb{C}$

Джон Сидлес
источник

Легко ли сформулировать эту теорему? Если нет, можете ли вы дать ссылку на хорошее утверждение и объяснение?

Тайсон Уильямс

@ Тайсон: Я думаю, что Джон говорит о своем опыте решения проблем, а не о теореме.

Джо Фицсимонс

Вы спросили его о теореме, а он, похоже, не говорит об одной. Я просто думал, что вы его неправильно поняли.

Джо Фицсимонс

На самом деле, я думал, что разместил комментарий и был удивлен, увидев его в качестве ответа. Doh! Я только что отредактировал его, чтобы добавить ссылку, но все же это очень далеко от удовлетворительного ответа. Прекрасный вопрос от Тайсона Уильямса! :)

Джон Сидлес

@Joe Он упомянул теорему Голомберга и Кобаяси о голоморфной бисекционной кривизне, поэтому я спросил его об этом. Я не уверен, означает ли это, что я его неправильно понял или нет.

Тайсон Уильямс