Calcular o polítopo dimensional mais baixo a partir de um determinado conjunto de vetores de sinais

11

Dado um conjunto de hiperplanos determinado pelos vetores normais , seus tipos de células (ou vetores de sinais) são todos vetores t { + , - } m para os quais existe um vetor v R d de modo que v , h i0 e t i = sinal ( v , h i)h1,,hmRdt{+,}mvRdv,hi0ti=sign(v,hi)vale para todos . Aqui, u , v denota o produto interno e sinal ( x ) denota o sinal ( + ou - ) do diferente de zero número real x .iu,vsign(x)+x

Pergunta: Qual é o algoritmo mais rápido conhecido para a operação inversa? Dado um conjunto de tipos de células, queremos calcular algum conjunto de hiperplanos nas menores dimensões possíveis, para que seus tipos de células sejam um superconjunto de t 1 , , t n .t1,,tnt1,,tn

Holger
fonte
1
Aliás, não está claro qual é o produto interno de um hiperplano e um vetor. Você tinha a intenção para ser o vetor normal do i hyperplane -ésimo? hii
Sasho Nikolov
Sim, eles deveriam ser os vetores normais - afirmei formalmente exatamente o que estou procurando.
Holger

Respostas:

5

Isso é equivalente ao cálculo da classificação de sinais de uma matriz, que é NP-difícil, como mostrado neste artigo . Portanto, você não pode esperar um algoritmo muito eficiente.

Sasho Nikolov
fonte