Sparsifying sums of norms

Abstract

For any norms $N_1,\dots ,N_m$ on ${\mathbb{R}}^n$ and $N(x):=N_1(x)+\cdots +N_m(x)$, we show there is a sparsified norm $\tilde{N}(x)=w_1{N}_1(x)+\cdots +w_m{N}_m(x)$ such that $|N(x)-\tilde{N}(x)|\le \epsilon N(x)$ for all $x\in {\mathbb{R}}^n$, where $w_1,\dots ,w_m$ are non-negative weights, of which only $O({\epsilon }^{-2}n\log (n/\epsilon )(\log n{)}^{2.5})$ are non-zero. Additionally, if $N$ is $\mathrm{poly}(n)$-equivalent to the Euclidean norm on ${\mathbb{R}}^n$, then such weights can be found with high probability in time $O(m(\log n{)}^{O(1)}+\mathrm{poly}(n))T$, where $T$ is the time required to evaluate a norm $N_i$. This immediately yields analogous statements for sparsifying sums of symmetric submodular functions. More generally, we show how to sparsify sums of $p$th powers of norms when the sum is $p$-uniformly smooth.