  Given a matrix $\mathbf{A} \in \mathbb{R}^{k \times n}$, a partitioning of
$[k]$ into groups $S_1,\dots,S_m$, an outer norm $p$, and a collection of inner
norms such that either $p \ge 1$ and $p_1,\dots,p_m \ge 2$ or $p_1=\dots=p_m=p
\ge 1/\log n$, we prove that there is a sparse weight vector $\mathbf{\beta}
\in \mathbb{R}^{m}$ such that $\sum_{i=1}^m \beta_i \cdot
\|\mathbf{A}_{S_i}\mathbf{x}\|_{p_i}^p \approx_{1\pm\varepsilon} \sum_{i=1}^m
\|\mathbf{A}_{S_i}\mathbf{x}\|_{p_i}^p$, where the number of nonzero entries of
$\mathbf{\beta}$ is at most $O_{p,p_i}(\varepsilon^{-2}n^{\max(1,p/2)}(\log
n)^2(\log(n/\varepsilon)))$. When $p_1\dots,p_m \ge 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 prove
that there exist efficient algorithms to find the sparse weight vector
$\mathbf{\beta}$ in several important regimes of $p$ and $p_1,\dots,p_m$.
  Our main technical contribution is a substantial generalization of the
change-of-measure method that Bourgain, Lindenstrauss, and Milman used to
obtain the analogous result when every group has size $1$. Our generalization
allows one to analyze change of measures beyond those implied by D. Lewis's
original construction, including the measure implied by the block Lewis weights
and natural approximations of this measure.
