Let $M$ be a binary ($0-1$) matrix of size $n \times m$. We define binary rank of $M$ as the smallest positive integer $r$ for which there exists a product decomposition $M = UV$, where $U$ is $n \times r$ and $V$ is $r \times m$, and all entries of $U$ and $V$ come from $\{0, 1\}$.
My question is that is there known algorithmic way to determine the binary rank of $M$; and Singular value decomposition that support the binary rank. Any reference in this regard would highly help.
I had the following recent paper giving an fpt algorithm for binary rank. Our algorithm checks whether the given matrix has binary rank $k$ in $\mathcal{O}(2^{3k^2})poly(n+m)$ time, and if yes it also ouputs the corresponding decomposition.
On the Parameterized Complexity of Biclique Cover and Partition. L. Sunil Chandran, Davis Issac, and Andreas Karrenbauer. Published in IPEC 2016
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].
