Approximating the sign rank of a matrix

Question

The sign rank of a matrix A with +1,-1 entries is the least rank (over the reals) of a matrix B which has the same sign pattern as A (i.e., $A_{ij}B_{ij}>0$ for all $i,j$). This notion is important in communication complexity and learning theory.

My question is: Are there any known (subexponential time) algorithms that approximate the sign-rank of a matrix to within a factor $o(n)$?

(I am aware of Forster's lower bound on the sign rank in terms of spectral norm, but this does not yield an approximation ratio better than $\Omega(n)$ in general.)

Answer 1

I believe this is an open question.

Lee and Schraibman in "An approximation algorithm for approximation rank" show that the approximation rank can be approximated to a constant factor by a polynomial time algorithm. To do so, they relate a semidefinite programming quantity $\gamma_2^\alpha$ to the approximation rank, where the $\alpha$ is some finite parameter greater than 1. Taking $\alpha$ to the limit of infinity yields the sign-rank but their result does not give anything in this setting.

Answer 2

Recent work by Alon, Moran, and Yehudayoff gives an $O(n/\log n)$ approximation algorithm. Let $d$ be the VC-dimension of a sign matrix $S$. The idea is that

• there exists an efficiently computable matrix $M$ with sign pattern $S$ such that $\mathrm{rank}\ M = O(n^{1-1/d})$;
• the sign rank of $S$ is at least $d$.

So the algorithm computes $M$ and outputs its rank. The approximation ratio is $O(n^{1-1/d}/d)$, which is maximized at $d = \Theta(\log n)$.