<p><a href="http://arxiv.org/abs/1503.07648">Recent work by Alon, Moran, and Yehudayoff</a> gives an $O(n/\log n)$ approximation algorithm. Let $d$ be the VC-dimension of a sign matrix $S$. The idea is that </p>

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

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

CC BY-SA 3.0
2015-11-17T12:15:55.280Z
2015-11-17T12:15:55.280Z
Sasho Nikolov
<p>I believe this is an open question.  </p>

<p>Lee and Schraibman in <a href="http://www.research.rutgers.edu/~troyjlee/approx_rank.pdf">"An approximation algorithm for approximation rank"</a> show that the <i>approximation rank</i> 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.</p>

CC BY-SA 2.5
2010-08-17T18:10:04.980Z
2010-08-17T18:20:48.827Z
2010-08-17T18:20:48.827Z
arnab
<p>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.</p>

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

<p>(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.)</p>

<lg.learning><open-problem><communication-complexity><matrices>
Approximating the sign rank of a matrix
Moritz
# Approximating the sign rank of a matrix

(Asked by: username_0 on 2010-08-17)

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

**Tags:** lg.learning, open-problem, communication-complexity, matrices

---

## 2 answers

### Answer by username_2 on 2010-08-17. Score: 17 | Accepted answer

I believe this is an open question.

Lee and Schraibman in ["An approximation algorithm for approximation rank"](http://www.research.rutgers.edu/~troyjlee/approx_rank.pdf) 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 by username_1 on 2015-11-17. Score: 12

[Recent work by Alon, Moran, and Yehudayoff](http://arxiv.org/abs/1503.07648) 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)$.


---

