# Bounding 0-1 matrix with k unique rows

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.

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