Matrix approximation

Question

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

Answer 1

I'll address the last question (about an a priori bound for $\epsilon$).

If $n\gg k\gg m$, the worst-case bound for $\epsilon$ is between $c(m)\cdot k^{-2/(m-1)}$ and $C(m)\cdot k^{-1/(m-1)}$ (probably near the former but I haven't checked this carefully). Note that the bound does not depend on $n$.

Proof. The columns of $A$ form a set $S$ of cardinality at most $n$ in $\mathbb R^m$. For a given $\epsilon$, a suitable $B$ exists if and only if there is a subset $T\subset S$ of cardinality at most $m$ such that the convex hull $conv(T)$ majorizes the set $(1-\epsilon)S$ in the following sense: for every $v\in S$, there is a point in $conv(T)$ which is component-wise greater than $(1-\epsilon)v$. And this majorization is implied by the following: $conv(sym(T))$ contains the set $(1-\epsilon)S$, or equivalently, the set $(1-\epsilon)conv(sym(S))$, where by $sym(X)$ denotes the minimal origin-symmetric set containing $X$, that is, $sym(X)=X\cup -X$.

Consider the polytope $P=conv(sym(S))$. We want to find a subset of its vertices of cardinality at most $k$, such that their convex hull approximates $P$ up to $(1-\epsilon)$-rescaling. This problem is invariant under linear transformations, and we may assume that $P$ has nonempty interior. Then Fritz John's theorem asserts that there is a linear transformation of $\mathbb R^m$ which transforms $P$ to a body contained in the unit ball and containing the ball of radius $1/\sqrt m$. For such a set, $(1-\epsilon)$-scaling approximation follows from $(\epsilon/\sqrt m)$-approximation in the sense of Hausdorff distance. So it suffices to choose $T$ to be an $(\epsilon/\sqrt m)$-net in $S$. Then a standard packing argument gives the above upper bound for $\epsilon$.

On the other hand, if $S$ is contained in the unit sphere and separated away from the coordinate hyperplanes, you must choose $T$ to be a $\sqrt\epsilon$-net in $S$. This gives the lower bound; the "worst case" is a uniformly packed set of $n=C(m)\cdot k$ points on the sphere.

UPDATE.

Fritz John theorem, also known as John Ellipsoid Theorem, says that for any origin-symmetric convex body $K\subset\mathbb R^m$, there is an ellipsoid $E$ (also centered at the origin) such that $E\subset K\subset\sqrt m E$. (There is a non-symmetric variant as well but the constant is worse.) The linear transformation that I used just sends $E$ to the unit ball. There are lecture notes about John ellipsoid here and probably in many other sources.

Comparing scaling distance (see also Banach-Mazur distance) and Hausdorff distance between convex bodies is based on the following. The scaling distance is determined by the worst ratio of the support functions of the two bodies, and the Hausdorff distance is the maximum difference between the support functions. Once you captured the bodies between two balls, you can compare relative and absolute difference. This should be explained in any reasonable textbook in convex geometry; unfortunately I'm not an expert in textbooks, especially English-language ones.

By "packing argument" I mean variants of the following argument showing that for any $\epsilon$, any subset $S$ of the unit ball in $\mathbb R^m$ contains an $\epsilon$-net of cardinality at most $(1+2/\epsilon)^m$. Take a maximal $\epsilon$-separated subset $T$ of $S$, it is always an $\epsilon$-net. Since $T$ is $\epsilon$-separated, the balls of radius $\epsilon/2$ centered at the points of $T$ are disjoint, hence the sum of their volumes is no greater than the volume of the $(1+\epsilon/2)$-ball that contains them all. Writing the volume of an $r$-ball as $c(m)\cdot r^m$ yields the result. This argument gives a rough estimate $$ \epsilon \le (2\sqrt m+1) k^{-1/m} $$ in the original problem (up to errors in my quick computations). To improve the exponent one can consider the $(m-1)$-dimensional surface of $P$ rather that the whole ball.