Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
Consider the low-rank matrix completion problem:
Given an integer $k$ and a subset of entries of some $n \times n$ matrix, fill in the rest of the entries so that the resulting matrix has rank at most $k$.
This problem is clearly in NP, since the set of additional entries is the required certificate. Therefore, it can be written as an integer program. How can one do this?
I'm having trouble seeing how to get rid of a rank constraint, even at the expense of adding integer constraints.
Simplifying the problem:
Given
- a positive integer $r$
- positive integers $m, n \geq 2$
- a partial binary matrix $\mathrm A \in \{*, 0,1\}^{m \times n}$ (where $*$ denotes an unknown entry)
determine whether it is possible to complete the given partial matrix $\mathrm A$ with values in $\{0,1\}$ such that the resulting completed matrix has rank at most $r$.
Let us consider an example.
Let $r = 2$, $m = n = 3$ and
$$\mathrm A = \begin{bmatrix} 1 & 1 & 1\\ 0 & 1 & 1\\ 0 & 0 & *\end{bmatrix}$$
Visual inspection of partial matrix $\mathrm A$ tells us that if the unknown $(3,3)$ entry is $0$, then the rank of the completed matrix is $2$. However, it would be nice not to have to rely on visual inspection.
If the rank is at most $2$, then there are matrices $\mathrm U, \mathrm V \in \{0,1\}^{3 \times 2}$ such that $\rm A = U V^{\top}$ holds at all known entries of $\rm A$. From the $(1,1)$ entry, we obtain the equation
$$(u_{11} \cdot v_{11}) \oplus (u_{12} \cdot v_{12}) = 1$$
where addition and multiplication are done over the finite field $\mathbb F_2$. Translating the equation above to propositional logic, we obtain
$$\Phi_{11} := \mbox{Xor} \left( u_{11} \land v_{11}, u_{12} \land v_{12} \right)$$
If $a_{ij} = 1$, we have $\Phi_{ij}$. If $a_{ij} = 0$, we have $\neg \Phi_{ij}$. Taking the conjunction of the CNFs of $\Phi_{ij}$ or $\neg \Phi_{ij}$, we obtain the following formula
$$\Psi := \mbox{CNF} (\Phi_{11}) \land \mbox{CNF} (\neg \Phi_{21}) \land \mbox{CNF} (\neg \Phi_{31}) \land \mbox{CNF} (\Phi_{12}) \land \mbox{CNF} (\Phi_{22}) \land \mbox{CNF} (\neg \Phi_{32}) \land \mbox{CNF} (\Phi_{13}) \land \mbox{CNF} (\Phi_{23})$$
which is in CNF by construction. If $\Psi$ is satisfiable, then there are matrices $\mathrm U, \mathrm V \in \{0,1\}^{3 \times 2}$ such that $\rm A = U V^{\top}$ holds at all known entries of $\rm A$. Using SymPy:
from sympy import *
u11, u12, u21, u22, u31, u32 = symbols('u11 u12 u21 u22 u31 u32')
v11, v12, v21, v22, v31, v32 = symbols('v11 v12 v21 v22 v31 v32')
Phi11 = Xor(u11 & v11, u12 & v12)
Phi21 = Xor(u21 & v11, u22 & v12)
Phi31 = Xor(u31 & v11, u32 & v12)
Phi12 = Xor(u11 & v21, u12 & v22)
Phi22 = Xor(u21 & v21, u22 & v22)
Phi32 = Xor(u31 & v21, u32 & v22)
Phi13 = Xor(u11 & v31, u12 & v32)
Phi23 = Xor(u21 & v31, u22 & v32)
Phi33 = Xor(u31 & v31, u32 & v32)
Psi = to_cnf(Phi11) & to_cnf(Not(Phi21)) & to_cnf(Not(Phi31)) & to_cnf(Phi12) & to_cnf(Phi22) & to_cnf(Not(Phi32)) & to_cnf(Phi13) & to_cnf(Phi23)
print "Formula Psi is \n", Psi
# is Psi satisfiable?
print "\nSatisfiable? \n", satisfiable(Psi)
produces $\Psi$ (in CNF)
And(Or(Not(u11), Not(u12), Not(v11), Not(v12)), Or(Not(u11), Not(u12), Not(v21), Not(v22)), Or(Not(u11), Not(u12), Not(v31), Not(v32)), Or(Not(u21), Not(u22), Not(v21), Not(v22)), Or(Not(u21), Not(u22), Not(v31), Not(v32)), Or(Not(u21), Not(v11), u22), Or(Not(u21), Not(v11), v12), Or(Not(u22), Not(v12), u21), Or(Not(u22), Not(v12), v11), Or(Not(u31), Not(v11), u32), Or(Not(u31), Not(v11), v12), Or(Not(u31), Not(v21), u32), Or(Not(u31), Not(v21), v22), Or(Not(u32), Not(v12), u31), Or(Not(u32), Not(v12), v11), Or(Not(u32), Not(v22), u31), Or(Not(u32), Not(v22), v21), Or(u11, u12), Or(u11, v12), Or(u11, v22), Or(u11, v32), Or(u12, v11), Or(u12, v21), Or(u12, v31), Or(u21, u22), Or(u21, v22), Or(u21, v32), Or(u22, v21), Or(u22, v31), Or(v11, v12), Or(v21, v22), Or(v31, v32))
and the satisfying assignment
{v31: False, v11: True, v32: True, u31: False, v22: True, u22: True, u11: True, v21: False, u12: True, u21: False, v12: False, u32: False}
Hence,
$$\mathrm U = \begin{bmatrix} 1 & 1\\ 0 & 1\\ 0 & 0\end{bmatrix}$$
$$\mathrm V = \begin{bmatrix} 1 & 0\\ 0 & 1\\ 0 & 1\end{bmatrix}$$
and, thus,
$$\mathrm U \mathrm V^{\top} = \begin{bmatrix} 1 & 0 & 0\\ 0 & 0 & 0\\ 0 & 0 & 0\end{bmatrix} + \begin{bmatrix} 0 & 1 & 1\\ 0 & 1 & 1\\ 0 & 0 & 0\end{bmatrix} = \begin{bmatrix} 1 & 1 & 1\\ 0 & 1 & 1\\ 0 & 0 & \color{red}{0}\end{bmatrix}$$
Thus, if the missing entry of $\rm A$ is zero, then we obtain a rank-$2$ matrix.
Translating to binary integer programming, formula $x_i \lor x_j$ becomes the linear inequality $x_i + x_j \geq 1$ and $\neg x_i$ becomes $1-x_i$. From $\Psi$ (in CNF), we obtain $32$ linear inequalities
$$\begin{array}{rl} - u_{11} - u_{12} - v_{11} - v_{12} &\geq -3\\ - u_{11} - u_{12} - v_{21} - v_{22} &\geq -3\\ & \vdots\\ v_{31} + v_{32} &\geq 1\end{array}$$
plus the inequality constraints $0 \leq u_{ij}, v_{ij} \leq 1$ and the integrality constraints $u_{ij}, v_{ij} \in \mathbb Z$.
To summarize, we reduced a simplified version of the original matrix completion problem to SAT and then we reduced SAT to binary integer programming. However, the reduction to SAT requires the computation of the CNF of either $\Phi_{ij}$ or $\neg \Phi_{ij}$, which produces a formula whose number of conjuncts may be non-polynomial in $r$.
Building on Rodrigo de Azevedo's answer, and assuming that you are dealing with binary matrices with all arithmetic done modulo 2, here is a more direct way to reduce this problem to integer linear programming:
A $n \times n$ matrix $M$ has rank $\le r$ iff there exist $n \times r$ matrices $U,V$ such that $M = UV^\top$. So, we can treat the entries of $U,V$ as unknowns (zero-or-one variables), and express the requirement that $M=UV^\top$ as a bunch of constraints, and see if there is any assignment to the variables that makes $M=UV^\top$ hold (for all of the entries of $M$ that are given).
Each constraint has the form
$$M_{ij} = \sum_{k=1}^r U_{ik} V_{jk} \pmod 2$$
where the $i,j$ cell of the partial matrix is filled with the value $M_{ij}$, and all arithmetic is done modulo 2.
Equivalently, this can be expressed as
$$M_{ij} = \sum_{k=1}^r U_{ik} V_{jk} - 2 S_{ij}$$
where $S_{ij}$ is some integer. We'll introduce fresh new temporary variables $T_{ijk},S_{ij}$ where $S_{ij}$ is constrained to be an integer and $T_{ijk}$ is constrained to be zero or one ($0 \le T_{ijk} \le 1$). We'll add some linear constraints to force that $T_{ijk} = U_{ik} V_{jk}$. Then we'll be able to write
$$M_{ij} = \sum_{k=1}^r T_{ijk} - 2 S_{ij}$$
which is a linear inequality.
So, all that remains is to express $T_{ijk} = U_{ik} V_{jk}$ (a nonlinear constraint) using linear inequalities. That can be done using the methods in Express boolean logic operations in zero-one integer linear programming (ILP). In particular, we can do that using the inequalities $T_{ijk} \ge U_{ik} + V_{jk} - 1$, $T_{ijk} \le U_{ik}$, $T_{ijk} \le V_{jk}$.
In this way, we obtain an integer program that uses only linear inequalities to express all of the constraints. It has $O(n^2r)$ variables and $O(n^2r)$ inequalities.
