Sparsifying Sums of Norms
share
For any norms N_1,…,N_m on ℝ^n and N(x) := N_1(x)+⋯+N_m(x), we show there is a sparsified norm Ñ(x) = w_1 N_1(x) + ⋯ + w_m N_m(x) such that |N(x) - Ñ(x)| ≤ϵ N(x) for all x ∈ℝ^n, where w_1,…,w_m are non-negative weights, of which only O(ϵ^-2 n log(n/ϵ) (log n)^2.5 ) are non-zero. Additionally, we show that 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 N_i(x), assuming that N(x) is poly(n)-equivalent to the Euclidean norm. 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.
READ FULL TEXT