Aproximando a classificação de sinais de uma matriz

25

A classificação de sinal de uma matriz A com entradas + 1, -1 é a menor classificação (acima dos reais) de uma matriz B que possui o mesmo padrão de sinal de A (ou seja, para todos os i , j ) Essa noção é importante na complexidade da comunicação e na teoria da aprendizagem.AijBij>0i,j

Minha pergunta é: Existem algoritmos conhecidos (tempo subexponencial) que aproximam a classificação de sinais de uma matriz dentro de um fator ?o(n)

(Estou ciente do limite inferior de Forster na classificação dos sinais em termos de norma espectral, mas isso não produz uma taxa de aproximação melhor que em geral.)Ω(n)

Moritz
fonte

Respostas:

17

Eu acredito que esta é uma questão em aberto.

Lee e Schraibman em "Um algoritmo de aproximação para classificação de aproximação" mostram que a classificação de aproximação pode ser aproximada a um fator constante por um algoritmo de tempo polinomial. Para fazer isso, eles relacionam uma quantidade de programação semidefinida à classificação de aproximação, onde α é um parâmetro finito maior que 1. Levar α até o limite do infinito gera a classificação de sinais, mas seu resultado não fornece nada nesse sentido. configuração.γ2ααα

arnab
fonte
12

O(n/logn)dS

  • MSrank M=O(n11/d)
  • Sd

MO(n11/d/d)d=Θ(logn)

Sasho Nikolov
fonte