Complexidade da classificação de tensores em um campo infinito

Um tensor é uma generalização de vetores e matrizes para dimensões mais altas e a classificação de um tensor também generaliza a classificação de uma matriz. Ou seja, a classificação de um tensor é o número mínimo de grau um tensores que soma a . Um vetor e uma matriz são tensores de grau 1 e 2, respectivamente. $T$ $T$

Os elementos em vêm de um campo . Se é finito, Håstad provou que decidir se a classificação de um tensor de grau 3 é no máximo é NP-completo, mas quando é um campo infinito como os racionais , ele não dá (ou cita) nenhum limite superior. $T$ $\mathbb{F}$ $\mathbb{F}$ $r$ $\mathbb{F}$ $\mathbb{Q}$

Pergunta: Qual é o limite superior mais conhecido para a complexidade de decidir se a classificação de um tensor de grau 3 acima de é no máximo ? $T$ $\mathbb{Q}$ $r$

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

A classificação de um tensor de grau três está acima de ℚ igual à classificação do mesmo tensor acima de ℝ? Nesse caso, o problema pode ser formulado como um caso especial da Teoria Existencial dos Reais e, portanto, está no PSPACE.

Tsuyoshi Ito

A idéia no meu comentário anterior não funcionará porque a classificação de um tensor acima de três graus ℚ às vezes é diferente da classificação do mesmo tensor acima de ℝ. Seja {x, y} a base de um espaço vetorial bidimensional e considere o tensor 2x⊗x⊗x + x⊗y⊗y + y⊗x⊗y + y⊗y⊗x. Não é difícil ver que sua classificação acima de ℝ é dois, mas sua classificação acima de ℚ é maior que dois. (Este exemplo foi obtido modificando o exemplo que mostra que a classificação acima de ℝ pode ser diferente da classificação acima de ℂ em Kruskal 1989 ).

Tsuyoshi Ito

@Tsuyoshi Ito Concordo plenamente. Também não consigo encontrar nenhum limite superior.

Tyson Williams

Eu acho que é melhor pedir computabilidade antes da complexidade.

Tsuyoshi Ito

O limite superior é trivial que é ce Hastad também prova no mesmo papel que o problema é

sobre

. O seguinte problema mais geral é ce-complete: dado um tensor parcialmente preenchido, existe uma conclusão dele com classificação

N P - h a r d

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

Q

$\mathbb{Q}$

\leq r

$\leq r$

Kaveh

Respostas:

Há uma pré-impressão recente sobre isso: http://galton.uchicago.edu/~lekheng/work/np.pdf . Isso mostra que a maioria dos problemas de classificação relacionada com tensores são NP duro durante e . (Também menciona que decidir a classificação sobre é NP difícil.) $\mathbb{R}$ $\mathbb{C}$ $\mathbb{Q}$

Bart
fonte

Bart, essa pré-impressão (de Hillar e Lim) é fantástica ... muito obrigado.

John Sidles

Agradável. No entanto, não entendo esta frase: "Embora o resultado de Håstad se aplique a

, essas opções de campos não fazem sentido para todos, exceto um dos problemas acima (a exceção é o sistema bilinear de equações), pois são problemas analíticos apenas bem definidos sobre um campo completo da característica 0. com um valor absoluto. Entre esses campos,

são de longe os mais comuns em aplicações e, portanto, restringiremos nossas discussões a esses campos ".

Q

$\mathbb{Q}$

F_{q}

$\mathbb{F}_q$

R

$\mathbb{R}$

C

$\mathbb{C}$

Tyson Williams

Um dos problemas mencionados na citação acima é a classificação. Esses autores estão dizendo que a classificação de um tensor não está bem definida em relação a

Q

$\mathbb{Q}$

Tyson Williams

@Tyson: Eu acho que os autores só quero dizer que para muitas aplicações numéricas (equações diferenciais parciais, processamento de sinal), você quer fazer cálculos em

. Sendo um analista numérica mim, não vejo muitas aplicações definidas em

. Eles não significam que a classificação não está bem definido em

R

$\mathbb{R}$

C

$\mathbb{C}$

Q

$\mathbb{Q}$

Q

$\mathbb{Q}$

Bart

Embora essa fosse realmente a única resposta (já que John queria que ele fosse um comentário), ainda acredito que essa resposta merece a recompensa, pois forneceu uma referência que mostrou dureza sobre os outros importantes campos infinitos (reais e complexos). Como sugere o título da minha pergunta, estou curioso sobre campos infinitos em geral, mas decidi perguntar sobre os racionais para ter uma pergunta com uma resposta específica. Ainda vou escolher outra pergunta como resposta aceita, se alguém puder fornecer um limite superior (ou mostrar que é incontestável).

Tyson Williams

O livro Perspectivas em complexidade computacional: o volume do aniversário de Somenath Biswas publicado neste verão (julho de 2014) concorda amplamente com o consenso que chegamos aqui. Na página 199 , diz:

$\mathbb{Q}$ $\mathbb{R}$

Tyson Williams
fonte

Uma pré-impressão recente também confirma isso: arxiv.org/pdf/1612.04338v1.pdf . (Veja a tabela na página 3.)

Huck Bennett

Nota: O texto abaixo foi planejado como um comentário ... definitivamente não é uma resposta, mas sim uma observação pragmática que surgiu de uma reafirmação dos Princípios de ressonância magnética de Charlie Slichter na linguagem da geometria simplética e da teoria quântica da informação (o que retrocede naturalmente nos espaços de estado do produto tensorial de classificação polinomial). Atualmente, temos uma compreensão geométrica parcial desses métodos de classificação de tensores, uma compreensão quântica marginal da informática, essencialmente nenhuma compreensão teórica ou combinatória da complexidade e uma compreensão computacional funcional (mas amplamente empírica).

Estamos muito interessados em ampliar, aprofundar e unificar esse entendimento e, portanto, esperamos que outras pessoas publiquem mais respostas / comentários sobre esse assunto.

C

$\mathbb{C}$

John Sidles
fonte

É fácil afirmar esse teorema? Caso contrário, você pode fornecer um link para uma boa declaração e explicação?

Tyson Williams

@ Tyson: Eu acho que John está falando sobre sua experiência em resolver instâncias do problema, e não sobre um teorema.

Joe Fitzsimons

Você perguntou a ele sobre um teorema, e ele não parece estar falando sobre um. Eu apenas pensei que você o tivesse entendido mal.

Joe Fitzsimons

Na verdade, pensei ter postado um comentário e fiquei surpreso ao vê-lo aparecer como resposta. Doh! Acabei de editá-lo para adicionar uma referência, mas ainda está muito longe de ser uma resposta satisfatória. Uma ótima pergunta de Tyson Williams! :)

John Sidles

@ Joe Ele mencionou o teorema da curvatura bissecional holomórfica de Goldberg e Kobayashi, então eu perguntei a ele sobre isso. Não tenho certeza se isso significa que eu o entendi mal ou não.

Tyson Williams