Przybliżenie rangi znaku macierzy

Ranga znaku macierzy A z wpisami + 1, -1 jest najmniejszą rangą (ponad rzeczywistymi) macierzy B, która ma taki sam wzór znaków jak A (tj. dla wszystkich i , j ). Pojęcie to jest ważne w złożoności komunikacji i teorii uczenia się.$A_{ij}B_{ij}>0$$i,j$

Moje pytanie brzmi: czy są jakieś znane algorytmy (czas podwykonawczy), które przybliżają rangę znaku macierzy do współczynnika ?$o(n)$

(Zdaję sobie sprawę z dolnej granicy Forstera na poziomie znaku pod względem normy widmowej, ale to nie daje współczynnika aproksymacji lepszego niż ogólnie .)$\Omega(n)$

Uważam, że to otwarte pytanie.

Lee i Schraibman w „Algorytmie aproksymacji rangi aproksymacji” pokazują, że rangę aproksymacji można aproksymować do stałego współczynnika za pomocą algorytmu wielomianowego czasu. W tym celu wiążą wielkość programowania pół-skończonego z rangą aproksymacji, gdzie α jest jakimś skończonym parametrem większym niż 1. Doprowadzenie α do granicy nieskończoności daje rangę znaku, ale ich wynik nic w tym nie daje oprawa.$\gamma_2^\alpha$$\alpha$$\alpha$

$O(n/\log n)$$d$$S$

• $M$$S$$\mathrm{rank}\ M = O(n^{1-1/d})$
• $S$$d$

$M$$O(n^{1-1/d}/d)$$d = \Theta(\log n)$