Aproximación del rango de signos de una matriz

25

El rango de signos de una matriz A con entradas + 1, -1 es el rango mínimo (sobre los reales) de una matriz B que tiene el mismo patrón de signos que A (es decir, para todo i , j ) Esta noción es importante en la complejidad de la comunicación y la teoría del aprendizaje.AijBij>0i,j

Mi pregunta es: ¿Hay algún algoritmo conocido (tiempo subexponencial) que se aproxime al rango de signos de una matriz dentro de un factor ?o(n)

(Soy consciente del límite inferior de Forster en el rango de signos en términos de norma espectral, pero esto no produce una relación de aproximación mejor que en general).Ω(n)

Moritz
fuente

Respuestas:

17

Creo que esta es una pregunta abierta.

Lee y Schraibman en "Un algoritmo de aproximación para el rango de aproximación" muestran que el rango de aproximación puede aproximarse a un factor constante mediante un algoritmo de tiempo polinómico. Para hacerlo, relacionan una cantidad de programación semidefinida con el rango de aproximación, donde α es un parámetro finito mayor que 1. Llevar a α al límite del infinito produce el rango de signos pero su resultado no da nada en esto ajuste.γ2ααα

arnab
fuente
12

O(n/logn)dS

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

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

Sasho Nikolov
fuente