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

  • $\begingroup$ I suppose $A\leq A(\epsilon I + B)$ means element-wise inequality? Otherwise, I can't make sense of the question. (But then, why didn't you write condition (1) as $B\ge0$?) I guess the main difficulty stems from requirement (3), which seems to give the problem a rather combinatorial flavour. Without that, it looks like a standard linear programming problem. $\endgroup$ Mar 30 '10 at 15:54
  • $\begingroup$ Do you assume that the elements of $A$ are nonnegative? If not, it may happen that there is no $\epsilon$ at all. $\endgroup$ Mar 30 '10 at 16:50
  • $\begingroup$ @Harald: a statement like $A \le B$ for matrices $A$ and $B$ often means that the matrix $A-B$ is non-negative definite. $\endgroup$ Mar 30 '10 at 22:32
  • $\begingroup$ Yes, I meant element-wise inequality and assume that A is nonnegative. I will clarify these points on the problem statement. $\endgroup$
    – Danu
    Mar 31 '10 at 4:03

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.


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.

  • $\begingroup$ Thank you for you answer! Quick questions for now: 1. What is $c(m)$ and $C(m)$? Are they some constants that depend on $m$? 2. Could you recommend a place where I can find out more about Fritz John's theorem? The argument seems to be correct to me but I will have to digest and work out some parts more before asking you some questions. (I don't know anything about $\epsilon/\sqrt m$ net and what the "standard packing argument" actually is.) Hope you don't mind answering some questions after that. Thank you! $\endgroup$
    – Danu
    Mar 31 '10 at 4:16
  • $\begingroup$ Just regarding Q2: typing "Fritz John theorem" turns up plenty of results. That theorem is a well-established part of convex geometry. It might help your question to get fuller answers if you say something about your mathematical background/experience, so that they don't talk past you or vice versa $\endgroup$
    – Yemon Choi
    Mar 31 '10 at 4:30
  • 1
    $\begingroup$ Yes $C(m)$ and $c(m)$ are constants depending on $m$ that I did not bother to compute. The proof assumes some background in convex geometry. I'll add some explanations so you can dig it out. $\endgroup$ Mar 31 '10 at 9:04
  • $\begingroup$ Thank you for clarification. Now I understand the whole argument. So I guess if one can show that the size of $\epsilon$-net is (roughly) $(1+2/\epsilon)^{(m-1)/2}$ instead of $(1+2/\epsilon)^{m-1}$ then one can show the upper bound $k^{-2/(m-1)}$ which matches the lower bound? (Note: I ignore the constants.) Is this possible? $\endgroup$
    – Danu
    Mar 31 '10 at 15:00
  • $\begingroup$ No, you generally cannot find an $\epsilon$-net that small. But the subset does not have to be an $\epsilon$-net. On the sphere, being a $\sqrt\epsilon$-net is sufficient, and I believe there is something similar on any convex surface. $\endgroup$ Mar 31 '10 at 15:46

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.