Złożoność rangi Tensor nad nieskończonym polem

Napinacz jest uogólnieniem wektorów i matryc do większych rozmiarów i stopnia z tensora uogólnia również rzędu macierzy. Mianowicie, ranga tensora jest minimalna liczba rangi jeden tensory tej kwoty . Wektor i macierz są odpowiednio tensorami stopnia 1 i 2. $T$ $T$

Elementy w pochodzą z pola . Jeśli jest skończony, to Håstad udowodnił, że decyzja, czy stopień tensora stopnia 3 jest co najwyżej jest NP-zupełny, ale kiedy jest polem nieskończonym, jak racjonalne , nie podaje (ani cytuje) żadnej górnej granicy. $T$ $\mathbb{F}$ $\mathbb{F}$ $r$ $\mathbb{F}$ $\mathbb{Q}$

Pytanie: Co to jest najlepiej znana górna granica dla złożoności decydując jeśli ranga stopnia 3 tensor nad jest co najwyżej ? $T$ $\mathbb{Q}$ $r$

ds.algorithms reference-request computability tensor-rank Tyson Williams
źródło

Czy ranga tensora stopnia ponad ℚ jest taka sama, jak ranga tego samego tensora ponad ℝ? Jeśli tak, problem można sformułować jako szczególny przypadek egzystencjalnej teorii rzeczywistości i dlatego leży on w PSPACE.

Tsuyoshi Ito

Pomysł w moim poprzednim komentarzu nie zadziała, ponieważ ranga tensora stopnia trzeciego nad ℚ jest czasem różna od rangi tego samego tensora ponad ℝ. Niech {x, y} będzie podstawą dwuwymiarowej przestrzeni wektorowej i rozważmy tensor 2x⊗x⊗x + x⊗y⊗y + y⊗x⊗y + y⊗y⊗x. Nietrudno dostrzec, że jego ranga nad ℝ wynosi dwa, ale ranga nad ℚ jest większa niż dwa. (Ten przykład uzyskano przez zmodyfikowanie przykładu pokazującego, że ranga nad ℝ może różnić się od rangi nad ℂ w Kruskal 1989. )

Tsuyoshi Ito

@Tsuyoshi Ito Całkowicie się zgadzam. Nie mogę też znaleźć żadnej górnej granicy.

Tyson Williams,

Myślę, że lepiej jest zapytać o obliczalność przed złożonością.

Tsuyoshi Ito

Trywialne górne ograniczenie polega na tym, że to Håstad również udowadnia w tym samym artykule, że problemem jest ponad . Poniższy bardziej ogólny problem jest CE-kompletna: podany częściowo wypełnione tensor, czy istnieje zakończenie tego, który ma rangę ?

N P - h a r d

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

Q

$\mathbb{Q}$

\leq r

$\leq r$

Kaveh

Odpowiedzi:

Jest na ten temat niedawny przedruk: http://galton.uchicago.edu/~lekheng/work/np.pdf . To pokazuje, że większość problemów związanych z rangami z tensorami są trudne NP w i . (Wspomina również, że decydowanie o randze w stosunku do jest NP trudne). $\mathbb{R}$ $\mathbb{C}$ $\mathbb{Q}$

Bart
źródło

Bart, ten przedruk (autorstwa Hillar i Lim) jest wspaniały ... bardzo dziękuję.

John Sidles,

Miły. Jednak nie rozumiem tego zdania: „Chociaż wynik Håstad dotyczy i , te wybory pól nie mają sensu dla wszystkich z wyjątkiem jednego z powyższych problemów (wyjątek stanowi bilinearny układ równań), ponieważ są to problemy analityczne dobrze zdefiniowane tylko w pełnym polu charakterystyki o wartości bezwzględnej 0. Wśród takich pól i są zdecydowanie najbardziej powszechne w aplikacjach i dlatego ograniczymy nasze dyskusje do tych dziedzin ”.

Q

$\mathbb{Q}$

F_{q}

$\mathbb{F}_q$

R

$\mathbb{R}$

C

$\mathbb{C}$

Tyson Williams,

Jednym z problemów przywołanych w powyższym cytacie jest ranga. Czy ci autorzy twierdzą, że ranga tensora nie jest dobrze zdefiniowana w stosunku do ?

Q

$\mathbb{Q}$

Tyson Williams,

@Tyson: Myślę, że autorzy chcą tylko powiedzieć, że dla wielu zastosowań numerycznych (równania różniczkowe cząstkowe, przetwarzanie sygnałów), chcesz wykonywać obliczenia w lub . Będąc analitykiem numerycznym, nie widzę wielu aplikacji zdefiniowanych w . Nie sugerują, że ranga nie jest dobrze zdefiniowana na .

R

$\mathbb{R}$

C

$\mathbb{C}$

Q

$\mathbb{Q}$

Q

$\mathbb{Q}$

Bart

Chociaż to była naprawdę jedyna odpowiedź (ponieważ John chciał, aby był komentarzem), nadal uważam, że ta odpowiedź zasługuje na nagrodę, ponieważ zawierała odniesienie, które pokazało twardość w stosunku do innych ważnych nieskończonych dziedzin (reali i kompleksów). Jak sugeruje tytuł mojego pytania, ogólnie jestem ciekawy nieskończonych dziedzin, ale postanowiłem zapytać o racjonalność, aby uzyskać pytanie z konkretną odpowiedzią. Nadal wybiorę inne pytanie jako zaakceptowaną odpowiedź, jeśli ktoś może podać górną granicę (lub pokazać, że jest to niemożliwe do obliczenia).

Tyson Williams,

Książka Perspectives in Computational Complexity: The Somenath Biswas Anniversary Volume opublikowana tego lata (lipiec 2014 r.) W dużej mierze zgadza się z konsensusem, który tutaj osiągnęliśmy. Na stronie 199 jest napisane:

Według mojej najlepszej wiedzy nawet nie wiadomo, czy [problem obliczania rangi tensora] w stosunku do jest rozstrzygalny. W przypadku sytuacja jest nieco lepsza ... Problem jest rozstrzygalny, a nawet w PSPACE, ponieważ można go sprowadzić do egzystencjalnej teorii rzeczywistości. $\mathbb{Q}$ $\mathbb{R}$

Tyson Williams
źródło

Niedawny przedruk również to potwierdza: arxiv.org/pdf/1612.04338v1.pdf . (Patrz tabela na stronie 3.)

Huck Bennett,

Uwaga: poniższy tekst miał być komentarzem… zdecydowanie nie jest odpowiedzią, ale raczej pragmatyczną obserwacją, która powstała w wyniku powtórzenia zasad rezonansu magnetycznego Charliego Slichtera w języku geometrii symplektycznej i teorii informacji kwantowej (która odsuwa się naturalnie na wielomianowe szeregi stanów produktu-tensora). Obecnie mamy częściowe geometryczne zrozumienie tych metod rangi tensorowej, marginalne zrozumienie kwantowe informatyczne, zasadniczo brak zrozumienia teoretycznego czy złożonościowego, oraz działające (ale w dużej mierze empiryczne) zrozumienie obliczeniowe.

Jesteśmy bardzo zainteresowani poszerzeniem, pogłębieniem i ujednoliceniem tego zrozumienia, dlatego mamy nadzieję, że inni ludzie opublikują dalsze odpowiedzi / komentarze na ten temat.

Z naszych praktycznych doświadczeń obliczeniowych wynika, że szacowanie rangi nad jest ogólnie możliwe do zastosowania metodami najbardziej stromego zejścia ... jak rozumiemy, ta solidność powstaje z geometrycznego powodu, mianowicie z holomorficznego twierdzenia o dwuwymiarowej krzywiźnie Goldberga i Kobayashiego . Jest to dalekie od rygorystycznego dowodu, nie trzeba dodawać.

C

$\mathbb{C}$

John Sidles
źródło

Czy to twierdzenie jest łatwe do stwierdzenia? Jeśli nie, czy możesz podać link do dobrego oświadczenia i wyjaśnienia?

Tyson Williams,

@Tyson: Myślę, że John mówi o swoim doświadczeniu w rozwiązywaniu problemów, a nie o twierdzeniu.

Joe Fitzsimons,

Zapytałeś go o twierdzenie, a on chyba o nim nie mówi. Myślałem, że go źle zrozumiałeś.

Joe Fitzsimons,

Właściwie myślałem, że opublikowałem komentarz i byłem zaskoczony, widząc, że pojawia się jako odpowiedź. Doh! Właśnie go edytowałem, aby dodać odniesienie, ale nadal jest bardzo daleka od zadowalającej odpowiedzi. Dobre pytanie Tysona Williamsa! :)

John Sidles,

@Joe Wspomniał o holomorficznym twierdzeniu o dwuwymiarowej krzywiźnie Goldberga i Kobayashiego, więc zapytałem go o to. Nie jestem jednak pewien, czy to oznacza, że go źle zrozumiałem, czy nie.

Tyson Williams,