Encontrar a solução mais esparsa para um sistema de equações lineares

13

Quão difícil é encontrar a solução mais esparsa para um sistema de equações lineares?

Mais formalmente, considere o seguinte problema de decisão:

Instância: Um sistema de equações lineares com coeficientes inteiros e um número .c

Pergunta: Existe uma solução para o sistema com pelo menos variáveis ​​atribuídas a zero?c

Também estou tentando determinar em que consiste a dependência . Ou seja, talvez o problema seja o FPT com o parâmetro c .cc

Todas as idéias ou referências são realmente apreciadas.

Michael Wehar
fonte

Respostas:

12

Considere o problema de maximizar o número de equações lineares satisfeitas sobre algum anel R , que geralmente é NP-difícil, por exemplo, no caso R = ZMAX-LIN(R)RR=Z

Tome uma instância desse problema, onde A é uma matriz n × m . Seja k = m + 1 . Construa um novo sistema linear ˜ A ˜ x = ˜ b , onde ˜ A é uma matriz k n × ( k n + m ) , ˜ x agora é um vetor dimensional ( k n + m ) , e ˜ bAx=bAn×mk=m+1A~x~=b~A~kn×(kn+m)x~(kn+m)b~é um vetor dimensional :kn

em queInrepresenta onxnmatriz identidade.

A~=[AInInInInInInIn],b~=[b00]
Inn×n

Note-se que este sistema é sempre satisfeita pelo vector . Na verdade, os primeiros m entradas de ~ x pode ser arbitrária, e há algum vector da solução com que prefixo.x~=(0bbb)Tmx~

Eu agora afirmar que fracção de equações de A x = b são sse satisfatível existe um escasso solução de ~ A ~ x = ~ b , que tem, pelo menos, ô n k zeros. Isso ocorre porque toda linha satisfeita de A x = b produz k zeros em potencial quando x é estendido para ˜ xδAx=bA~x~=b~δnkAx=bkxx~

Assim, se encontrar a dispersão da solução sparsest para , temos também maximizada δ , dividindo-se a dispersão por k .A~x~=b~δk

Portanto, acredito que seu problema é NP-difícil.

Joe Bebel
fonte
1
Legal! Obrigado por compartilhar. Então, o que você acha que a dependência está em c? Você acha que pode resolvê-lo em menos de ondené o tamanho da entrada? poly(n)(nc)n
Michael Wehar
1
Claro: se assumirmos que elementos de x são zero, você pode simplesmente remover esses elementos de x para obter uma dimensão menor x ' e também remover as colunas correspondentes de A para obter A ' . Em seguida, use a eliminação gaussiana para decidir se o sistema reduzido A x = b é viável; se for, você encontrou uma solução esparsa. Então, você tenta tudo ( ncxxxAAAx=b possívelAx(nc) . Ax
Joe Bebel
1
@MichaelWehar Eu não sei se este problema é FPT ou não embora
Joe Bebel
6

O problema é NP-completo, por redução do seguinte problema: Dada uma matriz A com entradas inteiras e um vetor inteiro b com nm×nAbn entradas, existe um vetor 0-1 com A x = b ?xAx=b

Para cada coordenada do vetor x , xix

  • introduza novas equações x i + y i , k = 0 com k = 1 , 100(n+m)xi+yi,k=0 e k=1,,100(n+m)
  • introduza novas equações x i + z i , k = 1 com k = 1 , 100(n+m)xi+zi,k=1 . k=1,,100(n+m)

Além disso, use o antigo sistema de equações .Ax=b

Existe uma solução de 0-1 para o sistema original , se e somente se o novo sistema tiver uma solução na qual pelo menos 100 ( n + m ) n variáveis ​​sejam zero.Ax=b100(n+m)n

Gamow
fonte
4

Esse problema é difícil , em várias configurações. Como indicado nas outras respostas a esta pergunta, o problema é NP-completo sobre os números inteiros.

No processamento de sinais, a matriz e os vetores têm entradas racionais, e esse problema às vezes é chamado de problema de reconstrução esparsa . Nesta configuração, o problema é NP-completo (consulte o Teorema 1).

Na teoria da codificação, as entradas são de um campo finito e esse problema às vezes é chamado de problema de decodificação de probabilidade máxima . Nesse cenário, o problema é NP-completo e não no tempo subexponencial , assumindo a hipótese do tempo exponencial. Além disso, de acordo com uma versão anterior de um artigo sobre o arXiv (consulte o Lema C.2 na versão 1 do artigo), o problema é W [1] - completo.

argentpepper
fonte
Sua referência à completude W [1] não parece ter um "Lema C.2".
@RickyDemer Existe um Lemma C.2 na versão 1 do artigo que ele vinculou. No entanto, a versão 2 parece ter um título diferente e foi alterada muito recentemente.
22815 Michael Wehar
Esse lema usa uma parametrização diferente do OP.
Ah, eu não sabia que havia uma versão atualizada, vou dar uma olhada e atualizar minha resposta de acordo.
Argentpepper
Como mencionei no meu comentário anterior, que "o lema usa uma parametrização diferente do OP", portanto, mesmo se assumirmos que o resultado é verdadeiro (apesar de ter sido removido da versão 2), a pergunta do OP sobre complexidade parametrizada ainda estaria em aberto.