Complejidad del rango de tensor sobre un campo infinito

Un tensor es una generalización de vectores y matrices a dimensiones superiores y el rango de un tensor también generaliza el rango de una matriz. A saber, el rango de un tensor es el número mínimo de rango uno tensores que suma a . Un vector y una matriz son tensores de grado 1 y 2 respectivamente. $T$ $T$

Los elementos en proceden de un campo . Si es finito, Håstad demostró que decidir si el rango de un tensor de grado 3 es a lo sumo es NP completo, pero cuando es un campo infinito como los racionales , no da (o cita) ningún límite superior. $T$ $\mathbb{F}$ $\mathbb{F}$ $r$ $\mathbb{F}$ $\mathbb{Q}$

Pregunta: ¿Cuál es el límite superior más conocido para la complejidad de decidir si el rango de un tensor de grado 3 sobre es como máximo ? $T$ $\mathbb{Q}$ $r$

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

¿Es el rango de un tensor de grado tres sobre ℚ el mismo que el rango del mismo tensor sobre ℝ? Si es así, el problema puede formularse como un caso especial de la Teoría Existencial de los Reales y, por lo tanto, reside en PSPACE.

Tsuyoshi Ito

La idea en mi comentario anterior no funcionará porque el rango de un tensor de grado tres sobre ℚ a veces es diferente del rango del mismo tensor sobre ℝ. Sea {x, y} la base de un espacio vectorial bidimensional, y considere el tensor 2x⊗x⊗x + x⊗y⊗y + y⊗x⊗y + y⊗y⊗x. No es difícil ver que su rango sobre ℝ es dos, pero su rango sobre ℚ es mayor que dos. (Este ejemplo se obtuvo modificando el ejemplo que muestra que el rango sobre ℝ puede ser diferente del rango sobre ℂ en Kruskal 1989 ).

Tsuyoshi Ito

@ Tsuyoshi Ito estoy completamente de acuerdo. Tampoco puedo encontrar ningún límite superior.

Tyson Williams

Creo que es mejor pedir computabilidad antes que complejidad.

Tsuyoshi Ito

El límite superior trivial es que es ce Hastad también demuestra en el mismo papel que el problema es

sobre

. El siguiente problema más general es ce-complete: dado un tensor parcialmente lleno, ¿hay una finalización que tenga rango

N P - h a r d

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

Q

$\mathbb{Q}$

\leq r

$\leq r$

Kaveh

Respuestas:

Hay un preprint reciente sobre esto: http://galton.uchicago.edu/~lekheng/work/np.pdf . Esto demuestra que la mayoría de los problemas relacionados con rango-tensores son NP dura más de y . (También menciona que decidir el rango sobre es NP difícil). $\mathbb{R}$ $\mathbb{C}$ $\mathbb{Q}$

Bart
fuente

Bart, esa preimpresión (de Hillar y Lim) es excelente ... muchas gracias.

John Sidles

Agradable. Sin embargo, no entiendo esta oración: "Si bien el resultado de Håstad se aplica a

, estas opciones de campos no tienen sentido para todos menos uno de los problemas anteriores (la excepción es el sistema bilineal de ecuaciones) ya que estos son problemas analíticos solo bien definidos sobre un campo completo de la característica 0 con un valor absoluto. Entre tales campos,

son, con mucho, los más comunes en las aplicaciones, por lo que restringiremos nuestras discusiones a estos campos ".

Q

$\mathbb{Q}$

F_{q}

$\mathbb{F}_q$

R

$\mathbb{R}$

C

$\mathbb{C}$

Tyson Williams el

Uno de los problemas a los que se hace referencia en la cita anterior es el rango. ¿Dicen estos autores que el rango de un tensor no está bien definido sobre

Q

$\mathbb{Q}$

Tyson Williams el

@Tyson: Creo que los autores sólo quiero decir que para muchas aplicaciones numéricas (ecuaciones diferenciales parciales, procesamiento de señales), que quiere hacer cálculos en

. Al ser un analista numérica a mí mismo, no veo muchas aplicaciones definidas sobre

. No implica que el rango no está bien definido en

R

$\mathbb{R}$

C

$\mathbb{C}$

Q

$\mathbb{Q}$

Q

$\mathbb{Q}$

Bart

Aunque esta fue realmente la única respuesta (ya que John quiso decir que era un comentario suyo), todavía creo que esta respuesta merece la recompensa, ya que proporcionó una referencia que mostró dureza sobre los otros campos infinitos importantes (reales y complejos). Como sugiere el título de mi pregunta, tengo curiosidad por los campos infinitos en general, pero decidí preguntar sobre los racionales para tener una pregunta con una respuesta específica. Todavía elegiré otra pregunta como la respuesta aceptada si alguien puede proporcionar un límite superior (o mostrar que es indiscutible).

Tyson Williams

El libro Perspectivas en la complejidad computacional: el volumen del aniversario de Somenath Biswas publicado este verano (julio de 2014) concuerda en gran medida con el consenso al que llegamos aquí. En la página 199 , dice:

Hasta donde sé, ni siquiera se sabe si [el problema de calcular el rango del tensor] sobre es decidible. Sobre , la situación es algo mejor ... El problema es decidible e incluso en PSPACE, ya que puede reducirse a la teoría existencial de los reales. $\mathbb{Q}$ $\mathbb{R}$

Tyson Williams
fuente

Una preimpresión reciente también confirma esto: arxiv.org/pdf/1612.04338v1.pdf . (Ver la tabla en la página 3.)

Huck Bennett

Nota: El texto a continuación tenía la intención de ser un comentario ... definitivamente no es una respuesta, sino más bien una observación pragmática que surgió de una reformulación de los Principios de resonancia magnética de Charlie Slichter en el lenguaje de la geometría simpléctica y la teoría de la información cuántica (que retrocede) naturalmente en espacios de estado de tensor-producto de rango polinómico). En la actualidad tenemos una comprensión geométrica parcial de estos métodos de rango tensorial, una comprensión informática cuántica marginal, esencialmente ninguna comprensión teórica de complejidad o combinatoria, y una comprensión computacional funcional (pero en gran medida empírica).

Estamos muy interesados en ampliar, profundizar y unificar esta comprensión, por lo que esperamos que otras personas publiquen más respuestas / comentarios sobre este tema.

Nuestra experiencia computacional práctica ha sido que estimar el rango sobre

es genéricamente manejable mediante métodos de descenso más pronunciado ... tal como lo entendemos, esta robustez surge por una razón geométrica, a saber, el teorema de curvatura biseccional holomorfa de Goldberg y Kobayashi. Esto está lejos de ser una prueba rigurosa, no hace falta decirlo.

C

$\mathbb{C}$

John Sidles
fuente

¿Es este teorema fácil de enunciar? Si no, ¿puede proporcionar un enlace a una buena declaración y explicación?

Tyson Williams el

@ Tyson: Creo que John está hablando de su experiencia resolviendo casos del problema y no de un teorema.

Joe Fitzsimons

Le preguntaste sobre un teorema, y él no parece estar hablando de uno. Solo pensé que lo habías entendido mal.

Joe Fitzsimons

En realidad, pensé que había publicado un comentario y me sorprendió ver que aparecía como respuesta. Doh! Acabo de editarlo para agregar una referencia, pero aún está muy lejos de ser una respuesta satisfactoria. ¡Una buena pregunta de Tyson Williams! :)

John Sidles

@ Joe Mencionó el teorema de curvatura biseccional holomorfa de Goldberg y Kobayashi, así que le pregunté al respecto. No estoy seguro de si eso significa que lo entendí mal o no.

Tyson Williams el