Given a matrix A ∈ ℝn×d, a partitioning of [n] into groups S1,…, Sm, an outer norm p, and inner norms such that either p ≥ 1 and p1,. ..,pm ≥ 2 or p1 = · · · = pm = p ≥ 1/ log d, we prove that there is a sparse weight vector ß ∈ ℝm such that , where the number of nonzero entries of ß is at most . When p1 …,pm ≥ 2, this weight vector arises from an importance sampling procedure based on the block Lewis weights, a recently proposed generalization of Lewis weights. Additionally, we give efficient algorithms to find the sparse weight vector ß in several regimes of p and p1,…, pm. Our results imply an algorithm for minimizing sums of Euclidean norms in linear system solves, improving over the previously known iteration complexity when m » d.

We present polylogarithmic approximation algorithms for variants of the Shortest Path, Group Steiner Tree, and Group ATSP problems with vector costs. In these problems, each edge e has a vector cost c_e ∈ ℝ_{≥0}^𝓁. For a feasible solution - a path, subtree, or tour (respectively) - we find the total vector cost of all the edges in the solution and then compute the 𝓁_p-norm of the obtained cost vector (we assume that p ≥ 1 is an integer). Our algorithms for series-parallel graphs run in polynomial time and those for arbitrary graphs run in quasi-polynomial time. To obtain our results, we introduce and use new flow-based Sum-of-Squares relaxations. We also obtain a number of hardness results.

We give near-optimal algorithms for computing an ellipsoidal rounding of a convex polytope whose vertices are given in a stream. The approximation factor is linear in the dimension (as in John's theorem) and only loses an excess logarithmic factor in the aspect ratio of the polytope. Our algorithms are nearly optimal in two senses: first, their runtimes nearly match those of the most efficient known algorithms for the offline version of the problem. Second, their approximation factors nearly match a lower bound we show against a natural class of geometric streaming algorithms. In contrast to existing works in the streaming setting that compute ellipsoidal roundings only for centrally symmetric convex polytopes, our algorithms apply to general convex polytopes. We also show how to use our algorithms to construct coresets from a stream of points that approximately preserve both the ellipsoidal rounding and the convex hull of the original set of points.

We give efficient deterministic one-pass streaming algorithms for finding an ellipsoidal approximation of a symmetric convex polytope. The algorithms are near-optimal in that their approximation factors differ from that of the optimal offline solution only by a factor sub-logarithmic in the aspect ratio of the polytope.