25
$\begingroup$

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.)

$\endgroup$
17
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
12
$\begingroup$

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)$.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.