Binary rank of binary matrix
This is equivalent to the biclique partition number of a bipartite graph. You can think of M as representing a bipartite graph $G$ on $[n] \times [m]$ in the natural way: $M_{i,j}$ is 1 if and only if there is an edge $(i,j)$ in G (where $i$ is an element of the left partition, and $j$ an element of the right partition). Then $M$ has binary rank $r$ if and only if the edges of the corresponding bipartite graph $G$ can be partitioned into $r$ complete bipartite subgraphs. To see this, take an optimal factorization $M = UV^\intercal$, denote the columns of $U$ by $u_1, \ldots, u_r$, and the columns of $V$ by $v_1, ..., v_r$. $M=UV^\intercal$ is equivalent to $M = \sum_{i = 1}^r{u_i v_i^\intercal}$, and $u_i v_i^\intercal$ represents a complete bipartite graph on the vertices $S_i \cup T_i$, where $S_i$ is the set of left vertices for which $u_i$ is the indicator vector, and $T_i$ is the set of right vertices for which $v_i$ is the indicator vector.

Computing the biclique partition number is NP-hard, and hard to approximate. See these two papers for some results and references: [1], [2].