0
$\begingroup$

Problem Statement: Suppose that I have a $0-1$ matrix $A$ (all of the entries are $0$ or $1$). I wish to find the tightest upper bound with $k$ many unique rows. To be more precise, let S denote the set of $0-1$ matrices $B$ such that it only has $k$ unique rows, $A_{ij} \leq B_{ij}$ for all $i$ and $j$. Find $$\min_{B \in S} ||A - B||$$

Example: Suppose $k = 2$ and $$A = \begin{bmatrix} 1 & 0 & 0 & 0 & 0\\ 1 & 1 & 0 & 0 & 0\\ 0 & 0 & 1 & 0 & 1\\ 0 & 0 & 1 & 1 & 0\\ \end{bmatrix}$$ Then the optimal matrix $B$ is $$A = \begin{bmatrix} 1 & 1 & 0 & 0 & 0\\ 1 & 1 & 0 & 0 & 0\\ 0 & 0 & 1 & 1 & 1\\ 0 & 0 & 1 & 1 & 1\\ \end{bmatrix}$$ Since $B$ only has $2$ distinct rows, $A \leq B$, and $||A - B|| = 3$ is minimized.

Question 1: This problem reminds of the minimum $k$-union, set-union, and other NP-complete problems. Is this problem an NP-complete optimization problem?

Question 2: Is there an efficient way to obtain approximately optimal matrix $B \in S$? Instead of minimizing $||A - B||$, can we get close to the minimum possible value?

So far, I have tried to cluster each row of matrix $A$ using k-means. Then within each cluster $i$, I tried to construct a vector $v_i$. Where $j^{th}$ entry of $v_i$ is $1$ if at least p-percent of the vectors in cluster $i$ has $j^{th}$ entry to be $1$. The vectors $v_i$ served as initial potential guess for possible rows of the matrix $B$. Then I used greedy algorithm. This has decent performance, but it's not great.

$\endgroup$
3
  • $\begingroup$ Which matrix norm does $\| \cdot \|$ represent? Can you edit the question to state that? $\endgroup$ – D.W. Jun 24 '20 at 4:15
  • $\begingroup$ Apparently it's the $\left\lVert \cdot \right\rVert_1$ norm $\endgroup$ – dhasson Jun 24 '20 at 14:13
  • $\begingroup$ $||\cdot ||_p$ for any $p \geq 0$ results in same minimization problem. But $||\cdot||_1$ is probably the easiest to think about. $\endgroup$ – Jaeyoon Kim Jun 24 '20 at 16:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.