$\epsilon$-approximation rank of a matrix $M$ is the minimum rank of a real matrix $A$ which differs from $M$ at most $\epsilon$ in each entry. Associating any function $f:X\times Y\rightarrow${1,-1} with a $(1,-1)$ matrix $M_f$ of size $|X|\times |Y|$. We know the log of rank of $M_f$ is lower bound of deterministic communication complexity of $f$ and the log of approximation rank of $M_f$ is lower bound of randomized communication complexity. The largest gap between deterministic communication complexity and randomized communication complexity is exponential. So how about the largest gap between rank and approximation rank?
$\begingroup$
$\endgroup$
5
-
$\begingroup$ How about comparing the zero matrix with ${\epsilon}I$ ? Or am I missing something? Gerhard "Ask Me About System Design" Paseman, 2011.04.14 $\endgroup$– Gerhard PasemanApr 15, 2011 at 6:08
-
2$\begingroup$ @Gerhard No 0's. But what about $J$ vs $\epsilon I+J$ With $J$ the all $1$'s matrix of the appropriate shape and $I$ the usual identity maxtrix with possible rows or columns of all $0$ to pad it to the correct size. $\endgroup$– Aaron MeyerowitzApr 15, 2011 at 6:28
-
1$\begingroup$ @Aaron, the way I read the problem, $M$ is to have $\pm1$ entries, and the matrix $A$ differing from $M$ by at most $\epsilon$ is to have as small a rank as possible. Your example goes the other way. $\endgroup$– Gerry MyersonApr 15, 2011 at 6:36
-
2$\begingroup$ For example, suppose $M$ has rank 2. $M$ must have a $2 \times 2$ submatrix $S$ that has rank 2. We can assume wlog this is $\left(\matrix{1 & 1\cr 1 & -1\cr}\right)$. It is then easy to see that any $2 \times 2$ matrix that differs by less than 1 from this in each entry has rank 2, so if $\epsilon < 1$ the $\epsilon$-approximation rank is 2. $\endgroup$– Robert IsraelApr 15, 2011 at 7:05
-
$\begingroup$ One could derive this bound from one on 0/1 matrices. Suppose M is a square full-rank -1/1 submatrix; suppose wlog that the first column is all ones; subtract this first column from all the other ones, and you remain with a $(n-1)\times (n-1)$ 0-2 matrix. By going backward we see that an entrywise-$\leq\varepsilon$ perturbation of the initial matrix becomes a $\leq 2\varepsilon$ perturbation of the modified matrix. So, if we can bound the distance from singularity of full-rank, square 0/1 matrices then we can extend this result to -1/1 matrices. $\endgroup$– Federico PoloniApr 15, 2011 at 8:13
Add a comment
|