Sparsifying sums of norms

For any norms N1,ldots,Nm on ℝn and N(x) := N1(x)+cdots+Nm(x), we show there is a sparsified norm tildeN(x) = w1 N1(x) + cdots + wm Nm(x) such that |N(x) - tildeN(x)| ≤ ε N(x) for all x ∈ ℝn, where w1,ldots,wm are non-negative weights, of which only O(ε-2 n log(n/ε) (log n)2.5 ) are non-zero. Additionally, if N is poly(n)-equivalent to the Euclidean norm on ℝn, then such weights can be found with high probability in time O(m (log n)O(1) + poly(n)) T, where T is the time required to evaluate a norm Ni. This immediately yields analogous statements for sparsifying sums of symmetric submodular functions. More generally, we show how to sparsify sums of pth powers of norms when the sum is p-uniformly smooth.