linear algebra - Matrix approximation

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

If $ngg kgg 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 $Tsubset 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 $vin 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)=Xcup -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 $sqrtepsilon$-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 $Ksubsetmathbb R^m$, there is an ellipsoid $E$ (also centered at the origin) such that $Esubset Ksubsetsqrt 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 (2sqrt 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.