How to reduce the low-rank matrix completion problem to integer programming?

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.

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$.

StackExchange Computer Science Q#34026, answer score: 4