The Change-of-Measure Method, Block Lewis Weights, and Approximating Matrix Block Norms

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.