Komplexität des Tensorrangs über ein unendliches Feld

Ein Tensor ist eine Verallgemeinerung von Vektoren und Matrizen auf höhere Dimensionen, und der Rang eines Tensors verallgemeinert auch den Rang einer Matrix. Der Rang eines Tensors ist nämlich die minimale Anzahl von Tensoren des Rangs 1, die sich zu summieren . Ein Vektor und eine Matrix sind Tensoren vom Grad 1 bzw. 2. $T$ $T$

Die Elemente in stammen aus einem Feld . Wenn endlich ist, dann hat Håstad bewiesen, dass die Entscheidung, ob der Rang eines Tensors 3. Grades höchstens ist, NP-vollständig ist, aber wenn ein unendliches Feld ist, wie die Rationen Er gibt (oder zitiert) keine Obergrenze. $T$ $\mathbb{F}$ $\mathbb{F}$ $r$ $\mathbb{F}$ $\mathbb{Q}$

Frage: Was ist die bekannteste Obergrenze für die Komplexität der Entscheidung, ob der Rang eines Tensors des Grades 3 über höchstens ? $T$ $\mathbb{Q}$ $r$

ds.algorithms reference-request computability tensor-rank Tyson Williams
quelle

Ist der Rang eines Tensors von Grad drei über ℚ der gleiche wie der Rang desselben Tensors über ℝ? In diesem Fall kann das Problem als Sonderfall der Existenztheorie der Realitäten formuliert werden und liegt daher in PSPACE.

Tsuyoshi Ito

Die Idee in meinem vorherigen Kommentar wird nicht funktionieren, weil sich der Rang eines Tensors um Grad drei über ℚ manchmal vom Rang desselben Tensors über ℝ unterscheidet. Sei {x, y} eine Basis eines zweidimensionalen Vektorraums und betrachte den Tensor 2x⊗x⊗x + x⊗y⊗y + y⊗x⊗y + y⊗y⊗x. Es ist nicht schwer zu erkennen, dass sein Rang über ℝ zwei ist, aber sein Rang über ℚ ist größer als zwei. (Dieses Beispiel wurde durch Modifizieren des Beispiels erhalten, das zeigt, dass der Rang über ℝ von dem Rang über ℂ in Kruskal 1989 abweichen kann .)

Tsuyoshi Ito

@ Tsuyoshi Ito Ich stimme vollkommen zu. Ich kann auch keine Obergrenze finden.

Tyson Williams

Ich denke, es ist besser, die Berechenbarkeit vor der Komplexität zu fragen.

Tsuyoshi Ito

Das Triviale ist, dass Håstad im selben Artikel auch nachweist, dass das Problem over . Das folgende allgemeinere Problem ist ce-vollständig: Gibt es bei einem teilweise gefüllten Tensor eine Vervollständigung, die den Rang ?

N P - h a r d

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

Q

$\mathbb{Q}$

\leq r

$\leq r$

Kaveh

Antworten:

Es gibt einen aktuellen Preprint dazu: http://galton.uchicago.edu/~lekheng/work/np.pdf . Es zeigt, dass die meisten Rank-bezogenen Probleme mit Tensoren NP-schwer über und . (Es wird auch erwähnt, dass es schwierig ist , den Rang über bestimmen .) $\mathbb{R}$ $\mathbb{C}$ $\mathbb{Q}$

Bart
quelle

Bart, dieser Preprint (von Hillar und Lim) ist großartig ... vielen Dank.

John Sidles

Nett. Ich verstehe diesen Satz jedoch nicht: "Während Håstads Ergebnis für

und

, ist diese Auswahl von Feldern nur für eines der oben genannten Probleme sinnvoll (mit Ausnahme des bilinearen Gleichungssystems) analytische Probleme, die nur über ein vollständiges Feld des Merkmals 0 mit einem absoluten Wert genau definiert sind. Unter diesen Feldern sind

und

bei weitem die häufigsten in Anwendungen, und daher werden wir unsere Erörterungen auf diese Felder beschränken. "

Q

$\mathbb{Q}$

F_{q}

$\mathbb{F}_q$

R

$\mathbb{R}$

C

$\mathbb{C}$

Tyson Williams

Eines der Probleme, auf die im obigen Zitat Bezug genommen wird, ist der Rang. Sagen diese Autoren, dass der Rang eines Tensors über

nicht genau definiert ist ?

Q

$\mathbb{Q}$

Tyson Williams

@Tyson: Ich denke, die Autoren möchten nur sagen, dass Sie für viele numerische Anwendungen (partielle Differentialgleichungen, Signalverarbeitung) Berechnungen in

oder

möchten . Da ich selbst ein numerischer Analyst bin, sehe ich nicht viele auf

definierte Anwendungen . Sie implizieren nicht, dass der Rang in

nicht gut definiert ist .

R

$\mathbb{R}$

C

$\mathbb{C}$

Q

$\mathbb{Q}$

Q

$\mathbb{Q}$

Bart

Obwohl dies wirklich die einzige Antwort war (da John meinte, er sei ein Kommentar), glaube ich immer noch, dass diese Antwort das Kopfgeld verdient, da sie eine Referenz darstellte, die Härte über die anderen wichtigen unendlichen Felder (Real und Komplexe) zeigte. Wie der Titel meiner Frage andeutet, bin ich auf unendliche Felder im Allgemeinen neugierig, habe mich jedoch entschlossen, nach den Begriffen zu fragen, um eine Frage mit einer bestimmten Antwort zu haben. Ich werde immer noch eine andere Frage als akzeptierte Antwort auswählen, wenn jemand eine Obergrenze angeben kann (oder zeigen kann, dass sie nicht berechenbar ist).

Tyson Williams

Das Buch Perspectives in Computational Complexity: The Somenath Biswas Anniversary Volume, das diesen Sommer (Juli 2014) veröffentlicht wurde, stimmt weitgehend mit dem Konsens überein, den wir hier erzielt haben. Auf Seite 199 heißt es:

Nach meinem besten Wissen ist sogar nicht bekannt, ob [das Problem der Berechnung des Tensorrangs] über entscheidbar ist. Über ist die Situation etwas besser ... Das Problem ist entscheidbar und sogar in PSPACE, da es auf die existentielle Theorie der Realitäten reduziert werden kann. $\mathbb{Q}$ $\mathbb{R}$

Tyson Williams
quelle

Ein aktueller Preprint bestätigt dies ebenfalls: arxiv.org/pdf/1612.04338v1.pdf . (Siehe Tabelle auf Seite 3.)

Huck Bennett

Anmerkung: Der folgende Text war als Kommentar gedacht… er ist definitiv keine Antwort, sondern eine pragmatische Beobachtung, die sich aus einer Neuformulierung von Charlie Slichters Prinzipien der Magnetresonanz in der Sprache der symplektischen Geometrie und der Quanteninformationstheorie (die sich zurückzieht) ergibt natürlich auf polynomrangige Tensorprodukt-Zustandsräume). Gegenwärtig haben wir ein partielles geometrisches Verständnis dieser Tensor-Rank-Methoden, ein minimales quanteninformatisches Verständnis, im Wesentlichen kein komplexitätstheoretisches oder kombinatorisches Verständnis und ein funktionierendes (aber weitgehend empirisches) rechnerisches Verständnis.

Wir sind sehr daran interessiert, dieses Verständnis zu erweitern, zu vertiefen und zu vereinheitlichen, und wir hoffen, dass andere Leute weitere Antworten / Kommentare zu diesem Thema veröffentlichen werden.

Unsere praktische Rechenerfahrung hat gezeigt, dass die Schätzung des Rangs über

im Allgemeinen mit Methoden der steilsten Senkung verfolgt werden kann. Nach unserem Verständnis entsteht diese Robustheit aus einem geometrischen Grund, nämlich dem holomorphen Satz der halbierten Krümmung von Goldberg und Kobayashi. Dies ist natürlich kein strenger Beweis.

C

$\mathbb{C}$

John Sidles
quelle

Ist dieser Satz leicht zu formulieren? Wenn nicht, können Sie einen Link zu einer guten Aussage und Erklärung bereitstellen?

Tyson Williams

@Tyson: Ich denke, John spricht über seine Erfahrung beim Lösen von Instanzen des Problems und nicht über einen Satz.

Joe Fitzsimons

Sie haben ihn nach einem Satz gefragt, und er scheint nicht über einen zu sprechen. Ich dachte nur, du hättest ihn falsch verstanden.

Joe Fitzsimons

Eigentlich dachte ich, ich hätte einen Kommentar gepostet und war überrascht, ihn als Antwort zu sehen. Doh! Ich habe es gerade bearbeitet, um einen Verweis hinzuzufügen, aber es ist noch weit von einer zufriedenstellenden Antwort entfernt. Eine gute Frage von Tyson Williams! :)

John Sidles

@ Joe Er erwähnte den Satz der holomorphen, bisektionalen Krümmung von Goldberg und Kobayashi, also fragte ich ihn danach. Ich bin mir nicht sicher, ob das bedeutet, dass ich ihn missverstanden habe oder nicht.

Tyson Williams