Sparsifying sums of norms

MaRDI QIDQ6436737zbMATH OpenFDO

Authors Arun Jambulapati, James R. Lee, Yang-Peng Liu, Aaron Sidford

Publication date 15 May 2023

Abstract: For any norms $N_1,ldots,N_m$ on $mathbb{R}^n$ and $N(x):=N_1(x)+cdots+N_m(x)$, we show there is a sparsified norm $ildeN(x)=w_1{N}_1(x)+cdots+w_m{N}_m(x)$ such that $|N(x)-ildeN(x)|leqepsilonN(x)$ for all $xinmathbb{R}^n$, where $w_1,ldots,w_m$ are non-negative weights, of which only $O(epsilo{n}^{-2}nlog(n/epsilon)(logn{)}^{2.5})$ are non-zero. Additionally, we show that such weights can be found with high probability in time $O(m(logn{)}^{O(1)}+mathrmpoly(n))T$, where $T$ is the time required to evaluate a norm $N_i(x)$, assuming that $N(x)$ is $mathrmpoly(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 $p$th powers of norms when the sum is $p$-uniformly smooth.

This page was built for publication: Sparsifying sums of norms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6436737)