Complexité du rang des tenseurs sur un champ infini

Un tenseur est une généralisation de vecteurs et de matrices à des dimensions supérieures et le rang d'un tenseur généralise également le rang d'une matrice. A savoir, le rang d'un tenseur $T$ est le nombre minimum de rang un tenseurs cette somme à $T$ . Un vecteur et une matrice sont des tenseurs de degré 1 et 2 respectivement.

Les éléments de $T$ proviennent d'un champ $\mathbb{F}$ . Si $\mathbb{F}$ est fini, alors Håstad a prouvé que décider si le rang d'un tenseur de degré 3 est au plus $r$ est NP-complet, mais quand $\mathbb{F}$ est un champ infini comme les rationnels $\mathbb{Q}$ , il ne donne (ou ne cite) aucune limite supérieure.

Question: Quel est le plus connu majorant la complexité de décider si le rang d'un degré 3 tenseur sur est au plus ? $T$ $\mathbb{Q}$ $r$

ds.algorithms reference-request computability tensor-rank Tyson Williams
la source

Le rang d'un tenseur de degré trois sur ℚ est-il le même que le rang du même tenseur sur ℝ? Si tel est le cas, le problème peut être formulé comme un cas particulier de la théorie existentielle des réels et réside donc dans PSPACE.

Tsuyoshi Ito

L'idée dans mon commentaire précédent ne fonctionnera pas car le rang d'un tenseur de degré trois sur ℚ est parfois différent du rang du même tenseur sur ℝ. Soit {x, y} la base d'un espace vectoriel bidimensionnel et considérons le tenseur 2x⊗x⊗x + x⊗y⊗y + y⊗x⊗y + y⊗y⊗x. Il n'est pas difficile de voir que son rang sur ℝ est deux mais son rang sur ℚ est supérieur à deux. (Cet exemple a été obtenu en modifiant l'exemple montrant que le classement sur ℝ peut être différent du classement sur ℂ dans Kruskal 1989. )

Tsuyoshi Ito

@Tsuyoshi Ito Je suis entièrement d'accord. Je ne trouve pas non plus de limite supérieure.

Tyson Williams

Je pense qu'il vaut mieux demander la calculabilité avant la complexité.

Tsuyoshi Ito

Le limitesup trivial est qu'il est Hastad CE prouve également dans le même document que le problème est

sur

. Le problème plus général suivant est ce-complet: étant donné un tenseur partiellement rempli, y a-t-il un achèvement de rang

N P - h a r d

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

Q

$\mathbb{Q}$

\leq r

$\leq r$

Kaveh

Réponses:

Il existe une préimpression récente à ce sujet: http://galton.uchicago.edu/~lekheng/work/np.pdf . Il montre que la plupart des questions connexes rang avec tenseurs sont difficiles NP sur et . (Il mentionne également que décider du rang sur est difficile NP.) $\mathbb{R}$ $\mathbb{C}$ $\mathbb{Q}$

Bart
la source

Bart, cette préimpression (par Hillar et Lim) est formidable ... merci beaucoup.

John Sidles

Agréable. Cependant, je ne comprends pas cette phrase: "Bien que le résultat de Håstad s'applique à

, ces choix de champs n'ont pas de sens pour tous mais un des problèmes ci-dessus (l'exception étant le système bilinéaire d'équations) car ce sont problèmes analytiques uniquement bien définis sur un champ complet de caractéristique 0 avec une valeur absolue. Parmi ces domaines,

sont de loin les plus courants dans les applications et nous limiterons donc nos discussions à ces domaines. "

Q

$\mathbb{Q}$

F_{q}

$\mathbb{F}_q$

R

$\mathbb{R}$

C

$\mathbb{C}$

Tyson Williams

L'un des problèmes mentionnés dans la citation ci-dessus est le grade. Ces auteurs disent-ils que le rang d'un tenseur n'est pas bien défini sur

Q

$\mathbb{Q}$

Tyson Williams

@Tyson: Je pense que les auteurs veulent juste dire que pour de nombreuses applications numériques (équations aux dérivées partielles, traitement du signal), vous voulez faire des calculs dans

. Être un analyste numérique moi - même, je ne vois pas beaucoup d' applications définies sur

. Ils ne signifient pas que le rang est pas bien définie sur

R

$\mathbb{R}$

C

$\mathbb{C}$

Q

$\mathbb{Q}$

Q

$\mathbb{Q}$

Bart

Bien que ce soit vraiment la seule réponse (puisque John voulait que ce soit un commentaire), je crois toujours que cette réponse mérite la prime car elle a fourni une référence qui a montré la dureté sur les autres champs infinis importants (réels et complexes). Comme le titre de ma question le suggère, je suis curieux de connaître les champs infinis en général mais j'ai décidé de poser des questions sur les logiques afin d'avoir une question avec une réponse précise. Je choisirai toujours une autre question comme réponse acceptée si quelqu'un peut fournir une limite supérieure (ou montrer qu'elle n'est pas calculable).

Tyson Williams

Le livre Perspectives in Computational Complexity: The Somenath Biswas Anniversary Volume publié cet été (juillet 2014) est en grande partie d'accord avec le consensus auquel nous sommes parvenus ici. À la page 199 , il est écrit:

À ma connaissance, on ne sait même pas si [le problème du calcul du rang du tenseur] sur est décidable. Sur , la situation est un peu meilleure ... Le problème est décidable et même dans PSPACE, puisqu'il peut être réduit à la théorie existentielle des réels. $\mathbb{Q}$ $\mathbb{R}$

Tyson Williams
la source

Une préimpression récente le confirme également: arxiv.org/pdf/1612.04338v1.pdf . (Voir le tableau à la page 3.)

Huck Bennett

Remarque: Le texte ci-dessous était destiné à être un commentaire ... ce n'est certainement pas une réponse, mais plutôt une observation pragmatique issue d'une reformulation des principes de résonance magnétique de Charlie Slichter dans le langage de la géométrie symplectique et de la théorie de l'information quantique (qui recule naturellement sur des espaces d'états de produits tensoriels de rang polynomial). À l'heure actuelle, nous avons une compréhension géométrique partielle de ces méthodes de rang de tenseur, une compréhension informatique quantique marginale, essentiellement aucune compréhension théorique ou combinatoire de la complexité, et une compréhension informatique fonctionnelle (mais largement empirique).

Nous sommes très intéressés à élargir, approfondir et unifier cette compréhension, et nous espérons donc que d'autres personnes publieront d'autres réponses / commentaires à ce sujet.

Notre expérience de calcul pratique a été que l'estimation du rang sur

est génériquement traitable par des méthodes de descente les plus abruptes ... telle que nous la comprenons, cette robustesse se pose pour une raison géométrique, à savoir le théorème de courbure bisectionnelle holomorphe de Goldberg et Kobayashi. C'est loin d'être une preuve rigoureuse, cela va sans dire.

C

$\mathbb{C}$

John Sidles
la source

Ce théorème est-il facile à énoncer? Sinon, pouvez-vous fournir un lien vers une bonne déclaration et une bonne explication?

Tyson Williams

@Tyson: Je pense que John parle de son expérience dans la résolution d'instances du problème, et non d'un théorème.

Joe Fitzsimons

Vous lui avez posé une question sur un théorème, et il ne semble pas en parler. Je pensais juste que tu l'avais mal compris.

Joe Fitzsimons

En fait, je pensais avoir posté un commentaire et j'ai été surpris de le voir apparaître comme une réponse. Ah! Je viens de le modifier pour ajouter une référence, mais c'est encore très loin d'une réponse satisfaisante. Une belle question de Tyson Williams! :)

John Sidles

@Joe Il a mentionné le théorème de courbure holomorphe bisectionnelle de Goldberg et Kobayashi, alors je lui ai posé des questions à ce sujet. Je ne sais pas si cela signifie que je l'ai mal compris ou non.

Tyson Williams