Return to Question

Let A be an $m\times n$ matrix and $k$ be an integer. We want to find a scalar $\epsilon$ and an $n\times n$ matrix $B$ such that $A\leq A(\epsilon I + B)$. The goal is to minimize $\epsilon$ and we have the following restrictions on $B$: 1) All elements of $B$ are non-negative. 2) Each column of $B$ has $L_1$ norm at most 1. 3) There are at most $k$ rows of $B$ that are non-zero (i.e., at least $n-k$ rows are zero vectors).

In case it helps, we may assume that $n>>k>>m$.

My goal is to get an algorithm for computing $B$ to minimize $\epsilon$ (either exactly or approximately) and my general question is whether you know of anything related. (I'm not familiar with this area. It's not even clear to me if the problem is NP-hard or not.) Another thing is whether it is possible to bound $\epsilon$ in terms of $k$, $m$ and $n$?

Let A be an $m\times n$ matrix and $k$ be an integer. Assume that $A$ is non-negative. We want to find a scalar $\epsilon$ and an $n\times n$ matrix $B$ such that $A\leq A(\epsilon I + B)$ (where $\leq$ is an element-wise comparison). The goal is to minimize $\epsilon$ and we have the following restrictions on $B$: 1) $B$ is non-negative. 2) Each column of $B$ has $L_1$ norm at most 1. 3) There are at most $k$ rows of $B$ that are non-zero (i.e., at least $n-k$ rows are zero vectors).

In case it helps, we may assume that $n>>k>>m$.

My goal is to get an algorithm for computing $B$ to minimize $\epsilon$ (either exactly or approximately) and my general question is whether you know of anything related. (I'm not familiar with this area. It's not even clear to me if the problem is NP-hard or not.) Another thing is whether it is possible to bound $\epsilon$ in terms of $k$, $m$ and $n$?