Given a non-negative real matrix $M$ of non-negative rank at least $r$, can we witness this fact by a small submatrix of $M$? While Moitra (SIAM J. Comput. 2013) proved that this cannot be achieved exactly, we show that such a witnessing is possible approximately: an $m\times n$ matrix always contains a submatrix with at most $r^3$ rows and columns of non-negative rank at least $\Omega(\frac{r}{\log n\log m})$. A similar result is proved for the $1$-partition number of a Boolean matrix and, consequently, also for its two-player deterministic communication complexity. Tightness of the latter estimate is closely related to Log-rank conjecture.

Given a non-negative real matrix $M$ of non-negative rank at least $r$, can we witness this fact by a small submatrix of $M$? While Moitra (SIAM J. Comput. 2013) proved that this cannot be achieved exactly, we show that such a witnessing is possible approximately: an $m\times n$ matrix always contains a submatrix with at most $r^3$ rows and columns of non-negative rank at least $\Omega(\frac{r}{\log n\log m})$. A similar result is proved for the $1$-partition number of a Boolean matrix and, consequently, also for its two-player deterministic communication complexity. Tightness of the latter estimate is closely related to Log-rank conjecture.