# Sharper Bounds for $\ell_{p}$ Sensitivity Sampling††thanks: Our sensitivity
sampling results for $p\in[1,2)$ are subsumed by an earlier sharper result of
Chen–Derezinski [CD21], which shows that the sensitivity scores upper bound
Lewis weights up to a factor of $d^{1-p/2}$, which implies a sampling
complexity bound of $\tilde{O}(\varepsilon^{-2}d^{1-p/2}\mathfrak{S})$. We
refer to Section 1.1 as well as the recent work of [MO23] for more details.

David P. Woodruff
Carnegie Mellon University
<EMAIL_ADDRESS>Taisuke Yasuda
Carnegie Mellon University
<EMAIL_ADDRESS>
###### Abstract

In large scale machine learning, _random sampling_ is a popular way to
approximate datasets by a small representative subset of examples. In
particular, _sensitivity sampling_ is an intensely studied technique which
provides provable guarantees on the quality of approximation, while reducing
the number of examples to the product of the _VC dimension_ $d$ and the _total
sensitivity_ $\mathfrak{S}$ in remarkably general settings. However,
guarantees going beyond this general bound of $\mathfrak{S}d$ are known in
perhaps only one setting, for _$\ell_{2}$ subspace embeddings_, despite
intense study of sensitivity sampling in prior work. In this work, we show the
first bounds for sensitivity sampling for $\ell_{p}$ subspace embeddings for
$p>2$ that improve over the general $\mathfrak{S}d$ bound, achieving a bound
of roughly $\mathfrak{S}^{2-2/p}$ for $2<p<\infty$. Furthermore, our
techniques yield further new results in the study of sampling algorithms,
showing that the _root leverage score sampling_ algorithm achieves a bound of
roughly $d$ for $1\leq p<2$, and that a combination of leverage score and
sensitivity sampling achieves an improved bound of roughly
$d^{2/p}\mathfrak{S}^{2-4/p}$ for $2<p<\infty$. Our sensitivity sampling
results yield the best known sample complexity for a wide class of structured
matrices that have small $\ell_{p}$ sensitivity.

##  1 Introduction

In typical large scale machine learning problems, one encounters a dataset
represented by an $n\times d$ matrix $\mathbf{A}$, consisting of $d$ features
and a large number $n\gg d$ of training examples. While an extremely large $n$
can cause various data analytic tasks to be intractable, it is often the case
that not all $n$ training examples are necessary, and _random sampling_ can
effectively reduce the number of training examples while approximately
preserving the information necessary for downstream prediction tasks.

Uniform sampling is perhaps the simplest instance of this idea that is often
used in practice. However, uniform sampling can lead to significant
information loss when there are a small number of important training examples
that must be kept under sampling. Thus, recent work, both in theory [LS10,
FL11] and in practice [KF17, JG18], has focused on _importance sampling_
methods that sample more important examples with higher probability.

In this work, we focus on the use of importance sampling techniques for
approximating objective functions for empirical risk minimization problems.
Consider an objective function $f:X\to\mathbb{R}_{\geq 0}$ of the form of a
sum along the coordinates, i.e.,

$f(\mathbf{x})=\sum_{i=1}^{n}f_{i}(\mathbf{x}),$

where $X$ is some domain set and $f_{i}:X\to\mathbb{R}_{\geq 0}$ are non-
negative loss functions for $i\in[n]=\\{1,2,\ldots,n\\}$. Then, we seek
algorithms that sample a subset $S\subseteq[n]$ and weights $\mathbf{w}_{i}$
for $i\in S$ such that, with high probability, the function

$\tilde{f}(\mathbf{x})\coloneqq\sum_{i\in S}\mathbf{w}_{i}f_{i}(\mathbf{x})$

satisfies

$\mbox{for every $\mathbf{x}\in X$,
}\qquad\tilde{f}(\mathbf{x})=(1\pm\varepsilon)f(\mathbf{x})$ (1)

for some accuracy parameter $0<\varepsilon<1$. We will also refer to the
$\varepsilon$ parameter as the _sampling error_. Note then that if $\lvert
S\rvert\ll n$, then $\tilde{f}$ can be used as a surrogate objective function
in downstream applications that can be processed much more efficiently than
$f$ itself.

##### Sensitivity Sampling.

The _sensitivity sampling_ framework, introduced by [LS10, FL11], provides one
method of achieving guarantees of the form of (1). In this framework, one
first computes111While computing sensitivity scores exactly is often
inefficient, efficiently computable approximations exist and suffice in many
cases. _sensitivity scores_ of each coordinate $i\in[n]$:

$\boldsymbol{\sigma}_{i}\coloneqq\sup_{\mathbf{x}\in
X}\frac{f_{i}(\mathbf{x})}{\sum_{j=1}^{n}f_{j}(\mathbf{x})}.$

Then, each $i\in[n]$ is independently sampled with probability $p_{i}$
proportional to $\boldsymbol{\sigma}_{i}$, and the sampled row is assigned a
weight of $1/p_{i}$. It is easy to see that this preserves the objective
function $f(\mathbf{x})$ in expectation for every $\mathbf{x}\in X$.
Furthermore, it can be shown that sampling
$\tilde{O}(\varepsilon^{-2}\mathfrak{S}d)$ rows provides a
$(1\pm\varepsilon)$-factor approximation to the objective function [BFL16,
FSS20], where $\mathfrak{S}=\sum_{i=1}^{n}\boldsymbol{\sigma}_{i}$ is known as
the _total sensitivity_ and $d$ is the VC dimension of an associated set
system.

##### Sampling Algorithms for $\ell_{p}$ Linear Regression.

We now turn to sampling algorithms for _$\ell_{p}$ linear regression_, which
is the main problem of study of this work. Consider an input matrix
$\mathbf{A}\in\mathbb{R}^{n\times d}$ with $n$ rows
$\mathbf{a}_{i}\in\mathbb{R}^{d}$, a label vector
$\mathbf{b}\in\mathbb{R}^{n}$, and $1\leq p<\infty$. We then seek to minimize

$f(\mathbf{x})=\sum_{i=1}^{n}\left\lvert\left\langle\mathbf{a}_{i},\mathbf{x}\right\rangle-\mathbf{b}_{i}\right\rvert^{p}=\left\lVert\mathbf{A}\mathbf{x}-\mathbf{b}\right\rVert_{p}^{p}.$

Note that this problem is in the form of an empirical risk minimization
problem as discussed previously, with
$f_{i}(\mathbf{x})=\left\lvert\left\langle\mathbf{a}_{i},\mathbf{x}\right\rangle-\mathbf{b}_{i}\right\rvert^{p}$
and $X=\mathbb{R}^{d}$. Furthermore, in the case of $\ell_{p}$ regression, we
may use the scale invariance of the $\ell_{p}$ norm to fold the weights
$\mathbf{w}_{i}$ into the objective $f_{i}$, so we can write the sampling
procedure as a diagonal map:

######  Definition 1.1 ($\ell_{p}$ Sampling Matrix).

Let $1\leq p<\infty$. A random diagonal matrix
$\mathbf{S}\in\mathbb{R}^{n\times n}$ is a _random $\ell_{p}$ sampling matrix
with sampling probabilities $\\{q_{i}\\}_{i=1}^{n}$_ if for each $i\in[n]$,
the $i$th diagonal entry is independently set to be

$\mathbf{S}_{i,i}=\begin{cases}1/q_{i}^{1/p}&\text{with probability
$q_{i}$}\\\ 0&\text{otherwise}\end{cases}$

Our goal then is to compute probabilities $\\{p_{i}\\}_{i=1}^{n}$ such that
the associated $\ell_{p}$ random sampling matrix $\mathbf{S}$ satisfies

$\mbox{for every
$\mathbf{x}\in\mathbb{R}^{d}$,}\quad\left\lVert\mathbf{A}\mathbf{x}-\mathbf{b}\right\rVert_{p}^{p}=(1\pm\varepsilon)\left\lVert\mathbf{S}\mathbf{A}\mathbf{x}-\mathbf{S}\mathbf{b}\right\rVert_{p}^{p}$

Note that we may in fact also assume that $\mathbf{b}=0$, since we can append
$\mathbf{b}$ to be one of the columns of $\mathbf{A}$. Thus, our problem is to
compute probabilities $\\{p_{i}\\}_{i=1}^{n}$ satisfying

$\mbox{for every
$\mathbf{x}\in\mathbb{R}^{d}$,}\quad\left\lVert\mathbf{S}\mathbf{A}\mathbf{x}\right\rVert_{p}^{p}=(1\pm\varepsilon)\left\lVert\mathbf{A}\mathbf{x}\right\rVert_{p}^{p},$
(2)

which is known as an _$\ell_{p}$ subspace embedding_ of $\mathbf{A}$.

We introduce the following notation for sensitivity sampling when specifically
applied to $\ell_{p}$ subspace embeddings:

######  Definition 1.2 ($\ell_{p}$ sensitivities).

Let $\mathbf{A}\in\mathbb{R}^{n\times d}$ and $p\geq 1$. Then, for each
$i\in[n]$, we define the _$i$ th $\ell_{p}$ sensitivity_ to be

$\boldsymbol{\sigma}_{i}^{p}(\mathbf{A})\coloneqq\sup_{\mathbf{x}\in\mathbb{R}^{d},\mathbf{A}\mathbf{x}\neq
0}\frac{\lvert[\mathbf{A}\mathbf{x}](i)\rvert^{p}}{\left\lVert\mathbf{A}\mathbf{x}\right\rVert_{p}^{p}}$

and the _total $\ell_{p}$ sensitivity_ to be
$\mathfrak{S}^{p}(\mathbf{A})\coloneqq\sum_{i=1}^{n}\boldsymbol{\sigma}_{i}^{p}(\mathbf{A})$.

Note that the calculation of $\ell_{p}$ sensitivities can be formulated as an
$\ell_{p}$ regression problem, and can be computed efficiently using recent
developments in algorithms for $\ell_{p}$ regression. Indeed, it is easy to
see that

$\frac{1}{\boldsymbol{\sigma}_{i}^{p}(\mathbf{A})}=\min_{[\mathbf{A}\mathbf{x}](i)=1}\left\lVert\mathbf{A}\mathbf{x}\right\rVert_{p}^{p},$

which can be efficiently approximated to high precision in nearly matrix
multiplication time [AKPS19, APS19, AS20].

For $p=2$, the $\ell_{p}$ sensitivities are exactly equal to the _leverage
scores_.

######  Definition 1.3 (Leverage scores).

Let $\mathbf{A}\in\mathbb{R}^{n\times d}$. Then, for each $i\in[n]$, we define
the _$i$ th leverage score_ to be
$\boldsymbol{\tau}_{i}(\mathbf{A})\coloneqq\boldsymbol{\sigma}_{i}^{2}(\mathbf{A})$.

For $\ell_{p}$ subspace embeddings, it is known that the total sensitivity is
at most $d$ for $p\leq 2$ and at most $d^{p/2}$ for $p>2$, where $d$ is the
dimension. Thus, sensitivity sampling applies in this setting, and has indeed
been successfully applied in prior work [BDM+20, BHM+21]. There are also other
sampling schemes, based on Lewis weights, which we discuss more below.

For $p=2$, which corresponds to the standard least squares regression problem,
it has long been known that sensitivity sampling, known as _leverage score
sampling_ in this case, yields $\ell_{2}$ subspace embeddings (2) with nearly
optimal sample complexity of444We write $\tilde{O}(f)$ to denote
$f\operatorname{poly}\log f$. $\tilde{O}(\varepsilon^{-2}d)$ [Mah11]. However,
it is also known that the total sensitivity $\mathfrak{S}$ is exactly $d$ in
this setting, and the dimension is also $d$. Thus, in the natural setting of
$\ell_{2}$ subspace embeddings, the bound of $\mathfrak{S}d=d^{2}$ for
sensitivity sampling is quadratically loose in the analysis. However, to the
best of our knowledge, no bound which improves over the general bound of
$\mathfrak{S}d$ specifically for sensitivity sampling is known in any other
setting. We thus arrive at the central question of our work:

######  Question 1.4.

How many samples are necessary for sensitivity sampling to output an
$\ell_{p}$ subspace embedding (2)?

###  1.1 Our Contributions

For $1\leq p<2$, an improved upper bound on the sample complexity of
$\ell_{p}$ sensitivity sampling is implicit in the work of Chen and Derezinski
[CD21]. For this range of $p$, this work shows that the sensitivity scores are
related up to a $d^{1-p/2}$ factor to _Lewis weights_ [Lew78, BLM89, LT91,
CP15, WY23], which are sampling scores known to achieve a sample complexity of
$\tilde{O}(\varepsilon^{-2}d)$ for the problem of sampling $\ell_{p}$ subspace
embeddings for $1\leq p<2$. Then by using sampling probabilities that are a
$d^{1-p/2}$ factor larger than the sensitivity scores, we can sample rows with
probability at least the Lewis weights, which implies a sampling complexity of
$\tilde{O}(\varepsilon^{-2}\mathfrak{S}d^{1-p/2})$ for sensitivity sampling.
The regime of $1\leq p<2$ is, however, perhaps less interesting, as Lewis
weight sampling already achieves nearly optimal bounds for any rank $d$
matrix. For the more interesting case of $2<p<\infty$, such a relationship
between the Lewis weights and the sensitivity scores is not known, and
furthermore, relating to Lewis weights is not as useful since the sample
complexity for Lewis weight sampling scales as
$\tilde{O}(\varepsilon^{-2}d^{p/2})$, even if the total sensitivity
$\mathfrak{S}$ is much less than $d^{p/2}$.

In this work, we make progress towards resolving Question 1.4 by obtaining the
first bounds for sensitivity sampling that go beyond the general
$\mathfrak{S}d$ bound for $2<p<\infty$.

######  Theorem 1.5 (Informal Restatement of Theorem 7.2 and Theorem 7.4).

Let $1\leq p<\infty$ and let $\mathbf{A}\in\mathbb{R}^{n\times d}$. Let
$\alpha>0$ and let
$q_{i}=\min\\{1,1/n+\boldsymbol{\sigma}_{i}^{p}(\mathbf{A})/\alpha\\}$ for
$i\in[n]$. Then, there is an $\alpha$ such that the random $\ell_{p}$ sampling
matrix $\mathbf{S}$ with sampling probabilities $\\{q_{i}\\}_{i=1}^{n}$
satisfies (2) and samples at most $m$ rows with probability at least
$1-1/\operatorname{poly}(n)$, with

$m=\begin{dcases}\frac{\mathfrak{S}^{p}(\mathbf{A})^{2/p}}{\varepsilon^{2}}\operatorname{poly}\log
n&1\leq p<2\\\
\frac{\mathfrak{S}^{p}(\mathbf{A})^{2-2/p}}{\varepsilon^{2}}\operatorname{poly}\log
n&2<p<\infty\end{dcases}$

For $1\leq p<2$, our techniques give a slightly weaker bound of
$\varepsilon^{-2}\mathfrak{S}^{p}(\mathbf{A})^{2/p}\operatorname{poly}\log n$,
which is looser than the bound of
$\varepsilon^{-2}d^{1-2/p}\mathfrak{S}^{p}(\mathbf{A})\operatorname{poly}\log
n$ obtained by [CD21]. On the other hand, our techniques completely avoid the
notion of Lewis weights, and thus may prove to be useful in other sensitivity
sampling settings, where it is more difficult to define analogous weights.

For $1\leq p<2$, we show that our bound of Theorem 1.5 (as well as that of
[CD21]) is in fact tight, in the sense that there exist matrices such that, up
to logarithmic factors, $\mathfrak{S}^{p}(\mathbf{A})^{2/p}$ samples are
necessary to obtain $\ell_{p}$ subspace embeddings. We show this by showing
that random matrices have a total sensitivity of at most
$\mathfrak{S}^{p}(\mathbf{A})=\tilde{O}(d^{p/2})$, which implies the claim
since $d$ rows are necessary to even maintain the rank.

######  Theorem 1.6.

Let $1\leq p<2$. Let $n=d^{O(p)}$ be large enough, and let $\mathbf{A}$ be a
random $n\times d$ standard Gaussian matrix. Then, with probability at least
$2/3$, $\mathfrak{S}^{p}(\mathbf{A})\leq O(d\log d)^{p/2}$.

Furthermore, we show the first bounds showing that the total $\ell_{p}$
sensitivity cannot be any smaller than the construction in Theorem 1.6, up to
logarithmic factors:

######  Theorem 1.7.

Let $\mathbf{A}\in\mathbb{R}^{n\times d}$ and $1\leq p<\infty$. Then,

$\mathfrak{S}^{p}(\mathbf{A})\geq\begin{cases}d/2&p>2\\\
d^{p/2}/2&p<2\end{cases}$

##### Comparison to $\ell_{p}$ Lewis Weight Sampling.

We now compare our results to the well-known _$\ell_{p}$ Lewis weight
sampling_ technique, which yields nearly optimal bounds for $\ell_{p}$
subspace embeddings for matrices with worst-case total $\ell_{p}$ sensitivity
[CP15, WY23]. More specifically, it is known that the total $\ell_{p}$
sensitivity is at most $d$ for $p<2$ and at most $d^{p/2}$ for $p>2$ for all
matrices $\mathbf{A}\in\mathbb{R}^{n\times d}$, and $\ell_{p}$ Lewis weight
sampling provides a way to reduce the number of rows to at most roughly
$d^{1\lor(p/2)}$ rows555We write $a\lor b$ to denote the maximum of $a$ and
$b$. for all matrices $\mathbf{A}$:

######  Theorem 1.8 ($\ell_{p}$ Lewis weight sampling).

Let $\mathbf{A}\in\mathbb{R}^{n\times d}$ and $p>0$. Let $\mathbf{S}$ be a
random $\ell_{p}$ sampling matrix with sampling probabilities
$\\{q_{i}\\}_{i=1}^{n}$ proportional to the $\ell_{p}$ Lewis weights. Then,
$\mathbf{S}$ samples $O(\varepsilon^{-2}d^{1\lor(p/2)}(\log
d)^{2}\log(d/\varepsilon))$ rows and satisfies (2).

In particular, $\ell_{p}$ Lewis weight sampling yields better sampling
complexity bounds than our Theorem 1.5 when $p<2$ or when the $\ell_{p}$ total
sensitivity $\mathfrak{S}^{p}(\mathbf{A})$ is close to $d^{p/2}$. However, our
results on $\ell_{p}$ sensitivity sampling have a number of advantages over
the existing $\ell_{p}$ Lewis weight sampling results. First, Lewis weight
sampling, to the best of our knowledge, is not known to admit bounds better
than $d^{p/2}$ for matrices with very small total sensitivity
$\mathfrak{S}^{p}(\mathbf{A})\ll d^{p/2}$ for $p>2$. Thus, for matrices with
substantially smaller total sensitivity, $\ell_{p}$ sensitivity sampling
yields far improved bounds. We illustrate a number of such applications below.
Second, sensitivity sampling generalizes to sampling problems beyond
$\ell_{p}$ subspace embeddings and has been applied to subspace embeddings for
general $M$-estimators and Orlicz norms [CW15a, CW15b, TMF20, MMWY22],
logistic regression [MSSW18] and other generalized linear models [MOP22], as
well as general shape fitting problems including clustering and subspace
approximation [HV20] and projective clustering [VX12]. Thus, our techniques
may be useful for improving the analyses of a broad range of sampling
problems.

##### Other Sampling Algorithms.

In addition to $\ell_{p}$ sensitivity sampling, our techniques yield other new
results on sampling algorithms for $\ell_{p}$ subspace embeddings.

Our next result is a new analysis of _root leverage score sampling_ , which is
a popular method for efficiently computing upper bounds to sensitivity scores
for loss functions of at most quadratic growth, including $\ell_{p}$ losses
for $1\leq p<2$, the Huber loss, and the logistic loss [CW15b, MSSW18, GPV21].
In this technique, the $p_{i}$ are set proportionally to the _square root_ of
the $\ell_{2}$ leverage scores (Definition 1.3). While the sum of the root
leverage scores can be as large as $\sqrt{nd}$, this sampling procedure can be
recursively applied for $O(\log\log n)$ iterations to reduce the sample
complexity to $\operatorname{poly}(d)$.

As with sensitivity sampling, the only previously known analyses of root
leverage score sampling proceed by a naïve union bound, which can only reduce
the number of samples to $d^{2}$, which is loose by a $d$ factor. Our
techniques for analyzing sensitivity sampling can be modified to show that
root leverage score sampling in fact leads to a _nearly optimal_ number of
samples:

######  Theorem 1.9 (Informal Restatement of Theorem 7.6 and Theorem 7.8).

Let $1\leq p<2$ and let $\mathbf{A}\in\mathbb{R}^{n\times d}$. Let $\alpha>0$
and let $p_{i}=\min\\{1,\boldsymbol{\tau}_{i}(\mathbf{A})^{p/2}/\alpha\\}$ for
$i\in[n]$. Then, there is an $\alpha$ such that the random $\ell_{p}$ sampling
matrix $\mathbf{S}$ with sampling probabilities $\\{p_{i}\\}_{i=1}^{n}$
satisfies (2) and samples at most $m$ rows with probability at least
$1-1/\operatorname{poly}(n)$, with

$m=\frac{n^{1-p/2}d^{p/2}}{\varepsilon^{2}}\operatorname{poly}\log n.$

Recursively applying this result gives a matrix $\mathbf{S}$ satisfying (2)
with at most $m$ rows, for

$m=\frac{d}{\varepsilon^{4/p}}\operatorname{poly}\log n.$

Our analysis of root leverage score sampling provides a promising direction
towards resolving the problem of designing nearly optimal sampling algorithms
for preserving subspaces under the _Huber loss_ , which has been raised as an
important question on sampling algorithms in a number of works [AS20, GPV21,
MMWY22] for its applications in Huber regression and fast algorithms for
$\ell_{p}$ regression. Here, the best known upper bound is a sampling
algorithm reducing the number of rows to roughly666A polylogarithmic
dependence on $n$ is necessary and sufficient here, but we omit this from our
discussion for simplicity. $d^{4-2\sqrt{2}}\approx d^{1.172}$, whereas $d$ is
conjectured to be possible [MMWY22]. Root leverage scores are known to upper
bound the sensitivities for the Huber loss [CW15a, CW15b, GPV21], so our
Theorem 1.9 suggests that root leverage score sampling may yield a sampling
algorithm reducing the number of samples to $d$ for the Huber loss as well.

We additionally show that by incorporating $\ell_{2}$ leverage scores into
$\ell_{p}$ sensitivity sampling, we can obtain sampling guarantees that
further improve over the guarantee of Theorem 1.5 for $p>2$. We note that our
proof of this result uses a recursive “flattening and sampling” scheme for
this result, rather than a direct sampling result as in our earlier results.

######  Theorem 1.10 (Informal Restatement of Theorem 7.10).

Let $2<p<\infty$ and let $\mathbf{A}\in\mathbb{R}^{n\times d}$. Then, there is
an efficient algorithm which computes a matrix
$\mathbf{S}\in\mathbb{R}^{m\times n}$ satisfying (2), for

$m=\frac{d^{2/p}\mathfrak{S}^{p}(\mathbf{A})^{1-2/p}}{\varepsilon^{2}}\operatorname{poly}\log
n.$

Although Theorem 1.10 does not specifically use sensitivity sampling, to the
best of our knowledge, it is the best known sampling result for $\ell_{p}$
subspace embeddings with small $\ell_{p}$ total sensitivity
$\mathfrak{S}^{p}(\mathbf{A})$.

##### Applications.

We now show several examples in structured regression problems in which our
new sensitivity sampling results give the best known sample complexity results
for $\ell_{p}$ subspace embeddings for $p>2$. We start by presenting a couple
of lemmas which show that certain natural classes of matrices have total
$\ell_{p}$ sensitivity $\ll d^{p/2}$.

The first result is a lemma extracted from a result of [MMM+22] bounding the
total $\ell_{p}$ sensitivity for a sparse perturbation of low rank matrices:

######  Lemma 1.11 (Sensitivity Bounds for Low Rank + Sparse Matrices
[MMM+22]).

Let $\mathbf{A}=\mathbf{K}+\mathbf{S}\in\mathbb{R}^{n\times d}$ for a rank $k$
matrix $\mathbf{K}$ and an $\mathbf{S}$ with at most $s$ nonzero entries per
row. Let $1\leq p<\infty$. Then, $\mathfrak{S}^{p}(\mathbf{A})\leq
d^{s}(k+s)^{p}$.

We provide a self-contained proof in Section 4.3.

In a second example, we show that “concatenated Vandermonde” matrices, which
were studied in, e.g., [ASW13], also have small total $\ell_{p}$ sensitivity.
These matrices naturally arise as the result of applying a polynomial feature
map to a matrix.

######  Definition 1.12 (Vandermonde matrix).

Given a vector $\mathbf{a}\in\mathbb{R}^{n}$, the degree $q$ Vandermonde
matrix $V^{q}(\mathbf{a})\in\mathbb{R}^{n\times(q+1)}$ is defined entrywise as
$V^{q}(\mathbf{a})_{i,j}=\mathbf{a}_{i}^{j}$ for $j=0,1,\dots,q$.

######  Definition 1.13 (Polynomial feature map).

Given a matrix $\mathbf{A}\in\mathbb{R}^{n\times k}$ and an integer $q$, we
define the matrix $V^{q}(\mathbf{A})\in\mathbb{R}^{n\times k(q+1)}$ to be the
horizontal concatenation of the Vandermonde matrices
$V^{q}(\mathbf{A}\mathbf{e}_{1}),V^{q}(\mathbf{A}\mathbf{e}_{2}),\dots,V^{q}(\mathbf{A}\mathbf{e}_{k})$.

We show the following result, proven in Section 4.3.

######  Lemma 1.14 (Sensitivity Bounds for Matrices Under Polynomial Feature
Maps).

Let $\mathbf{A}\in\mathbb{R}^{n\times k}$ and let $q$ be an integer. Let
$1\leq p<\infty$. Then, $\mathfrak{S}^{p}(V^{q}(\mathbf{A}))\leq(pq+1)^{k}$.

This generalizes a result of [MMM+22], which bounds the $\ell_{p}$
sensitivities of a single Vandermonde matrix.

In the low-sensitivity matrices of Lemma 1.11 and Lemma 1.14, it is in fact
possible to apply Lewis weight sampling to obtain sampling bounds that match
these sensitivity bounds, by using the _tensoring trick_ [MMM+22]. However,
when a tiny amount of noise is added to these matrices, then algebraic tricks
such as tensoring break down, and the sensitivity bounds derived from Lewis
weights increase substantially to $d^{p/2}$ for $p>2$. On the other hand,
sensitivity sampling itself is robust with respect to the addition of noise,
as it depends only on norms rather than brittle quantities such as rank.
Indeed, we have the following fact, which we prove in Section 4.4:

######  Lemma 1.15.

Let $\mathbf{A}\in\mathbb{R}^{n\times d}$ be a rank $d$ matrix with minimum
singular value $\sigma_{\min}$. Let $\mathbf{E}\in\mathbb{R}^{n\times d}$ be
an arbitrary perturbation matrix with

$\left\lVert\mathbf{E}\right\rVert_{2}\leq\frac{\sigma_{\min}}{2n^{1+1/p}}.$

Then, $\mathfrak{S}^{p}(\mathbf{A}+\mathbf{E})\leq
2^{p}(\mathfrak{S}^{p}(\mathbf{A})+1)$.

Thus, for small perturbations of structured matrices with small $\ell_{p}$
sensitivity as specified by Lemma 1.15, Theorem 1.5 and Theorem 1.10 give the
tightest known bounds on the sample complexity for $\ell_{p}$ subspace
embeddings. Such perturbations may arise due to roundoff error or finite
precision on a computer, and no prior bounds beating Lewis weight sampling or
the naïve $\mathfrak{S}d$ bound for sensitivity sampling were known for the
applications above.

###  1.2 Other Related Work

The problem of designing sampling algorithms for $\ell_{p}$ subspace
embeddings has a long and rich history, dating back to works in the functional
analysis literature and culminating in the Lewis weight sampling result
[Lew78, Sch87, BLM89, Tal90, LT91, Tal95, SZ01]. More recently, the
theoretical computer science community has studied this problem for its
applications to $\ell_{p}$ linear regression and other empirical risk
minimization problems. The early works of [Cla05, DDH+09] obtained sampling
algorithms for $\ell_{p}$ regression based on sensitivity score upper bounds
given by various constructions of _$\ell_{p}$ well-conditioned bases_ for
$\mathbf{A}$. The theory of Lewis weight sampling was brought to the
theoretical computer science literature by [CP15], and has been improved both
in the computation of the weights [Lee16, FLPS22, JLS22] and sampling
guarantees [WY22, WY23].

##  2 Sampling Error Bounds

We now give a more detailed discussion of our techniques and results. While
our discussion in this section will present most of the major ideas necessary
to prove our new results, all of the full proofs will be deferred to the
appendix due to space considerations.

###  2.1 Prior Approaches

We start by describing the standard proof of the
$\tilde{O}(\varepsilon^{-2}\mathfrak{S}d)$ sample complexity bound for
sensitivity sampling [Sch87]. Using Bernstein bounds, it can be shown that
sampling $O(\varepsilon^{-2}\mathfrak{S}\log\frac{1}{\delta})$ rows preserves
the $\ell_{p}$ norm of a fixed vector $\mathbf{A}\mathbf{x}$ up to a
$(1\pm\varepsilon)$ factor with probability at least $1-\delta$. One can then
consider an _$\varepsilon$ -net_ $N$, which is a set of size roughly
$1/\varepsilon^{d}$ such that any $\ell_{p}$ unit vector
$\mathbf{A}\mathbf{x}$ is $\varepsilon$-close to some
$\mathbf{A}\mathbf{x}^{\prime}\in N$. By a union bound, the norm preservation
guarantee holds simultaneously for every $\mathbf{A}\mathbf{x}^{\prime}\in N$
with constant probability, if we set $\delta=\varepsilon^{d}$. Now for an
arbitrary $\ell_{p}$ unit vector $\mathbf{A}\mathbf{x}$, the norm preservation
guarantee holds for an $\varepsilon$-close point
$\mathbf{A}\mathbf{x}^{\prime}\in N$, which implies the norm preservation
guarantee for $\mathbf{A}\mathbf{x}$ itself by a standard argument. Finally,
scale invariance ensures that the same conclusion holds for all vectors
$\mathbf{A}\mathbf{x}$, rather than just unit vectors.

To improve over this argument, the $\ell_{p}$ Lewis weight sampling technique
was developed in a line of work from the functional analysis literature
[Lew78, BLM89, Tal90, LT91, Tal95], which incorporates _chaining arguments_.
Chaining arguments are a way of improving $\varepsilon$-net arguments by using
a _sequence_ of $\varepsilon$-nets at different “scales”, rather than using a
single scale of $\varepsilon$, and using tighter bounds for net constructions
(i.e., smaller cardinality nets) at larger scales (see, e.g., [Nel16] for a
survey of chaining applications in computer science).

We now delve into a discussion of the overall strategy towards bounding the
_sampling error_ of our $\ell_{p}$ sampling results, which is a random
variable $\Lambda$ depending on $\mathbf{S}$ given by

$\Lambda\coloneqq\sup_{\left\lVert\mathbf{A}\mathbf{x}\right\rVert_{p}=1}\left\lvert\left\lVert\mathbf{S}\mathbf{A}\mathbf{x}\right\rVert_{p}^{p}-1\right\rvert.$
(3)

Note that if $\Lambda\leq\varepsilon$, then
$\left\lVert\mathbf{S}\mathbf{A}\mathbf{x}\right\rVert_{p}^{p}=(1\pm\varepsilon)\left\lVert\mathbf{A}\mathbf{x}\right\rVert_{p}^{p}$
for every $\mathbf{x}\in\mathbb{R}^{d}$. In our discussions in this section,
we will focus on bounding $\Lambda$ in expectation, although our full proofs
in the appendix will bound higher moments of $\Lambda$ to obtain high
probability bounds.

###  2.2 Generalized Chaining Bounds for $\ell_{p}$ Subspace Embeddings

Our main technical lemma towards bounding (3) is a generalization of the
chaining argument framework for Lewis weight sampling, which bounds the
sampling error of $\ell_{p}$ sampling algorithms by the leverage scores and
$\ell_{p}$ sensitivities of the sampled matrix $\mathbf{S}\mathbf{A}$, rather
than by the Lewis weights of $\mathbf{S}\mathbf{A}$.

First, we introduce our sampling bounds obtained by generalizing the chaining
arguments of [BLM89, LT91]. In this result, we obtain the following bound on a
certain Rademacher process, which can be interpreted as the sampling error of
a uniform sampling process, as we describe in Section 2.4.

######  Lemma 2.1 (Rademacher Process Bound, Simplified).

Let $\mathbf{A}\in\mathbb{R}^{n\times d}$ and $1\leq p<\infty$. Let
$\tau\geq\boldsymbol{\tau}_{i}(\mathbf{A})$ and
$\sigma\geq\boldsymbol{\sigma}_{i}^{p}(\mathbf{A})$ for every $i\in[n]$. Let

$E\coloneqq\operatorname*{\mathbf{E}}_{\boldsymbol{\varepsilon}\sim\\{\pm
1\\}^{n}}\sup_{\left\lVert\mathbf{A}\mathbf{x}\right\rVert_{p}=1}\left\lvert\sum_{i=1}^{n}\boldsymbol{\varepsilon}_{i}\left\lvert[\mathbf{A}\mathbf{x}](i)\right\rvert^{p}\right\rvert.$

Then,

$E\leq\begin{cases}O(\tau^{1/2})(\log n)^{3/2}&p<2\\\ O(\tau^{1/2})(\sigma
n)^{1/2-1/p}(\log n)^{3/2}&p>2\end{cases}$

This result follows from a Gaussianization argument (Lemma 7.1), followed by
an application of Dudley’s entropy integral theorem (Theorem 6.2), and then
bounding the entropy integral in Lemma 6.6 and Lemma 6.7.

As we discuss in Section 2.4, Lemma 2.1 will be a key ingredient in bounding
the sampling error in our sensitivity sampling analysis.

###  2.3 Leverage Score and Sensitivity Bounds

In our final argument, Lemma 2.1 will be applied with the matrix $\mathbf{A}$
set to be (a modified version of) the sampled matrix $\mathbf{S}\mathbf{A}$.
Thus, we require a bound on the leverage scores and sensitivities $\tau$ and
$\sigma$ of $\mathbf{S}\mathbf{A}$. In fact, $\sigma$ is naturally bounded by
the $\ell_{p}$ sensitivity sampling algorithm: indeed, if we a priori assume
that
$\left\lVert\mathbf{S}\mathbf{A}\mathbf{x}\right\rVert_{p}^{p}\geq(1/2)\left\lVert\mathbf{A}\mathbf{x}\right\rVert_{p}^{p}$
for every $\mathbf{x}\in\mathbb{R}^{d}$, then
$\boldsymbol{\sigma}_{i}^{p}(\mathbf{S}\mathbf{A})$ is at most

$\sup_{\mathbf{S}\mathbf{A}\mathbf{x}\neq
0}\frac{\left\lvert[\mathbf{S}\mathbf{A}\mathbf{x}](i)\right\rvert^{p}}{\left\lVert\mathbf{S}\mathbf{A}\mathbf{x}\right\rVert_{p}^{p}}\leq
2\sup_{\mathbf{A}\mathbf{x}\neq
0}\frac{1}{p_{i}}\frac{\left\lvert[\mathbf{A}\mathbf{x}](i)\right\rvert^{p}}{\left\lVert\mathbf{A}\mathbf{x}\right\rVert_{p}^{p}}\leq\frac{2\boldsymbol{\sigma}_{i}^{p}(\mathbf{A})}{p_{i}}$
(4)

which is at most $2\alpha$ if
$p_{i}\geq\boldsymbol{\sigma}_{i}^{p}(\mathbf{A})/\alpha$. While this is only
an informal argument, this intuition can be formalized, as we discuss later in
this section.

Next, we require a bound on the leverage scores $\tau$ of
$\mathbf{S}\mathbf{A}$, which is more challenging, as sensitivity sampling
does not directly bound this quantity. To address this problem, we show how to
bound the leverage scores of an arbitrary matrix by the $\ell_{p}$
sensitivities of the matrix. In particular, we show that for $q\geq p$, the
largest $\ell_{q}$ sensitivity bounds the largest $\ell_{p}$ sensitivity.

######  Lemma 2.2 (Monotonicity of Max $\ell_{p}$ Sensitivity).

Let $q\geq p>0$ and $\mathbf{y}\in\mathbb{R}^{n}$. Then,

$\frac{\lVert\mathbf{y}\rVert_{\infty}^{p}}{\left\lVert\mathbf{y}\right\rVert_{p}^{p}}\leq\frac{\left\lVert\mathbf{y}\right\rVert_{\infty}^{q}}{\left\lVert\mathbf{y}\right\rVert_{q}^{q}}.$

We also use an “approximate converse” of the above result:

######  Lemma 2.3 (Reverse Monotonicity of Max $\ell_{p}$ Sensitivity).

Let $q\geq p>0$ and $\mathbf{y}\in\mathbb{R}^{n}$. Then,

$\frac{\left\lVert\mathbf{y}\right\rVert_{\infty}^{q}}{\left\lVert\mathbf{y}\right\rVert_{q}^{q}}\leq\left\lparen\frac{\left\lVert\mathbf{y}\right\rVert_{\infty}^{p}}{\left\lVert\mathbf{y}\right\rVert_{p}^{p}}\right\rparen^{q/p}n^{q/p-1}.$

While these lemmas only apply to the max $\ell_{p}$ sensitivity and are quite
loose when the max $\ell_{p}$ sensitivity can be arbitrary, we use the crucial
fact that the $\ell_{p}$ sensitivities of $\mathbf{S}\mathbf{A}$ are
essentially “flat”, that is, the maximum $\ell_{p}$ sensitivity will be within
a small factor of the _average_ $\ell_{p}$ sensitivity
$\mathfrak{S}^{p}(\mathbf{A})/n$. Thus, Lemma 2.2 and Lemma 2.3 allow us to
bound the leverage scores by the $\ell_{p}$ sensitivities for $p>2$ and $p<2$,
respectively. This idea also allows us to prove Theorem 1.7.

###  2.4 Gaussianization Reduction for Sampling Algorithms

In the works of [BLM89, LT91], a version of Lemma 2.1 tailored to $\ell_{p}$
Lewis weight sampling is used as a part of a recursive sampling algorithm,
where the Rademacher process represents the sampling error of a process that
samples each row $i\in[n]$ with probability $1/2$ and scales the result by
$2$. Indeed, if $\mathbf{S}_{i,i}$ takes the value $0$ or $2^{1/p}$ with
probability $1/2$ each and
$\left\lVert\mathbf{A}\mathbf{x}\right\rVert_{p}^{p}=1$, then
$(\mathbf{S}_{i,i}^{p}-1)$ is a Rademacher variable and

$\left\lVert\mathbf{S}\mathbf{A}\mathbf{x}\right\rVert_{p}^{p}-1=\sum_{i=1}^{n}(\mathbf{S}_{i,i}^{p}-1)\left\lvert[\mathbf{A}\mathbf{x}](i)\right\rvert^{p},$

and thus Lemma 2.1 bounds (3). While this only reduces the number of rows by a
factor of $2$, this process can be applied recursively for $O(\log n)$ rounds
to reduce the number of rows to $\operatorname{poly}(d)$.

However, we instead primarily use Lemma 2.1 in a reduction based on [CP15] for
an algorithm with _one_ round of sampling. In this reduction, we bound the
sampling error (3) by introducing an independent copy $\mathbf{S}^{\prime}$ of
$\mathbf{S}$ and estimate

$\Lambda\leq\operatorname*{\mathbf{E}}\sup_{\left\lVert\mathbf{A}\mathbf{x}\right\rVert_{p}=1}\left\lvert\left\lVert\mathbf{S}\mathbf{A}\mathbf{x}\right\rVert_{p}^{p}-\left\lVert\mathbf{S}^{\prime}\mathbf{A}\mathbf{x}\right\rVert_{p}^{p}\right\rvert$

Because $\mathbf{S}$ and $\mathbf{S}^{\prime}$ are identically distributed,
multiplying each coordinate $i\in[n]$ by a Rademacher variable
$\boldsymbol{\varepsilon}_{i}\sim\\{\pm 1\\}$ does not change the
distribution. Then by applying the triangle inequality, it follows that

$\Lambda\leq 2\operatorname*{\mathbf{E}}_{\boldsymbol{\varepsilon}\sim\\{\pm
1\\}^{n}}\sup_{\left\lVert\mathbf{A}\mathbf{x}\right\rVert_{p}=1}\left\lvert\sum_{i=1}^{n}\boldsymbol{\varepsilon}_{i}\left\lvert[\mathbf{S}\mathbf{A}\mathbf{x}](i)\right\rvert^{p}\right\rvert,$
(5)

which closely resembles Lemma 2.1.

At this point, for each fixing of $\mathbf{S}$, we wish to apply Lemma 2.1
with $\mathbf{A}$ replaced by $\mathbf{S}\mathbf{A}$, with sensitivities
bounded using the idea of (4). However, we cannot a priori assume that
$\left\lVert\mathbf{S}\mathbf{A}\mathbf{x}\right\rVert_{p}^{p}\geq(1/2)\left\lVert\mathbf{A}\mathbf{x}\right\rVert_{p}^{p}$.
To fix this, the idea of [CP15] is to introduce an _auxiliary subspace
embedding_ $\mathbf{S}^{\prime}$ such that $\mathbf{S}^{\prime}\mathbf{A}$
also has $\ell_{p}$ sensitivities bounded by $\alpha$, and _does_ satisfy
$\left\lVert\mathbf{S}^{\prime}\mathbf{A}\mathbf{x}\right\rVert_{p}^{p}=\Theta(1)\left\lVert\mathbf{A}\mathbf{x}\right\rVert_{p}^{p}$
for every $\mathbf{x}\in\mathbb{R}^{d}$. Then, we can apply the result of
Lemma 2.1 to the concatenated matrix

$\mathbf{A}^{\prime}\coloneqq\begin{pmatrix}\mathbf{S}\mathbf{A}\\\
\mathbf{S}^{\prime}\mathbf{A}\end{pmatrix}.$

It can then be shown that the quantity $E$ bounded in Lemma 2.1 indeed bounds
the quantity in (5), and furthermore, we can fix the argument of (4) by
bounding

$\sup_{\mathbf{A}^{\prime}\mathbf{x}\neq
0}\frac{\left\lvert[\mathbf{S}\mathbf{A}\mathbf{x}](i)\right\rvert^{p}}{\left\lVert\mathbf{A}^{\prime}\mathbf{x}\right\rVert_{p}^{p}}\leq\sup_{\mathbf{A}\mathbf{x}\neq
0}\frac{1}{p_{i}}\frac{\left\lvert[\mathbf{A}\mathbf{x}](i)\right\rvert^{p}}{\left\lVert\mathbf{S}^{\prime}\mathbf{A}\mathbf{x}\right\rVert_{p}^{p}}\leq\frac{O(\boldsymbol{\sigma}_{i}^{p}(\mathbf{A}))}{p_{i}}.$

Importantly, we only need to use the existence of $\mathbf{S}^{\prime}$ for
the analysis and thus $\mathbf{S}^{\prime}$ can be constructed in any way,
rather than just by sensitivity sampling.

###  2.5 Construction of Auxiliary $\ell_{p}$ Subspace Embeddings

We now delve into further detail about the other key piece of our analysis,
which is the construction of auxiliary $\ell_{p}$ subspace embeddings
$\mathbf{S}^{\prime}$ which are compatible with the reduction argument in
Section 2.4.

####  2.5.1 Sensitivity Sampling, $p<2$

For our sensitivity sampling result for $p<2$ in Theorem 1.5, we aim to sample
roughly $m=\varepsilon^{-2}\mathfrak{S}^{p}(\mathbf{A})^{2/p}$ rows. We first
briefly sketch the intuition behind this bound. If we sample each row
$i\in[n]$ with probability roughly
$\boldsymbol{\sigma}_{i}^{p}(\mathbf{A})/\alpha$ for an oversampling parameter
$\alpha>0$, then we expect the $\ell_{p}$ sensitivities of
$\mathbf{S}\mathbf{A}$ to be bounded by $\alpha$ according to the informal
reasoning of (4). We then wish to bound the sampling error using Lemma 2.1,
which, combined with the bound on the leverage scores using the sensitivities
in Lemma 2.3, gives a bound of

$\tau\leq\alpha^{2/p}m^{2/p-1}=\alpha\mathfrak{S}^{p}(\mathbf{A}))^{2/p-1}$

by using that $m$ is $\mathfrak{S}^{p}(\mathbf{A})/\alpha$ in expectation.
Since we want this to be at most $\varepsilon^{2}$, we set
$\alpha=\varepsilon^{2}/\mathfrak{S}^{p}(\mathbf{A})^{2/p-1}$, which gives a
bound of $m=\varepsilon^{-2}\mathfrak{S}^{p}(\mathbf{A})^{2/p}$ as claimed.

Now coming back to the formal argument using the auxiliary $\ell_{p}$ subspace
embedding $\mathbf{S}^{\prime}$, we wish to construct a subspace embedding
$\mathbf{S}^{\prime}$ that preserves $\ell_{p}$ norms of
$\mathbf{A}\mathbf{x}$ up to a constant factor, but also has $\ell_{p}$
sensitivities at most $\alpha$, since this is the bound that
$\mathbf{S}\mathbf{A}$ will satisfy. To construct this $\mathbf{S}^{\prime}$,
we proceed by first using Lewis weight sampling (Theorem 1.8) to construct a
$\Theta(1)$-approximate $\ell_{p}$ subspace sampling with $\tilde{O}(d)$ rows.
Importantly, we show that this sampling procedure can only increase the total
$\ell_{p}$ sensitivity by a constant factor (see Lemma 4.1). We then apply a
flattening procedure (see Lemma 4.4), which yields an $\ell_{p}$ isometry with
at most $\mathfrak{S}^{p}(\mathbf{A})/\alpha$ rows such that the sensitivity
of each row is bounded by $\alpha$. Furthermore, because the number of rows
$\mathfrak{S}^{p}(\mathbf{A})/\alpha$ of this auxiliary subspace embedding
$\mathbf{S}^{\prime}$ is at most the bound $m$ that we seek, we can apply the
same reasoning as before using Lemma 2.3 to bound the leverage scores of
$\mathbf{S}^{\prime}\mathbf{A}$ to recover the same bound as that for
$\mathbf{S}\mathbf{A}$. Thus, we obtain our desired construction of the
auxiliary $\ell_{p}$ subspace embedding, allowing the reduction argument as
described in Section 2.4 to go through.

####  2.5.2 Sensitivity Sampling, $p>2$

For our result on sensitivity sampling when $p>2$, the intuition and reasoning
roughly follows the case of $p<2$. However, we must be more careful with the
construction of the auxiliary $\ell_{p}$ subspace embedding, since we cannot
use Lewis weight sampling to construct it; this is because the sample
complexity of $\tilde{O}(d^{p/2})$ for Lewis weight sampling is larger than
our sample complexity bound of
$m=\varepsilon^{-2}\mathfrak{S}^{p}(\mathbf{A})^{2-2/p}$ that we aim for.
Thus, in order to obtain our auxiliary $\ell_{p}$ subspace embedding, we must
essentially achieve the same results that we claim in Theorem 1.5, using an
_alternate construction_ that does not directly use one-shot sensitivity
sampling. For this, we instead revisit the _recursive sampling_ process
mentioned earlier in Section 2.4, which originates from the functional
analysis literature. Here, we first flatten our input matrix using Lemma 4.4
to a matrix with at most $(4/3)n$ rows and $\ell_{p}$ sensitivities at most
$O(\mathfrak{S}^{p}(\mathbf{A})/n)$, and then use Lemma 2.1 directly as the
sampling error bound for a uniform sampling algorithm which samples each row
with probability $1/2$. Note then that overall, we retain $(4/3)(1/2)n=(2/3)n$
rows altogether in expectation after this result, and furthermore, we have a
sampling error of at most $\varepsilon$. Then, because we sample only a
constant fraction of rows after each application of the procedure, it can be
shown that recursively applying this result for $O(\log n)$ iterations
accumulates a total sampling error of $O(\varepsilon\log n)$, while reducing
the number of rows down to
$\varepsilon^{-2}\mathfrak{S}^{p}(\mathbf{A})^{2-2/p}$, which matches the
number of rows that we claim for sensitivity sampling in Theorem 1.5. By
rescaling $\varepsilon$ by an $O(\log n)$ factor, we can obtain a total error
of $\varepsilon$ while only losing polylogarithmic factors in $n$. This is
carried out in Lemma 7.3. Thus, we may again carry out the reduction argument
as described in Section 2.4.

####  2.5.3 Root Leverage Score Sampling, $p<2$

For our root leverage score sampling theorem Theorem 1.9, we take a
conceptually different approach for obtaining the leverage score bound
required in Lemma 2.1. For sensitivity sampling, our idea was to bound the
leverage scores by relating them to the $\ell_{p}$ sensitivities, which were
controlled by the sensitivity sampling process. For root leverage score
sampling, however, the idea is that by sampling by the root leverage scores,
we directly control the _leverage scores_ of the sampled matrix
$\mathbf{S}\mathbf{A}$, rather than the sensitivity scores. Indeed, one can
show that if the sampling probabilities $p_{i}$ satisfy
$p_{i}\geq\boldsymbol{\tau}_{i}(\mathbf{A})^{p/2}/\alpha$, and if
$\left\lVert\mathbf{S}\mathbf{A}\mathbf{x}\right\rVert_{2}^{2}\geq(1/2)\left\lVert\mathbf{A}\mathbf{x}\right\rVert_{2}^{2}$
for every $\mathbf{x}\in\mathbb{R}^{d}$, then the leverage scores of
$\mathbf{S}\mathbf{A}$ are bounded by

$\sup_{\mathbf{S}\mathbf{A}\mathbf{x}\neq
0}\frac{\left\lvert[\mathbf{S}\mathbf{A}\mathbf{x}](i)\right\rvert^{2}}{\left\lVert\mathbf{S}\mathbf{A}\mathbf{x}\right\rVert_{2}^{2}}\leq
2\sup_{\mathbf{A}\mathbf{x}\neq
0}\frac{1}{p_{i}^{2/p}}\frac{\left\lvert[\mathbf{A}\mathbf{x}](i)\right\rvert^{2}}{\left\lVert\mathbf{A}\mathbf{x}\right\rVert_{2}^{2}}\leq
2\frac{\boldsymbol{\tau}_{i}(\mathbf{A})}{p_{i}^{2/p}}$ (6)

which is at most $2\alpha^{2/p}$. However, it is not clear that
$\left\lVert\mathbf{S}\mathbf{A}\mathbf{x}\right\rVert_{2}^{2}\geq(1/2)\left\lVert\mathbf{A}\mathbf{x}\right\rVert_{2}^{2}$
should hold at all, since $\mathbf{S}$ is only a subspace embedding for
$\ell_{p}$ and not $\ell_{2}$. For this intuition to go through, we require an
auxiliary $\ell_{p}$ subspace embedding that preserves both $\ell_{p}$ norms
and $\ell_{2}$ norms, with flat $\ell_{2}$ leverage scores.

To make this argument work, we crucially use the fact that the bound in Lemma
2.1 does not depend polynomially on the number of rows of the input matrix.
Thus, we can afford to construct $\mathbf{S}^{\prime}\mathbf{A}$ to have many
rows, as long as its leverage scores are controlled. Thus, in Lemma 7.5, we
take the approach of constructing an $\ell_{p}$ isometry of $\mathbf{A}$ by
splitting every row $\mathbf{a}_{i}$ into $k$ copies of
$\mathbf{a}_{i}/k^{1/p}$, where we will set $k=1/\alpha$. Note then that after
splitting, every row contains at most a $1/k$ fraction of the $\ell_{2}$ mass,
so the $\ell_{2}$ leverage scores are all at most $\alpha$ (in fact, all
$\ell_{q}$ sensitivities for any $q$ are at most $\alpha$). Furthermore,
crucially, the $\ell_{2}$ norm will be preserved up to a factor of
$\alpha^{1/p-1/q}$. Then altogether, we can fix (6) and instead bound

$\sup_{\mathbf{S}\mathbf{A}\mathbf{x}\neq
0}\frac{\left\lvert[\mathbf{S}\mathbf{A}\mathbf{x}](i)\right\rvert^{2}}{\left\lVert\mathbf{A}^{\prime}\mathbf{x}\right\rVert_{2}^{2}}\leq
2\sup_{\mathbf{A}\mathbf{x}\neq
0}\frac{1}{p_{i}^{2/p}}\frac{\left\lvert[\mathbf{A}\mathbf{x}](i)\right\rvert^{2}}{\alpha^{2/p-1}\left\lVert\mathbf{A}\mathbf{x}\right\rVert_{2}^{2}}$

which is at most $2\alpha$, where $\mathbf{A}^{\prime}$ is the concatenation
of $\mathbf{S}\mathbf{A}$ and $\mathbf{S}^{\prime}\mathbf{A}$. These ideas
lead to our Theorem 1.9.

####  2.5.4 Leverage Score + Sensitivity Sampling, $p>2$

Finally, for our Theorem 1.10, we take essentially the same approach as the
recursive form of our sensitivity sampling result for $p>2$ in Theorem 1.5,
except that we improve our flattening approach by flattening _leverage scores_
as well, which is formalized in Lemma 7.9. Note that when we only flatten
$\ell_{p}$ sensitivities using Lemma 4.4, then the resulting bound on the
leverage scores is just roughly the average $\ell_{p}$ sensitivity, which is
$\mathfrak{S}^{p}(\mathbf{A})/n$. We show that by also flattening the leverage
scores, we can improve this bound to

$\left\lparen\frac{d}{n}\right\rparen^{2/p}\left\lparen\frac{\mathfrak{S}^{p}(\mathbf{A})}{n}\right\rparen^{1-2/p}.$

Because $\mathfrak{S}^{p}(\mathbf{A})$ is always at least $d/2$ for $p>2$ due
to our Theorem 1.7, this is always better than the previous bound of
$\mathfrak{S}^{p}(\mathbf{A})/n$, which ultimately leads to our improved
sampling algorithm Theorem 1.10.

We note that we do not obtain a corresponding one-shot sampling algorithm,
where the main difficulty is in constructing an auxiliary $\ell_{p}$ subspace
embedding that has few rows, flat leverage scores, does not increase
$\ell_{p}$ norms, and does not decrease $\ell_{2}$ norms. Nonetheless, the
recursive sampling procedure still leads to an efficient algorithm.

##  3 Conclusion and Future Directions

Our work introduces a new analysis for sensitivity sampling for $\ell_{p}$
subspace embeddings, which breaks a previous general sampling barrier of
$\tilde{O}(\varepsilon^{-2}\mathfrak{S}^{p}(\mathbf{A})d)$ samples via a
simple union bound argument, to obtain an improved bound of
$\tilde{O}(\varepsilon^{-2}\mathfrak{S}^{p}(\mathbf{A})^{2/p})$ samples for
$p<2$ and $\tilde{O}(\varepsilon^{-2}\mathfrak{S}^{p}(\mathbf{A})^{2-2/p})$
samples for $p>2$. We also present other novel results for sampling algorithms
for $\ell_{p}$ subspace embeddings based on our techniques, showing that the
popular root leverage score sampling algorithm yields a bound of
$\tilde{O}(\varepsilon^{-4/p}d)$ for $p<2$, as well as an improved
$\tilde{O}(\varepsilon^{-2}d^{2/p}\mathfrak{S}^{p}(\mathbf{A})^{2-4/p})$ bound
for $p>2$ using a recursive sampling algorithm that combines $\ell_{p}$
sensitivity flattening with leverage score flattening. Our improved analyses
of sensitivity sampling as well as our novel leverage score and sensitivity
flattening algorithm give the best known sampling guarantees for a number of
structured regression problems with small arbitrary noise.

We conclude with several open questions. Perhaps the most natural is to
completely resolve Question 1.4 by characterizing the sample complexity of
sensitivity sampling. We conjecture that a sample complexity of
$\tilde{O}(\varepsilon^{-2}(\mathfrak{S}^{p}(\mathbf{A})+d))$ is possible for
$\ell_{p}$ subspace embeddings, and perhaps for more broad settings where
sensitivity sampling applies as well. Furthermore, for $p>2$, we believe it is
of interest to obtain this bound even without the use of sensitivity sampling
via other methods. Finally, we raise the question of obtaining sampling
algorithms for subspace embeddings for the Huber loss with nearly optimal
sample complexity, for which our results may be useful.

## Acknowledgements

We thank the anonymous reviewers for useful feedback on improving the
presentation of this work. David P. Woodruff and Taisuke Yasuda were supported
by a Simons Investigator Award.

## References

  * [AKPS19] Deeksha Adil, Rasmus Kyng, Richard Peng, and Sushant Sachdeva.  Iterative refinement for $\ell_{p}$-norm regression.  In Timothy M. Chan, editor, Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, California, USA, January 6-9, 2019, pages 1405–1424. SIAM, 2019.
  * [APS19] Deeksha Adil, Richard Peng, and Sushant Sachdeva.  Fast, provably convergent IRLS algorithm for p-norm linear regression.  In Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d’Alché-Buc, Emily B. Fox, and Roman Garnett, editors, Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, December 8-14, 2019, Vancouver, BC, Canada, pages 14166–14177, 2019.
  * [AS20] Deeksha Adil and Sushant Sachdeva.  Faster _p_ -norm minimizing flows, via smoothed _q_ -norm problems.  In Shuchi Chawla, editor, Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020, Salt Lake City, UT, USA, January 5-8, 2020, pages 892–910. SIAM, 2020.
  * [ASW13] Haim Avron, Vikas Sindhwani, and David P. Woodruff.  Sketching structured matrices for faster nonlinear regression.  In Christopher J. C. Burges, Léon Bottou, Zoubin Ghahramani, and Kilian Q. Weinberger, editors, Advances in Neural Information Processing Systems 26: 27th Annual Conference on Neural Information Processing Systems 2013. Proceedings of a meeting held December 5-8, 2013, Lake Tahoe, Nevada, United States, pages 2994–3002, 2013.
  * [BDM+20] Vladimir Braverman, Petros Drineas, Cameron Musco, Christopher Musco, Jalaj Upadhyay, David P. Woodruff, and Samson Zhou.  Near optimal linear algebra in the online and sliding window models.  In 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020, Durham, NC, USA, November 16-19, 2020, pages 517–528. IEEE, 2020.
  * [BFL16] Vladimir Braverman, Dan Feldman, and Harry Lang.  New frameworks for offline and streaming coreset constructions.  CoRR, abs/1612.00889, 2016.
  * [BHM+21] Vladimir Braverman, Avinatan Hassidim, Yossi Matias, Mariano Schain, Sandeep Silwal, and Samson Zhou.  Adversarial robustness of streaming algorithms through importance sampling.  In Marc’Aurelio Ranzato, Alina Beygelzimer, Yann N. Dauphin, Percy Liang, and Jennifer Wortman Vaughan, editors, Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, NeurIPS 2021, December 6-14, 2021, virtual, pages 3544–3557, 2021.
  * [BLM89] J. Bourgain, J. Lindenstrauss, and V. Milman.  Approximation of zonoids by zonotopes.  Acta Math., 162(1-2):73–141, 1989.
  * [CD21] Xue Chen and Michal Derezinski.  Query complexity of least absolute deviation regression via robust uniform convergence.  In Mikhail Belkin and Samory Kpotufe, editors, Conference on Learning Theory, COLT 2021, 15-19 August 2021, Boulder, Colorado, USA, volume 134 of Proceedings of Machine Learning Research, pages 1144–1179. PMLR, 2021.
  * [Cla05] Kenneth L. Clarkson.  Subgradient and sampling algorithms for $\ell_{1}$ regression.  In Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’05, pages 257–266, USA, 2005. Society for Industrial and Applied Mathematics.
  * [CP15] Michael B. Cohen and Richard Peng.  L${}_{\mbox{p}}$ row sampling by lewis weights.  In Rocco A. Servedio and Ronitt Rubinfeld, editors, Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015, Portland, OR, USA, June 14-17, 2015, pages 183–192. ACM, 2015.
  * [CW15a] Kenneth L. Clarkson and David P. Woodruff.  Input sparsity and hardness for robust subspace approximation.  In Venkatesan Guruswami, editor, IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015, Berkeley, CA, USA, 17-20 October, 2015, pages 310–329. IEEE Computer Society, 2015.
  * [CW15b] Kenneth L. Clarkson and David P. Woodruff.  Sketching for _M_ -estimators: A unified approach to robust regression.  In Piotr Indyk, editor, Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, San Diego, CA, USA, January 4-6, 2015, pages 921–939. SIAM, 2015.
  * [DDH+09] Anirban Dasgupta, Petros Drineas, Boulos Harb, Ravi Kumar, and Michael W. Mahoney.  Sampling algorithms and coresets for $\ell_{p}$ regression.  SIAM J. Comput., 38(5):2060–2078, 2009.
  * [FL11] Dan Feldman and Michael Langberg.  A unified framework for approximating and clustering data.  In Lance Fortnow and Salil P. Vadhan, editors, Proceedings of the 43rd ACM Symposium on Theory of Computing, STOC 2011, San Jose, CA, USA, 6-8 June 2011, pages 569–578. ACM, 2011.
  * [FLPS22] Maryam Fazel, Yin Tat Lee, Swati Padmanabhan, and Aaron Sidford.  Computing lewis weights to high precision.  In Joseph (Seffi) Naor and Niv Buchbinder, editors, Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, SODA 2022, Virtual Conference / Alexandria, VA, USA, January 9 - 12, 2022, pages 2723–2742. SIAM, 2022.
  * [FSS20] Dan Feldman, Melanie Schmidt, and Christian Sohler.  Turning big data into tiny data: Constant-size coresets for k-means, pca, and projective clustering.  SIAM J. Comput., 49(3):601–657, 2020.
  * [GPV21] Mehrdad Ghadiri, Richard Peng, and Santosh S Vempala.  Faster p-norm regression using sparsity.  arXiv preprint arXiv:2109.11537, 2021.
  * [HV20] Lingxiao Huang and Nisheeth K. Vishnoi.  Coresets for clustering in euclidean spaces: importance sampling is nearly optimal.  In Konstantin Makarychev, Yury Makarychev, Madhur Tulsiani, Gautam Kamath, and Julia Chuzhoy, editors, Proccedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, Chicago, IL, USA, June 22-26, 2020, pages 1416–1429. ACM, 2020.
  * [JG18] Tyler B. Johnson and Carlos Guestrin.  Training deep models faster with robust, approximate importance sampling.  In Samy Bengio, Hanna M. Wallach, Hugo Larochelle, Kristen Grauman, Nicolò Cesa-Bianchi, and Roman Garnett, editors, Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurIPS 2018, December 3-8, 2018, Montréal, Canada, pages 7276–7286, 2018.
  * [JLS22] Arun Jambulapati, Yang P. Liu, and Aaron Sidford.  Improved iteration complexities for overconstrained _p_ -norm regression.  In Stefano Leonardi and Anupam Gupta, editors, STOC ’22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20 \- 24, 2022, pages 529–542. ACM, 2022.
  * [KF17] Angelos Katharopoulos and François Fleuret.  Biased importance sampling for deep neural network training.  CoRR, abs/1706.00043, 2017.
  * [Lee16] Yin Tat Lee.  Faster algorithms for convex and combinatorial optimization.  PhD thesis, Massachusetts Institute of Technology, 2016.
  * [Lew78] D. R. Lewis.  Finite dimensional subspaces of ${L}_{p}$.  Studia Mathematica, 63(2):207–212, 1978.
  * [LS10] Michael Langberg and Leonard J. Schulman.  Universal epsilon-approximators for integrals.  In Moses Charikar, editor, Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2010, Austin, Texas, USA, January 17-19, 2010, pages 598–607. SIAM, 2010.
  * [LT91] Michel Ledoux and Michel Talagrand.  Probability in Banach Spaces: isoperimetry and processes, volume 23.  Springer Science & Business Media, 1991.
  * [Mah11] Michael W. Mahoney.  Randomized algorithms for matrices and data.  Found. Trends Mach. Learn., 3(2):123–224, 2011.
  * [MMM+22] Raphael A. Meyer, Cameron Musco, Christopher Musco, David P. Woodruff, and Samson Zhou.  Fast regression for structured inputs.  In The Tenth International Conference on Learning Representations, ICLR 2022, Virtual Event, April 25-29, 2022. OpenReview.net, 2022.
  * [MMWY22] Cameron Musco, Christopher Musco, David P. Woodruff, and Taisuke Yasuda.  Active linear regression for $\ell_{p}$ norms and beyond.  In 63rd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2022, Denver, CO, USA, October 31 - November 3, 2022, pages 744–753. IEEE, 2022.
  * [MO23] Naren Sarayu Manoj and Max Ovsiankin.  The change-of-measure method, block lewis weights, and approximating matrix block norms.  CoRR, abs/2311.10013, 2023.
  * [MOP22] Alexander Munteanu, Simon Omlor, and Christian Peters.  p-generalized probit regression and scalable maximum likelihood estimation via sketching and coresets.  In Gustau Camps-Valls, Francisco J. R. Ruiz, and Isabel Valera, editors, International Conference on Artificial Intelligence and Statistics, AISTATS 2022, 28-30 March 2022, Virtual Event, volume 151 of Proceedings of Machine Learning Research, pages 2073–2100. PMLR, 2022\.
  * [MSSW18] Alexander Munteanu, Chris Schwiegelshohn, Christian Sohler, and David P. Woodruff.  On coresets for logistic regression.  In Samy Bengio, Hanna M. Wallach, Hugo Larochelle, Kristen Grauman, Nicolò Cesa-Bianchi, and Roman Garnett, editors, Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurIPS 2018, December 3-8, 2018, Montréal, Canada, pages 6562–6571, 2018.
  * [Nel16] Jelani Nelson.  Chaining introduction with some computer science applications.  Bull. EATCS, 120, 2016.
  * [Sch87] Gideon Schechtman.  More on embedding subspaces of $L_{p}$ in $l^{n}_{r}$.  Compositio Math., 61(2):159–169, 1987.
  * [SW18] Christian Sohler and David P. Woodruff.  Strong coresets for k-median and subspace approximation: Goodbye dimension.  In Mikkel Thorup, editor, 59th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2018, Paris, France, October 7-9, 2018, pages 802–813. IEEE Computer Society, 2018.
  * [SZ01] Gideon Schechtman and Artem Zvavitch.  Embedding subspaces of $l_{p}$ into $l_{p}^{n}$, $0<p<1$.  Mathematische Nachrichten, 227(1):133–142, 2001.
  * [Tal90] Michel Talagrand.  Embedding subspaces of $L_{1}$ into $l^{N}_{1}$.  Proc. Amer. Math. Soc., 108(2):363–369, 1990.
  * [Tal95] Michel Talagrand.  Embedding subspaces of $L_{p}$ in $l^{N}_{p}$.  In Geometric aspects of functional analysis (Israel, 1992–1994), volume 77 of Oper. Theory Adv. Appl., pages 311–325. Birkhäuser, Basel, 1995.
  * [TMF20] Murad Tukan, Alaa Maalouf, and Dan Feldman.  Coresets for near-convex functions.  In Hugo Larochelle, Marc’Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tien Lin, editors, Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual, 2020.
  * [Ver18] Roman Vershynin.  High-dimensional probability, volume 47 of Cambridge Series in Statistical and Probabilistic Mathematics.  Cambridge University Press, Cambridge, 2018.
  * [VX12] Kasturi R. Varadarajan and Xin Xiao.  On the sensitivity of shape fitting problems.  In Deepak D’Souza, Telikepalli Kavitha, and Jaikumar Radhakrishnan, editors, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2012, December 15-17, 2012, Hyderabad, India, volume 18 of LIPIcs, pages 486–497. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2012.
  * [WY22] David P. Woodruff and Taisuke Yasuda.  High-dimensional geometric streaming in polynomial space.  In 63rd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2022, Denver, CO, USA, October 31 - November 3, 2022, pages 732–743. IEEE, 2022.
  * [WY23] David P. Woodruff and Taisuke Yasuda.  Online Lewis weight sampling.  In Proceedings of the 34th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2023. SIAM, 2023.

##  4 Properties of $\ell_{p}$ Sensitivities

###  4.1 Monotonicity of Max $\ell_{p}$ Sensitivity

We first provide proofs of Lemma 2.2 and Lemma 2.3. The results are similar to
results used in [BDM+20, MMWY22]. In particular, it generalizes Lemma 4.6 of
[BDM+20] and is a simplification of a specific instance of Lemma C.3 of
[MMWY22].

###### Proof of Lemma 2.2.

We have that

$\left\lVert\mathbf{y}\right\rVert_{q}^{q}=\sum_{i=1}^{n}\lvert\mathbf{y}(i)\rvert^{q}\leq\left\lVert\mathbf{y}\right\rVert_{\infty}^{q-p}\sum_{i=1}^{n}\lvert\mathbf{y}(i)\rvert^{p}=\left\lVert\mathbf{y}\right\rVert_{\infty}^{q-p}\left\lVert\mathbf{y}\right\rVert_{p}^{p},$

so

$\frac{\lVert\mathbf{y}\rVert_{\infty}^{p}}{\left\lVert\mathbf{y}\right\rVert_{p}^{p}}\leq\frac{\lVert\mathbf{y}\rVert_{\infty}^{p}}{\left\lVert\mathbf{y}\right\rVert_{q}^{q}/\left\lVert\mathbf{y}\right\rVert_{\infty}^{q-p}}=\frac{\left\lVert\mathbf{y}\right\rVert_{\infty}^{q}}{\left\lVert\mathbf{y}\right\rVert_{q}^{q}}.$

∎

###### Proof of Lemma 2.3.

Since
$\left\lVert\mathbf{y}\right\rVert_{p}\leq\left\lVert\mathbf{y}\right\rVert_{q}n^{1/p-1/q}$,
we have that

$\frac{\left\lVert\mathbf{y}\right\rVert_{\infty}^{q}}{\left\lVert\mathbf{y}\right\rVert_{q}^{q}}\leq\frac{\lvert\mathbf{y}(i)\rvert^{q}}{\left\lVert\mathbf{y}\right\rVert_{p}^{q}\cdot
n^{1-q/p}}\leq\frac{\lVert\mathbf{y}\rVert_{\infty}^{q}}{\left\lVert\mathbf{y}\right\rVert_{p}^{q}\cdot
n^{1-q/p}}=\left\lparen\frac{\left\lVert\mathbf{y}\right\rVert_{\infty}^{p}}{\left\lVert\mathbf{y}\right\rVert_{p}^{p}}\right\rparen^{q/p}n^{q/p-1}.$

∎

###  4.2 Total Sensitivity

We now derive bounds on the total $\ell_{p}$ sensitivity.

####  4.2.1 Sampling Preserves Total Sensitivity

######  Lemma 4.1 (Sampling Preserves Total Sensitivity).

Let $\mathbf{A}\in\mathbb{R}^{n\times d}$ and $1\leq p<\infty$. Let
$\mathbf{S}$ be a random $\ell_{p}$ sampling matrix such that with probability
at least $3/4$,

$\left\lVert\mathbf{S}\mathbf{A}\mathbf{x}\right\rVert_{p}=(1\pm
1/2)\left\lVert\mathbf{A}\mathbf{x}\right\rVert_{p}$

simultaneously for every $\mathbf{x}\in\mathbb{R}^{d}$. Then, with probability
at least $1/2$,

$\operatorname*{\mathbf{Pr}}\left\\{\mathfrak{S}^{p}(\mathbf{S}\mathbf{A})\leq
8\mathfrak{S}^{p}(\mathbf{A})\right\\}\geq\frac{1}{2}.$

###### Proof.

We have that

$\mathfrak{S}^{p}(\mathbf{S}\mathbf{A})=\sum_{i=1}^{n}\sup_{\mathbf{S}\mathbf{A}\mathbf{x}\neq
0}\frac{\left\lvert[\mathbf{S}\mathbf{A}\mathbf{x}](i)\right\rvert^{p}}{\left\lVert\mathbf{S}\mathbf{A}\mathbf{x}\right\rVert_{p}^{p}}=\sum_{i=1}^{n}\mathbf{S}_{i,i}^{p}\sup_{\mathbf{S}\mathbf{A}\mathbf{x}\neq
0}\frac{\left\lvert[\mathbf{A}\mathbf{x}](i)\right\rvert^{p}}{\left\lVert\mathbf{A}\mathbf{x}\right\rVert_{p}^{p}}\frac{\left\lVert\mathbf{A}\mathbf{x}\right\rVert_{p}^{p}}{\left\lVert\mathbf{S}\mathbf{A}\mathbf{x}\right\rVert_{p}^{p}}\leq\sum_{i=1}^{n}\mathbf{S}_{i,i}^{p}\boldsymbol{\sigma}_{i}^{p}(\mathbf{A})\sup_{\mathbf{S}\mathbf{A}\mathbf{x}\neq
0}\frac{\left\lVert\mathbf{A}\mathbf{x}\right\rVert_{p}^{p}}{\left\lVert\mathbf{S}\mathbf{A}\mathbf{x}\right\rVert_{p}^{p}}.$

We are guaranteed that

$\operatorname*{\mathbf{Pr}}\left\\{\sup_{\mathbf{S}\mathbf{A}\mathbf{x}\neq
0}\frac{\left\lVert\mathbf{A}\mathbf{x}\right\rVert_{p}^{p}}{\left\lVert\mathbf{S}\mathbf{A}\mathbf{x}\right\rVert_{p}^{p}}\leq
2\right\\}\geq\frac{3}{4}.$

On the other hand, we have that

$\operatorname*{\mathbf{E}}\left[\sum_{i=1}^{n}\mathbf{S}_{i,i}^{p}\boldsymbol{\sigma}_{i}^{p}(\mathbf{A})\right]=\sum_{i=1}^{n}\operatorname*{\mathbf{E}}[\mathbf{S}_{i,i}^{p}]\boldsymbol{\sigma}_{i}^{p}(\mathbf{A})=\mathfrak{S}^{p}(\mathbf{A})$

so by Markov’s inequality,

$\operatorname*{\mathbf{Pr}}\left\\{\sum_{i=1}^{n}\mathbf{S}_{i,i}^{p}\boldsymbol{\sigma}_{i}^{p}(\mathbf{A})\leq
4\mathfrak{S}^{p}(\mathbf{A})\right\\}\geq\frac{3}{4}.$

By a union bound,

$\operatorname*{\mathbf{Pr}}\left\\{\mathfrak{S}^{p}(\mathbf{S}\mathbf{A})\leq
8\mathfrak{S}^{p}(\mathbf{A})\right\\}\geq\frac{1}{2}.$

∎

We also prove a high probability and high accuracy version of Lemma 4.1.

######  Lemma 4.2 (Sensitivity Sampling Preserves Total Sensitivity: High
Probability and Accuracy).

Let $\mathbf{A}\in\mathbb{R}^{n\times d}$ and $1\leq p<\infty$. Let
$0<\varepsilon,\delta<1$. Let $\mathbf{S}$ be a random $\ell_{p}$ sampling
matrix such that with probability at least $1-\delta$,

$\left\lVert\mathbf{S}\mathbf{A}\mathbf{x}\right\rVert_{p}=(1\pm\varepsilon)\left\lVert\mathbf{A}\mathbf{x}\right\rVert_{p}$

simultaneously for every $\mathbf{x}\in\mathbb{R}^{d}$. Furthermore, suppose
that

$\frac{\boldsymbol{\sigma}_{i}}{q_{i}}\leq
M\coloneqq\frac{\varepsilon^{2}\mathfrak{S}^{p}(\mathbf{A})}{3\log\frac{2}{\delta}}$

for every $i\in[n]$. Then, with probability at least $1-2\delta$,

$\operatorname*{\mathbf{Pr}}\left\\{\mathfrak{S}^{p}(\mathbf{S}\mathbf{A})=(1\pm
O(\varepsilon))\mathfrak{S}^{p}(\mathbf{A})\right\\}\geq 1-2\delta.$

###### Proof.

The proof follows Lemma 4.1. Just as in Lemma 4.1, we have that

$\mathfrak{S}^{p}(\mathbf{S}\mathbf{A})\leq\sum_{i=1}^{n}\mathbf{S}_{i,i}^{p}\boldsymbol{\sigma}_{i}^{p}(\mathbf{A})\sup_{\mathbf{S}\mathbf{A}\mathbf{x}\neq
0}\frac{\left\lVert\mathbf{A}\mathbf{x}\right\rVert_{p}^{p}}{\left\lVert\mathbf{S}\mathbf{A}\mathbf{x}\right\rVert_{p}^{p}}.$

Similarly,

$\mathfrak{S}^{p}(\mathbf{S}\mathbf{A})\geq\sum_{i=1}^{n}\mathbf{S}_{i,i}^{p}\boldsymbol{\sigma}_{i}^{p}(\mathbf{A})\inf_{\mathbf{S}\mathbf{A}\mathbf{x}\neq
0}\frac{\left\lVert\mathbf{A}\mathbf{x}\right\rVert_{p}^{p}}{\left\lVert\mathbf{S}\mathbf{A}\mathbf{x}\right\rVert_{p}^{p}}.$

Furthermore, since $\boldsymbol{\sigma}_{i}/q_{i}\leq M$,
$\mathbf{S}_{i,i}^{p}\boldsymbol{\sigma}_{i}^{p}(\mathbf{A})/M$ is a random
variable bounded by $1$, with

$\operatorname*{\mathbf{E}}\left[\sum_{i=1}^{n}\frac{\mathbf{S}_{i,i}^{p}\boldsymbol{\sigma}_{i}^{p}(\mathbf{A})}{M}\right]=\frac{\mathfrak{S}^{p}(\mathbf{A})}{M}\geq\frac{3}{\varepsilon^{2}}\log\frac{2}{\delta}.$

Thus by Chernoff bounds, we have that

$\operatorname*{\mathbf{Pr}}\left\\{\sum_{i=1}^{n}\mathbf{S}_{i,i}^{p}\boldsymbol{\sigma}_{i}^{p}(\mathbf{A})=(1\pm\varepsilon)\mathfrak{S}^{p}(\mathbf{A})\right\\}\geq
1-\delta.$

We conclude by a union bound as in Lemma 4.1. ∎

####  4.2.2 Total Sensitivity Lower Bounds

We start with the classical result that the total $\ell_{2}$ sensitivity is
exactly $d$:

######  Lemma 4.3.

Let $\mathbf{A}\in\mathbb{R}^{n\times d}$ and let
$\mathbf{U}\in\mathbb{R}^{n\times d}$ be an orthnormal basis for the column
space of $\mathbf{A}$. Then,

$\boldsymbol{\tau}_{i}(\mathbf{A})=\left\lVert\mathbf{e}_{i}^{\top}\mathbf{U}\right\rVert_{2}^{2}$

and

$\sum_{i=1}^{n}\boldsymbol{\tau}_{i}(\mathbf{A})=\left\lVert\mathbf{U}\right\rVert_{F}^{2}=d.$

###### Proof.

We have that

$\boldsymbol{\tau}_{i}(\mathbf{A})=\sup_{\mathbf{x}\in\mathbb{R}^{d},\mathbf{A}\mathbf{x}\neq
0}\frac{\left\lvert[\mathbf{A}\mathbf{x}](i)\right\rvert^{2}}{\left\lVert\mathbf{A}\mathbf{x}\right\rVert_{2}^{2}}=\sup_{\mathbf{x}\in\mathbb{R}^{d},\mathbf{U}\mathbf{x}\neq
0}\frac{\left\lvert[\mathbf{U}\mathbf{x}](i)\right\rvert^{2}}{\left\lVert\mathbf{U}\mathbf{x}\right\rVert_{2}^{2}}=\sup_{\mathbf{x}\in\mathbb{R}^{d},\mathbf{x}\neq
0}\frac{\left\lvert[\mathbf{U}\mathbf{x}](i)\right\rvert^{2}}{\left\lVert\mathbf{x}\right\rVert_{2}^{2}}=\left\lVert\mathbf{e}_{i}^{\top}\mathbf{U}\right\rVert_{2}^{2}.$

∎

We now use Lemma 4.3 together with Lemma 2.2 and Lemma 2.3 to derive lower
bounds on $\mathfrak{S}^{p}(\mathbf{A})$.

By using a simple argument based on “splitting rows” (see, e.g., [LT91, CP15,
CD21, MMWY22]), it is possible to assume without loss of generality that the
maximum $\ell_{p}$ sensitivity is related to the average $\ell_{p}$
sensitivity, up to a factor of $2$:

######  Lemma 4.4 ($\ell_{p}$ Sensitivity Flattening).

Let $\mathbf{A}\in\mathbb{R}^{n\times d}$ and $1\leq p<\infty$. Let $C\geq 1$.
Then, there exists a $\mathbf{A}^{\prime}\in\mathbb{R}^{m\times d}$ for
$m=(1+1/C)n$ such that
$\left\lVert\mathbf{A}\mathbf{x}\right\rVert_{p}=\left\lVert\mathbf{A}^{\prime}\mathbf{x}\right\rVert_{p}$
for every $\mathbf{x}\in\mathbb{R}^{d}$,
$\mathfrak{S}^{p}(\mathbf{A})=\mathfrak{S}^{p}(\mathbf{A}^{\prime})$, and
$\boldsymbol{\sigma}_{i^{\prime}}^{p}(\mathbf{A}^{\prime})\leq
C\mathfrak{S}^{p}(\mathbf{A})/n$ for every $i^{\prime}\in[m]$.

###### Proof of Lemma 4.4.

Suppose that for any row $\mathbf{a}_{i}\in\mathbb{R}^{d}$ of $\mathbf{A}$ for
$i\in[n]$ with $\boldsymbol{\sigma}_{i}^{p}(\mathbf{A})\geq
C\mathfrak{S}^{p}(\mathbf{A})/n$, we replace the row with
$k\coloneqq\left\lceil\boldsymbol{\sigma}_{i}^{p}(\mathbf{A})/(C\mathfrak{S}^{p}(\mathbf{A})/n)\right\rceil$
copies of $\mathbf{a}_{i}/k^{1/p}$ to form a new matrix $\mathbf{A}^{\prime}$.
Then, we add at most

$\sum_{i:\boldsymbol{\sigma}_{i}^{p}(\mathbf{A})\geq\mathfrak{S}^{p}(\mathbf{A})/n}\left\lceil\frac{\boldsymbol{\sigma}_{i}^{p}(\mathbf{A})}{C\mathfrak{S}^{p}(\mathbf{A})/n}\right\rceil-1\leq\sum_{i:\boldsymbol{\sigma}_{i}^{p}(\mathbf{A})\geq\mathfrak{S}^{p}(\mathbf{A})/n}\frac{\boldsymbol{\sigma}_{i}^{p}(\mathbf{A})}{C\mathfrak{S}^{p}(\mathbf{A})/n}=\frac{\mathfrak{S}^{p}(\mathbf{A})}{C\mathfrak{S}^{p}(\mathbf{A})/n}=\frac{n}{C}$

rows. Furthermore, we clearly have that
$\left\lVert\mathbf{A}\mathbf{x}\right\rVert_{p}=\left\lVert\mathbf{A}^{\prime}\mathbf{x}\right\rVert_{p}$
for every $\mathbf{x}\in\mathbb{R}^{d}$, and also for any row
$i^{\prime}\in[m]$ that comes from row $i\in[n]$ in the original matrix,

$\frac{\left\lvert[\mathbf{A}^{\prime}\mathbf{x}](i^{\prime})\right\rvert^{p}}{\left\lVert\mathbf{A}^{\prime}\mathbf{x}\right\rVert_{p}^{p}}\leq\frac{C\mathfrak{S}^{p}(\mathbf{A})/n}{\boldsymbol{\sigma}_{i}^{p}(\mathbf{A})}\frac{\left\lvert[\mathbf{A}\mathbf{x}](i)\right\rvert^{p}}{\left\lVert\mathbf{A}\mathbf{x}\right\rVert_{p}^{p}}\leq\frac{C\mathfrak{S}^{p}(\mathbf{A})}{n}.$

Finally, it is also clear that the sum of the sensitivities is also preserved,
since the sum of the sensitivities of the $k$ copies of each row $i\in[n]$ in
the original matrix is $\boldsymbol{\sigma}_{i}^{p}(\mathbf{A})$. ∎

We can now prove Theorem 1.7:

###### Proof of Theorem 1.7.

Let $\mathbf{A}^{\prime}\in\mathbb{R}^{2n\times d}$ be the matrix given by
Lemma 4.4 applied with $C=1$. Then for $p>2$, we have by Lemma 2.2 that

$\frac{d}{n}\leq\max_{i=1}^{n}\boldsymbol{\sigma}_{i}^{2}(\mathbf{A}^{\prime})\leq\max_{i=1}^{n}\boldsymbol{\sigma}_{i}^{p}(\mathbf{A}^{\prime})\leq\frac{2\mathfrak{S}^{p}(\mathbf{A})}{n}$

and for $p<2$, we have by Lemma 2.3 that

$\frac{d}{n}\leq\max_{i=1}^{n}\boldsymbol{\sigma}_{i}^{2}(\mathbf{A}^{\prime})\leq\left\lparen\max_{i=1}^{n}\boldsymbol{\sigma}_{i}^{p}(\mathbf{A}^{\prime})\right\rparen^{2/p}n^{2/p-1}\leq\left\lparen\frac{2\mathfrak{S}^{p}(\mathbf{A})}{n}\right\rparen^{2/p}n^{2/p-1}=\frac{2^{2/p}\mathfrak{S}^{p}(\mathbf{A})^{2/p}}{n}$

which yield the claimed results. ∎

####  4.2.3 Random Matrices Have Small Total Sensitivity

We show that the above lower bounds can be tight, up to logarithmic factors.
We will use Dvoretzky’s theorem, which can be found in, e.g., Fact 15 in
[SW18]:

######  Theorem 4.5 (Dvoretzky’s Theorem).

Let $1\leq p<2$. Let $n=(d/\varepsilon)^{O(p)}$ be sufficiently large, and let
$\mathbf{A}$ be a suitably scaled random $n\times d$ Gaussian matrix. Then,
with probability at least $99/100$, we have for every
$\mathbf{x}\in\mathbb{R}^{d}$ that

$\left\lVert\mathbf{A}\mathbf{x}\right\rVert_{p}=(1\pm\varepsilon)\left\lVert\mathbf{x}\right\rVert_{2}.$

This gives a proof of Theorem 1.6:

###### Proof of Theorem 1.6.

By applying Theorem 4.5 with $\varepsilon=1/2$, we have that
$\left\lVert\mathbf{A}\mathbf{x}\right\rVert_{p}^{p}=\Theta(n)\left\lVert\mathbf{x}\right\rVert_{2}^{p}$
with probability at least $99/100$. Note also that

$\max_{i=1}^{n}\left\lVert\mathbf{e}_{i}^{\top}\mathbf{A}\right\rVert_{2}\leq
O(\sqrt{d\log n})=O(\sqrt{d\log d})$

which also happens with probability at least $99/100$. By a union bound, both
events happen with probability at least $98/100$.

Now for any $\mathbf{x}\in\mathbb{R}^{d}$ with unit $\ell_{2}$ norm, we have
that

$\left\lvert[\mathbf{A}\mathbf{x}](i)\right\rvert^{p}\leq\left\lVert\mathbf{e}_{i}^{\top}\mathbf{A}\right\rVert_{2}^{p}\cdot\left\lVert\mathbf{x}\right\rVert_{2}^{p}=\left\lVert\mathbf{e}_{i}^{\top}\mathbf{A}\right\rVert_{2}^{p}\leq
O(d\log d)^{p/2}.$

Thus,

$\mathfrak{S}^{p}(\mathbf{A})\leq
n\cdot\max_{i=1}^{n}\sup_{\left\lVert\mathbf{x}\right\rVert_{2}=1}\frac{\left\lvert[\mathbf{A}\mathbf{x}](i)\right\rvert^{p}}{\left\lVert\mathbf{A}\mathbf{x}\right\rVert_{p}^{p}}\leq
n\cdot\max_{i=1}^{n}\sup_{\left\lVert\mathbf{x}\right\rVert_{2}=1}\frac{O(d\log
d)^{p/2}}{\Theta(n)}=O(d\log d)^{p/2}.$

∎

###  4.3 Structured Matrices with Small Sensitivity, $p>2$

###### Proof of Lemma 1.11.

Let $r$ be an integer such that $2^{r}\leq p<2^{r+1}$. Then, for each
$i\in[n]$, we may write

$\mathbf{a}_{i}=\mathbf{k}_{i}+\mathbf{s}_{i}=\sum_{j=1}^{k}\alpha_{i,j}\mathbf{v}_{j}+\sum_{j=1}^{s}\beta_{i,j}\mathbf{e}_{i_{j}}$

where $\mathbf{v}_{j}\in\mathbb{R}^{d}$ for $j\in[k]$. Then, the tensor
product $\mathbf{a}_{i}^{\otimes 2^{r}}$ of $\mathbf{a}_{i}$ with itself
$2^{r}$ times can be written as a linear combination of tensor products
$\mathbf{y}_{1}\otimes\dots\otimes\mathbf{y}_{2^{r}}$, where each
$\mathbf{y}_{q}$ for $q\in[2^{r}]$ is one of
$\\{\mathbf{v}_{1},\mathbf{v}_{2},\dots,\mathbf{v}_{k},\mathbf{e}_{i_{1}},\mathbf{e}_{i_{2}},\dots,\mathbf{e}_{i_{s}}\\}$.
Thus, $\mathbf{a}_{i}^{\otimes r}$ lies in the span of at most $(k+s)^{2^{r}}$
vectors, for a fixed choice of
$\mathbf{e}_{i_{1}},\mathbf{e}_{i_{2}},\dots,\mathbf{e}_{i_{s}}$. Since there
are at most $d^{s}$ possible choices of the sparsity pattern, every
$\mathbf{a}_{i}^{\otimes 2^{r}}$ for $i\in[n]$ lies in the span of at most
$d^{\prime}\coloneqq d^{s}(k+s)^{2^{r}}$ vectors. That is, if
$\mathbf{A}^{\otimes 2^{r}}$ is the Khatri-Rao $2^{r}$th power of
$\mathbf{A}$, then $\mathbf{A}^{\otimes 2^{r}}$ is a rank $d^{\prime}$ matrix.
Then, we have that

$\left\lvert[\mathbf{A}\mathbf{x}](i)\right\rvert^{p}=(\left\lvert[\mathbf{A}\mathbf{x}](i)\right\rvert^{2^{r}})^{p/2^{r}}=(\left\langle\mathbf{a}_{i},\mathbf{x}\right\rangle^{2^{r}})^{p/2^{r}}=\left\lvert\left\langle\mathbf{a}_{i}^{\otimes
2^{r}},\mathbf{x}^{\otimes 2^{r}}\right\rangle\right\rvert^{p/2^{r}}$

so

$\sup_{\mathbf{A}\mathbf{x}\neq
0}\frac{\left\lvert[\mathbf{A}\mathbf{x}](i)\right\rvert^{p}}{\left\lVert\mathbf{A}\mathbf{x}\right\rVert_{p}^{p}}=\sup_{\mathbf{A}\mathbf{x}\neq
0}\frac{\left\lvert[\mathbf{A}^{\otimes 2^{r}}\mathbf{x}^{\otimes
2^{r}}](i)\right\rvert^{p/2^{r}}}{\left\lVert\mathbf{A}^{\otimes
2^{r}}\mathbf{x}^{\otimes
2^{r}}\right\rVert_{p/2^{r}}^{p/2^{r}}}\leq\sup_{\mathbf{A}^{\otimes
2^{r}}\mathbf{x}\neq 0}\frac{\left\lvert[\mathbf{A}^{\otimes
2^{r}}\mathbf{x}](i)\right\rvert^{p/2^{r}}}{\left\lVert\mathbf{A}^{\otimes
2^{r}}\mathbf{x}\right\rVert_{p/2^{r}}^{p/2^{r}}}$

that is, the $\ell_{p/2^{r}}$ sensitivities of $\mathbf{A}^{\otimes 2^{r}}$
upper bound the $\ell_{p}$ sensitivities of $\mathbf{A}$. Since $p/2^{r}\leq
2$, the total $\ell_{p/2^{r}}$ sensitivity of $\mathbf{A}^{\otimes 2^{r}}$ is
bounded by its rank, which is $d^{\prime}$. ∎

###### Proof of Lemma 1.14.

Let $r$ be an integer such that $2^{r}\leq p<2^{r+1}$. Fix some
$\mathbf{x}\in\mathbb{R}^{k(q+1)}$. Now consider the vector
$\left\langle\mathbf{a},\mathbf{x}\right\rangle$, where $\mathbf{a}$ is a
$k(q+1)$-dimensional vector of monomials of degree $0$ through $q$ of the
indeterminate variables $a_{1},a_{2},\dots,a_{k}$, that is,

$\mathbf{a}=(1,a_{1},a_{1}^{2},\dots,a_{1}^{q},\quad
1,a_{2},a_{2}^{2},\dots,a_{2}^{q},\quad\dots,\quad
1,a_{k},a_{k}^{2},\dots,a_{k}^{q}).$

Then, $\left\langle\mathbf{a},\mathbf{x}\right\rangle$ is a degree $q$
polynomial in the indeterminates $a_{1},a_{2},\dots,a_{k}$ with coefficients
specified by $\mathbf{x}$, so
$\left\langle\mathbf{a},\mathbf{x}\right\rangle^{2^{r}}$ is a polynomial in
the indeterminates $a_{1},a_{2},\dots,a_{k}$, such that every monomial term is
at most degree $2^{r}q$ in each variable. Note that there are at most $k$
variables, so there can be at most $(2^{r}q+1)^{k}$ possible monomials, by
choosing the degree of each of the monomials. Let $\mathbf{x}^{\prime}$ denote
the coefficients of this polynomial in the monomial basis, for a given set of
original coefficients $\mathbf{x}$.

Now consider the matrix $V^{q}(\mathbf{A})$. Then, for a fixed
$\mathbf{x}\in\mathbb{R}^{k(q+1)}$, $[V^{q}(\mathbf{A})\mathbf{x}](i)^{2^{r}}$
is the evaluation of $\left\langle\mathbf{a},\mathbf{x}\right\rangle^{2^{r}}$
at the $i$th row $\mathbf{a}_{i}$ of $\mathbf{A}$ for the indeterminates
$a_{1},a_{2},\dots,a_{k}$, so it can be written as the linear combination of
at most $(2^{r}q+1)^{k}$ monomials evaluated at $\mathbf{a}_{i}$, with
coefficients $\mathbf{x}^{\prime}$. Thus,
$[V^{q}(\mathbf{A})\mathbf{x}](i)^{2^{r}}=\mathbf{A}^{\prime}\mathbf{x}^{\prime}$
for some $\mathbf{A}^{\prime}$ with rank at most $(2^{r}q+1)^{k}$.

Finally, note that

$\left\lvert[V^{q}(\mathbf{A})\mathbf{x}](i)\right\rvert^{p}=(\left\lvert[V^{q}(\mathbf{A})\mathbf{x}](i)\right\rvert^{2^{r}})^{p/2^{r}}=\left\lvert[\mathbf{A}^{\prime}\mathbf{x}^{\prime}](i)\right\rvert^{p/2^{r}}.$

Thus, the total $\ell_{p}$ sensitivity of $V^{q}(\mathbf{A})$ is bounded by
the total $\ell_{p/2^{r}}$ sensitivity of $\mathbf{A}^{\prime}$, which is at
most $(2^{r}q+1)^{k}\leq(pq+1)^{k}$. ∎

###  4.4 Total $\ell_{p}$ Sensitivity Under Perturbations

###### Proof of Lemma 1.15.

For any $\mathbf{x}\in\mathbb{R}^{d}$, we have that

$\displaystyle\left\lVert(\mathbf{A}+\mathbf{E})\mathbf{x}\right\rVert_{p}$
$\displaystyle=\left\lVert\mathbf{A}\mathbf{x}\right\rVert_{p}\pm\left\lVert\mathbf{E}\mathbf{x}\right\rVert_{p}$
$\displaystyle=\left\lVert\mathbf{A}\mathbf{x}\right\rVert_{p}\pm\sqrt{n}\left\lVert\mathbf{E}\mathbf{x}\right\rVert_{2}$
$\displaystyle=\left\lVert\mathbf{A}\mathbf{x}\right\rVert_{p}\pm\frac{\sigma_{\min}}{\sqrt{n}}\left\lVert\mathbf{x}\right\rVert_{2}$
$\displaystyle=\left\lVert\mathbf{A}\mathbf{x}\right\rVert_{p}\pm\frac{\sigma_{\min}}{\sqrt{n}}\frac{1}{\sigma_{\min}}\left\lVert\mathbf{A}\mathbf{x}\right\rVert_{2}$
$\displaystyle=\left\lVert\mathbf{A}\mathbf{x}\right\rVert_{p}\pm\frac{1}{2}\left\lVert\mathbf{A}\mathbf{x}\right\rVert_{p}$
$\displaystyle=(1\pm 1/2)\left\lVert\mathbf{A}\mathbf{x}\right\rVert_{p}$

so

$\frac{\left\lvert[(\mathbf{A}+\mathbf{E})\mathbf{x}](i)\right\rvert^{p}}{\left\lVert(\mathbf{A}+\mathbf{E})\mathbf{x}\right\rVert_{p}^{p}}\leq
2^{p-1}\frac{\left\lvert[\mathbf{A}\mathbf{x}](i)\right\rvert^{p}}{\left\lVert(\mathbf{A}+\mathbf{E})\mathbf{x}\right\rVert_{p}^{p}}+2^{p-1}\frac{\left\lvert[\mathbf{E}\mathbf{x}](i)\right\rvert^{p}}{\left\lVert(\mathbf{A}+\mathbf{E})\mathbf{x}\right\rVert_{p}^{p}}\leq
2^{p}\frac{\left\lvert[\mathbf{A}\mathbf{x}](i)\right\rvert^{p}}{\left\lVert\mathbf{A}\mathbf{x}\right\rVert_{p}^{p}}+2^{p}\frac{\left\lvert[\mathbf{E}\mathbf{x}](i)\right\rvert^{p}}{\left\lVert\mathbf{A}\mathbf{x}\right\rVert_{p}^{p}}.$

The first term is clearly bounded by
$2^{p}\boldsymbol{\sigma}_{i}^{p}(\mathbf{A})$ for any $\mathbf{x}$. On the
other hand, the second term is bounded by

$2^{p}\frac{\left\lvert[\mathbf{E}\mathbf{x}](i)\right\rvert^{p}}{\left\lVert\mathbf{A}\mathbf{x}\right\rVert_{p}^{p}}\leq
2^{p}\frac{\left\lVert\mathbf{E}\mathbf{x}\right\rVert_{p}^{p}}{\left\lVert\mathbf{A}\mathbf{x}\right\rVert_{p}^{p}}\leq
2^{p}n^{p/2}\frac{\left\lVert\mathbf{E}\mathbf{x}\right\rVert_{2}^{p}}{\left\lVert\mathbf{A}\mathbf{x}\right\rVert_{p}^{p}}\leq
2^{p}\frac{\sigma_{\min}^{p}}{n^{p/2+1}}\frac{\left\lVert\mathbf{x}\right\rVert_{2}^{p}}{\left\lVert\mathbf{A}\mathbf{x}\right\rVert_{p}^{p}}\leq
2^{p}\frac{1}{n^{p/2+1}}\frac{\left\lVert\mathbf{A}\mathbf{x}\right\rVert_{2}^{p}}{\left\lVert\mathbf{A}\mathbf{x}\right\rVert_{p}^{p}}\leq
2^{p}\frac{\left\lVert\mathbf{A}\mathbf{x}\right\rVert_{p}^{p}}{n\left\lVert\mathbf{A}\mathbf{x}\right\rVert_{p}^{p}}=\frac{2^{p}}{n}.$

Thus, the total sensitivity is bounded by

$2^{p}\sum_{i=1}^{n}\boldsymbol{\sigma}_{i}^{p}(\mathbf{A})+\frac{1}{n}=2^{p}(\mathfrak{S}^{p}(\mathbf{A})+1).$

∎

##  5 Entropy Estimates

In this section, we collect our results on estimates on various metric
entropies, which are needed for our chaining arguments. Our results here are
based on similar results given by [BLM89]. However, we modify their arguments
to only depend on leverage scores and $\ell_{p}$ sensitivities, rather than
using Lewis weights [Lew78, BLM89].

###  5.1 Preliminaries

We first recall general definitions from convex geometry that are relevant to
this section.

######  Definition 5.1 ($d_{X}$-balls).

Let $d_{X}$ be a metric on $\mathbb{R}^{d}$. Then, for
$\mathbf{x}\in\mathbb{R}^{d}$ and $t\geq 0$, we define the $d_{X}$-ball of
radius $t$ $B_{d}(\mathbf{x},t)$ to be

$B_{X}(\mathbf{x},t)\coloneqq\left\\{\mathbf{x}^{\prime}\in\mathbb{R}^{d}:d_{X}(\mathbf{x},\mathbf{x}^{\prime})\leq
t\right\\}.$

######  Definition 5.2 (Covering numbers and metric entropy).

Let $K,T\subseteq\mathbb{R}^{d}$ be two convex bodies. Then, the _covering
number_ $E(K,T)$ is defined as

$E(K,T)\coloneqq\min\left\\{k\in\mathbb{N}:\exists\\{\mathbf{x}_{i}\\}_{i=1}^{k},K\subseteq\bigcup_{i=1}^{k}(\mathbf{x}_{i}+T)\right\\}.$

If $d_{X}$ is a metric and $t>0$ a radius, then $E(K,d_{X},t)$ is defined as

$E(K,d_{X},t)\coloneqq E(K,B_{X}(0,t))$

(see Definition 5.1). The _metric entropy_ is the logarithm of the covering
number.

Next, we introduce some notation that is specific to our setting of $\ell_{p}$
subspace embeddings.

######  Definition 5.3.

For a matrix $\mathbf{A}\in\mathbb{R}^{n\times d}$ and $p\geq 1$, we define
the ball

$B^{p}(\mathbf{A})\coloneqq\left\\{\mathbf{A}\mathbf{x}\in\mathbb{R}^{n}:\left\lVert\mathbf{A}\mathbf{x}\right\rVert_{p}\leq
1\right\\}.$

We simply write $B^{p}$ if $\mathbf{A}$ is clear from context.

###  5.2 Dual Sudakov Minoration

One powerful tool for bounding covering numbers for covers of the Euclidean
ball is the _dual Sudakov minoration_ theorem, which bounds covering numbers
in terms of the so-called _Levy mean_ :

######  Definition 5.4 (Levy mean).

Let $\left\lVert\cdot\right\rVert_{X}$ be a norm. Then, the _Levy mean of
$\left\lVert\cdot\right\rVert_{X}$_ is defined to be

$M_{X}\coloneqq\frac{\operatorname*{\mathbf{E}}_{\mathbf{g}\in\mathcal{N}(0,\mathbf{I}_{d})}\left\lVert\mathbf{g}\right\rVert_{X}}{\operatorname*{\mathbf{E}}_{\mathbf{g}\in\mathcal{N}(0,\mathbf{I}_{d})}\left\lVert\mathbf{g}\right\rVert_{2}}.$

Bounds on the Levy mean imply bounds for covering the Euclidean ball by
$\left\lVert\cdot\right\rVert_{X}$-balls via the following result:

######  Theorem 5.5 (Dual Sudakov minoration, Proposition 4.2 of [BLM89]).

Let $\left\lVert\cdot\right\rVert_{X}$ be a norm, and let
$B\subseteq\mathbb{R}^{d}$ denote the Euclidean ball in $d$ dimensions. Then,

$\log E(B,\left\lVert\cdot\right\rVert_{X},t)\leq O(d)\frac{M_{X}^{2}}{t^{2}}$

###  5.3 Entropy Estimates for $p>2$

We now use the preceding results to obtain the entropy estimates necessary to
prove our main result for $p>2$. We start by bounding the Levy mean for the
norm defined by
$\mathbf{x}\mapsto\left\lVert\mathbf{A}\mathbf{x}\right\rVert_{q}$ for some
matrix $\mathbf{A}$.

######  Lemma 5.6.

Let $q\geq 2$ and let $\mathbf{A}\in\mathbb{R}^{n\times d}$. Let
$\tau\geq\max_{i=1}^{n}\left\lVert\mathbf{e}_{i}^{\top}\mathbf{A}\right\rVert_{2}^{2}$.
Then,

$\operatorname*{\mathbf{E}}_{\mathbf{g}\sim\mathcal{N}(0,\mathbf{I}_{d})}\lVert\mathbf{A}\mathbf{g}\rVert_{q}\leq
n^{1/q}\sqrt{q\cdot\tau}.$

###### Proof.

We have for every $i\in[n]$ that

$\operatorname*{\mathbf{E}}\lvert[\mathbf{A}\mathbf{g}](i)\rvert^{q}=\frac{2^{q/2}\Gamma(\frac{q+1}{2})}{\sqrt{\pi}}\lVert\mathbf{e}_{i}^{\top}\mathbf{A}\rVert_{2}^{q}\leq
q^{q/2}\cdot\tau^{q/2}$

since $[\mathbf{A}\mathbf{g}](i)$ is distributed as a Gaussian random
variable. Then by Jensen’s inequality and linearity of expectation,

$\operatorname*{\mathbf{E}}_{\mathbf{g}\sim\mathcal{N}(0,\mathbf{I}_{d})}\lVert\mathbf{A}\mathbf{g}\rVert_{q}\leq\left\lparen\operatorname*{\mathbf{E}}_{\mathbf{g}\sim\mathcal{N}(0,\mathbf{I}_{d})}\lVert\mathbf{A}\mathbf{g}\rVert_{q}^{q}\right\rparen^{1/q}=\left\lparen
n\cdot q^{q/2}\cdot\tau^{q/2}\right\rparen^{1/q}=n^{1/q}\sqrt{q\cdot\tau}$

∎

By combining the above calculation with Theorem 5.5, we obtain the following:

######  Corollary 5.7.

Let $2\leq q<\infty$ and let $\mathbf{A}\in\mathbb{R}^{n\times d}$ be
orthonormal. Let
$\tau\geq\max_{i=1}^{n}\left\lVert\mathbf{e}_{i}^{\top}\mathbf{A}\right\rVert_{2}^{2}$.
Then,

$\log E(B^{2},B^{q},t)\leq O(1)\frac{n^{2/q}q\cdot\tau}{t^{2}}$

###### Proof.

For $\mathbf{A}$ orthonormal, $B^{2}(\mathbf{A})=B^{2}$ is isometric to the
Euclidean ball in $d$ dimensions, and thus Theorem 5.5 applies. ∎

We also get a similar result for $q=\infty$, by applying Corollary 5.7 with
$q=O(\log n)$.

######  Corollary 5.8.

Let $\mathbf{A}\in\mathbb{R}^{n\times d}$ be orthonormal. Let
$\tau\geq\max_{i=1}^{n}\left\lVert\mathbf{e}_{i}^{\top}\mathbf{A}\right\rVert_{2}^{2}$.
Then,

$\log E(B^{2},B^{\infty},t)\leq O(1)\frac{(\log n)\cdot\tau}{t^{2}}$

###### Proof.

This follows from the fact that for $\mathbf{y}\in\mathbb{R}^{n}$,

$\left\lVert\mathbf{y}\right\rVert_{\infty}\leq\left\lVert\mathbf{y}\right\rVert_{q}\leq
n^{1/q}\left\lVert\mathbf{y}\right\rVert_{\infty}=O(1)\left\lVert\mathbf{y}\right\rVert_{\infty}$

for $q=O(\log n)$. ∎

###  5.4 Entropy Estimates for $p<2$

By interpolation, we can improve the bound in Corollary 5.7, which is needed
for our results for $p<2$:

######  Lemma 5.9.

Let $2<r<\infty$ and let $\mathbf{A}\in\mathbb{R}^{n\times d}$ be orthonormal.
Let
$\tau\geq\max_{i=1}^{n}\left\lVert\mathbf{e}_{i}^{\top}\mathbf{A}\right\rVert_{2}^{2}$.
Let $1\leq t\leq\operatorname{poly}(d)$. Then,

$\log E(B^{2},B^{r},t)\leq
O(1)\frac{1}{(t/2)^{2r/(r-2)}}\cdot\left\lparen\frac{r}{r-2}\log d+\log
n\right\rparen\tau$

###### Proof.

Let $q>r$, and let $0<\theta<1$ satisfy

$\frac{1}{r}=\frac{1-\theta}{2}+\frac{\theta}{q}$

Then by Hölder’s inequality, we have for any $\mathbf{y}\in\mathbb{R}^{n}$
that

$\left\lVert\mathbf{y}\right\rVert_{r}=\left\lparen\sum_{i=1}^{n}\lvert\mathbf{y}(i)\rvert^{r(1-\theta)}\lvert\mathbf{y}(i)\rvert^{r\theta}\right\rparen^{1/r}\leq\left\lparen\sum_{i=1}^{n}\lvert\mathbf{y}(i)\rvert^{2}\right\rparen^{(1-\theta)/2}\left\lparen\sum_{i=1}^{n}\lvert\mathbf{y}(i)\rvert^{q}\right\rparen^{\theta/q}=\left\lVert\mathbf{y}\right\rVert_{2}^{1-\theta}\left\lVert\mathbf{y}\right\rVert_{q}^{\theta}$

Then for any $\mathbf{y},\mathbf{y}^{\prime}\in B^{2}$, we have

$\left\lVert\mathbf{y}-\mathbf{y}^{\prime}\right\rVert_{r}\leq\left\lVert\mathbf{y}-\mathbf{y}^{\prime}\right\rVert_{2}^{1-\theta}\left\lVert\mathbf{y}-\mathbf{y}^{\prime}\right\rVert_{q}^{\theta}\leq
2\left\lVert\mathbf{y}-\mathbf{y}^{\prime}\right\rVert_{q}^{\theta}$

so

$\log E(B^{2},B^{r},t)\leq\log E(B^{2},B^{q},(t/2)^{1/\theta})\leq
O(1)\frac{n^{2/q}q\cdot\tau}{(t/2)^{2/\theta}}$

by Corollary 5.7. Now, we have

$\frac{2}{\theta}=2\frac{\frac{1}{2}-\frac{1}{q}}{\frac{1}{2}-\frac{1}{r}}=\frac{q-2}{q}\frac{2r}{r-2}$

so by taking $q=O(\frac{r}{r-2}\log d+\log n)$, we have that $n^{2/q}=O(1)$
and $(t/2)^{1/\theta}=\Theta(1)(t/2)^{2r/(r-2)}$, so we conclude as claimed. ∎

Using Lemma 5.9, we obtain the following analogue of Corollary 5.7 for $p<2$.

######  Lemma 5.10.

Let $1\leq p<2$ and let $\mathbf{A}\in\mathbb{R}^{n\times d}$ be orthonormal.
Let
$\tau\geq\max_{i=1}^{n}\left\lVert\mathbf{e}_{i}^{\top}\mathbf{A}\right\rVert_{2}^{2}$.
Then,

$\log E(B^{p},B^{\infty},t)\leq O(1)\frac{1}{t^{p}}\left\lparen\frac{\log
d}{2-p}+\log n\right\rparen\tau.$

###### Proof.

In order to bound a covering of $B^{p}$ by $B^{\infty}$, we first cover
$B^{p}$ by $B^{2}$, and then use Corollary 5.8 to cover $B^{2}$ by
$B^{\infty}$.

We will first bound $E(B^{p},B^{2},t)$ using Lemma 5.9. For each $k\geq 0$,
let $\mathcal{E}_{k}\subseteq B^{p}$ be a maximal subset of $B^{p}$ such that
for each distinct $\mathbf{y},\mathbf{y}^{\prime}\in\mathcal{E}_{k}$,
$\left\lVert\mathbf{y}-\mathbf{y}^{\prime}\right\rVert_{2}>8^{k}t$, with
$\mathcal{E}_{k}\coloneqq\\{0\\}$ for $8^{k+1}t>n^{1/p-1/q}$. Note then that

$\lvert\mathcal{E}_{k}\rvert\geq E(B^{p},B^{2},8^{k}t).$

By averaging, for each $k$, there exists $\mathbf{y}^{(k)}\in\mathcal{E}_{k}$
such that if

$\mathcal{F}_{k}\coloneqq\left\\{\mathbf{y}\in\mathcal{E}_{k}:\lVert\mathbf{y}-\mathbf{y}^{(k)}\rVert_{2}\leq
8^{k+1}t\right\\},$

then

$\lvert\mathcal{F}_{k}\rvert\geq\frac{\lvert\mathcal{E}_{k}\rvert}{E(B^{p},B^{2},8^{k+1}t)}\geq\frac{E(B^{p},B^{2},8^{k}t)}{E(B^{p},B^{2},8^{k+1}t)}$

We now use this observation to construct an $\ell_{p^{\prime}}$-packing of
$B^{2}$, where $p^{\prime}$ is the Hölder conjugate of $p$. Let

$\mathcal{G}_{k}\coloneqq\left\\{\frac{1}{8^{k+1}t}(\mathbf{y}-\mathbf{y}^{(k)}):\mathbf{y}\in\mathcal{F}_{k}\right\\}.$

Then, $\mathcal{G}_{k}\subseteq B^{2}$ and $\mathcal{G}_{k}\subseteq
B^{p}\cdot 2/8^{k+1}t$, and
$\lVert\mathbf{y}-\mathbf{y}^{\prime}\rVert_{2}>1/8$ for every distinct
$\mathbf{y},\mathbf{y}^{\prime}\in\mathcal{G}_{k}$. Then by Hölder’s
inequality,

$\frac{1}{8^{2}}\leq\left\lVert\mathbf{y}-\mathbf{y}^{\prime}\right\rVert_{2}^{2}\leq\left\lVert\mathbf{y}-\mathbf{y}^{\prime}\right\rVert_{p}\left\lVert\mathbf{y}-\mathbf{y}^{\prime}\right\rVert_{p^{\prime}}\leq\frac{4}{8^{k+1}t}\left\lVert\mathbf{y}-\mathbf{y}^{\prime}\right\rVert_{p^{\prime}}$

so $\left\lVert\mathbf{y}-\mathbf{y}^{\prime}\right\rVert_{p^{\prime}}\geq
2\cdot 8^{k-2}t$. Thus, $\mathcal{G}_{k}$ is an $\ell_{p^{\prime}}$-packing of
$B^{2}$, so

$\log
E(B^{2},B^{p^{\prime}},8^{k-2}t)\geq\log\lvert\mathcal{G}_{k}\rvert=\log\lvert\mathcal{F}_{k}\rvert\geq\log
E(B^{p},B^{2},8^{k}t)-\log E(B^{p},B^{2},8^{k+1}t).$ (7)

Summing over $k$ gives

$\displaystyle\log E(B^{p},B^{2},t)$ $\displaystyle=\sum_{k\geq 0}\log
E(B^{p},B^{2},8^{k}t)-\log E(B^{p},B^{2},8^{k+1}t)$
$\displaystyle\leq\sum_{k\geq 0}\log E(B^{2},B^{p^{\prime}},8^{k-2}t)$ (7)
$\displaystyle\leq
O(1)\frac{1}{(t/2)^{2p^{\prime}/(p^{\prime}-2)}}\cdot\left\lparen\frac{p^{\prime}}{p^{\prime}-2}\log
d+\log n\right\rparen\tau$ Lemma 5.9 and Corollary 5.8
$\displaystyle=O(1)\frac{1}{(t/2)^{2p/(2-p)}}\cdot\left\lparen\frac{p}{2-p}\log
d+\log n\right\rparen\tau$

where we take $p^{\prime}/(p^{\prime}-2)=1$ for $p^{\prime}=\infty$. Using
this and Corollary 5.8, we now bound

$\displaystyle\log E(B^{p},B^{\infty},t)$ $\displaystyle\leq\log
E(B^{p},B^{2},\lambda)+\log E(B^{2},B^{\infty},t/\lambda)$ $\displaystyle\leq
O(1)\frac{1}{(\lambda/2)^{2p/(2-p)}}\cdot\left\lparen\frac{p}{2-p}\log d+\log
n\right\rparen\tau+O(1)\frac{(\log n)\cdot\tau}{(t/\lambda)^{2}}$

for any $\lambda\in[1,t]$. We choose $\lambda$ satisfying

$\frac{1}{(\lambda/2)^{2p/(2-p)}}=\frac{(\lambda/2)^{2}}{t^{2}},$

which gives

$(\lambda/2)^{2p/(2-p)}=\left\lparen
t^{2}\right\rparen^{\frac{2p/(2-p)}{2+2p/(2-p)}}=t^{p}$

so we obtain a bound of

$O(1)\frac{1}{t^{p}}\left\lparen\frac{1}{2-p}\log d+\log n\right\rparen\tau.$

∎

##  6 Bounding a Gaussian Process

Using our estimates from Section 5, we study estimates on the Gaussian process
given by

$X:\mathbf{y}\mapsto\sum_{i=1}^{n}\mathbf{g}_{i}\lvert\mathbf{y}(i)\rvert^{p},\qquad\mathbf{y}\in
B^{p}(\mathbf{A})$

for $\mathbf{g}\sim\mathcal{N}(0,\mathbf{I}_{n})$, and in particular, tail
bounds and moment bounds on the quantity

$\sup_{\mathbf{y}\in B^{p}(\mathbf{A})}\lvert
X(\mathbf{y})\rvert=\sup_{\left\lVert\mathbf{A}\mathbf{x}\right\rVert_{p}\leq
1}\left\lvert\sum_{i=1}^{n}\mathbf{g}_{i}\lvert[\mathbf{A}\mathbf{x}](i)\rvert^{p}\right\rvert$

As we show later, this Gaussian process bounds the error of the sensitivity
sampling estimate. Our techniques here are based on similar results obtained
by [LT91].

The main tool is Dudley’s tail inequality for Gaussian processes:

######  Theorem 6.1 (Theorem 8.1.6, [Ver18]).

Let $(X(t))_{t\in T}$ be a Gaussian process with pseudo-metric
$d_{X}(s,t)\coloneqq\left\lVert
X(s)-X(t)\right\rVert_{2}=\sqrt{\operatorname*{\mathbf{E}}(X(s)-X(t))^{2}}$
and let

$\operatorname{diam}(T)\coloneqq\sup\left\\{d_{X}(s,t):s,t\in T\right\\}$

Then, there is a constant $C=O(1)$ such that for every $z\geq 0$,

$\operatorname*{\mathbf{Pr}}\left\\{\sup_{t\in T}X_{t}\geq
C\left[\int_{0}^{\infty}\sqrt{\log
E(T,d_{X},u)}~{}du+z\cdot\operatorname{diam}(T)\right]\right\\}\leq
2\exp(-z^{2})$

The expectation bound version of the theorem will also be useful:

######  Theorem 6.2 (Theorem 8.1.3, [Ver18]).

Let $(X(t))_{t\in T}$ be a Gaussian process with pseudo-metric
$d_{X}(s,t)\coloneqq\left\lVert
X(s)-X(t)\right\rVert_{2}=\sqrt{\operatorname*{\mathbf{E}}(X(s)-X(t))^{2}}$.
Then, there is a constant $C=O(1)$ such that

$\operatorname*{\mathbf{E}}\sup_{t\in T}X_{t}\leq C\int_{0}^{\infty}\sqrt{\log
E(T,d_{X},u)}~{}du.$

###  6.1 Bounds on $d_{X}$

We first bound $d_{X}$ as well as the $d_{X}$-diameter of $B^{p}(\mathbf{A})$.

######  Lemma 6.3.

Let $1\leq p<\infty$ and let $\mathbf{A}\in\mathbb{R}^{n\times d}$. Define the
pseudo-metric

$d_{X}(\mathbf{y},\mathbf{y}^{\prime})\coloneqq\left\lparen\operatorname*{\mathbf{E}}_{\mathbf{g}\sim\mathcal{N}(0,\mathbf{I}_{n})}\left\lvert\sum_{i=1}^{n}\mathbf{g}_{i}\lvert\mathbf{y}(i)\rvert^{p}-\sum_{i=1}^{n}\mathbf{g}_{i}\lvert\mathbf{y}^{\prime}(i)\rvert^{p}\right\rvert^{2}\right\rparen^{1/2}$

Let $\sigma\geq\max_{i=1}^{n}\boldsymbol{\sigma}_{i}^{p}(\mathbf{A})$. Then,
for any $\mathbf{y},\mathbf{y}^{\prime}\in B_{p}(\mathbf{A})$,

$d_{X}(\mathbf{y},\mathbf{y}^{\prime})\leq\begin{dcases}2\left\lVert\mathbf{y}-\mathbf{y}^{\prime}\right\rVert_{\infty}^{p/2}&p<2\\\
2p\cdot\sigma^{1/2-1/p}\cdot\left\lVert\mathbf{y}-\mathbf{y}^{\prime}\right\rVert_{\infty}&p>2\end{dcases}$

###### Proof.

Note first that by expanding out the square and noting that
$\operatorname*{\mathbf{E}}[\mathbf{g}_{i}\mathbf{g}_{j}]=\mathbbm{1}(i=j)$,
we have

$d_{X}(\mathbf{y},\mathbf{y}^{\prime})=\left\lparen\sum_{i=1}^{n}(\lvert\mathbf{y}(i)\rvert^{p}-\lvert\mathbf{y}^{\prime}(i)\rvert^{p})^{2}\right\rparen^{1/2}$

For $p<2$, we bound this as

$\displaystyle d_{X}(\mathbf{y},\mathbf{y}^{\prime})^{2}$
$\displaystyle=\sum_{i=1}^{n}(\lvert\mathbf{y}(i)\rvert^{p}-\lvert\mathbf{y}^{\prime}(i)\rvert^{p})^{2}$
$\displaystyle=\sum_{i=1}^{n}(\lvert\mathbf{y}(i)\rvert^{p/2}-\lvert\mathbf{y}^{\prime}(i)\rvert^{p/2})^{2}(\lvert\mathbf{y}(i)\rvert^{p/2}+\lvert\mathbf{y}^{\prime}(i)\rvert^{p/2})^{2}$
$\displaystyle\leq\sum_{i=1}^{n}(\lvert\mathbf{y}(i)-\mathbf{y}^{\prime}(i)\rvert^{p/2})^{2}(\lvert\mathbf{y}(i)\rvert^{p/2}+\lvert\mathbf{y}^{\prime}(i)\rvert^{p/2})^{2}$
$\displaystyle\leq
2\left\lVert\mathbf{y}-\mathbf{y}^{\prime}\right\rVert_{\infty}^{p}\sum_{i=1}^{n}\lvert\mathbf{y}(i)\rvert^{p}+\lvert\mathbf{y}^{\prime}(i)\rvert^{p}$
$\displaystyle\leq
4\left\lVert\mathbf{y}-\mathbf{y}^{\prime}\right\rVert_{\infty}^{p}.$

For $p>2$, we have by convexity that

$\lvert\mathbf{y}(i)\rvert^{p}-\lvert\mathbf{y}^{\prime}(i)\rvert^{p}\leq
p\lvert\mathbf{y}(i)-\mathbf{y}^{\prime}(i)\rvert(\lvert\mathbf{y}(i)\rvert^{p-1}+\lvert\mathbf{y}^{\prime}(i)\rvert^{p-1})$

and that $\left\lVert\mathbf{y}\right\rVert_{\infty}\leq\sigma^{1/p}$, so we
have

$\displaystyle d_{X}(\mathbf{y},\mathbf{y}^{\prime})^{2}$
$\displaystyle=\sum_{i=1}^{n}(\lvert\mathbf{y}(i)\rvert^{p}-\lvert\mathbf{y}^{\prime}(i)\rvert^{p})^{2}$
$\displaystyle\leq
p^{2}\sum_{i=1}^{n}\lvert\mathbf{y}(i)-\mathbf{y}^{\prime}(i)\rvert^{2}(\lvert\mathbf{y}(i)\rvert^{p-1}+\lvert\mathbf{y}^{\prime}(i)\rvert^{p-1})^{2}$
$\displaystyle\leq
2p^{2}\left\lVert\mathbf{y}-\mathbf{y}^{\prime}\right\rVert_{\infty}^{2}\sum_{i=1}^{n}\lvert\mathbf{y}(i)\rvert^{2p-2}+\lvert\mathbf{y}^{\prime}(i)\rvert^{2p-2}$
$\displaystyle\leq
2p^{2}\max\\{\left\lVert\mathbf{y}\right\rVert_{\infty},\lVert\mathbf{y}^{\prime}\rVert_{\infty}\\}^{p-2}\left\lVert\mathbf{y}-\mathbf{y}^{\prime}\right\rVert_{\infty}^{2}\sum_{i=1}^{n}\lvert\mathbf{y}(i)\rvert^{p}+\lvert\mathbf{y}^{\prime}(i)\rvert^{p}$
$\displaystyle\leq
4p^{2}\sigma^{1-2/p}\left\lVert\mathbf{y}-\mathbf{y}^{\prime}\right\rVert_{\infty}^{2}$

∎

######  Lemma 6.4.

Let $1\leq p<\infty$ and let $\mathbf{A}\in\mathbb{R}^{n\times d}$. Let
$\sigma\geq\max_{i=1}^{n}\boldsymbol{\sigma}_{i}^{p}(\mathbf{A})$. Then, the
diameter of $B^{p}(\mathbf{A})$ with respect to $d_{X}$ is bounded by

$\operatorname{diam}(B^{p}(\mathbf{A}))\leq\begin{cases}4\cdot\sigma^{1/2}&p<2\\\
4p\cdot\sigma^{1/2}&p>2\end{cases}$

###### Proof.

For any $\mathbf{y}\in B^{p}(\mathbf{A})$, we have that
$\left\lVert\mathbf{y}\right\rVert_{\infty}\leq\sigma^{1/p}$, so combining the
triangle inequality and Lemma 6.3 yields the result. ∎

###  6.2 Computing the Entropy Integral

We may now evaluate the entropy integral required in Theorem 6.1. We use the
following calculus lemma:

######  Lemma 6.5.

Let $0<\lambda\leq 1$. Then,

$\int_{0}^{\lambda}\sqrt{\log\frac{1}{t}}~{}dt=\lambda\sqrt{\log(1/\lambda)}+\frac{\sqrt{\pi}}{4}\operatorname{erfc}(\sqrt{\log(1/\lambda)})\leq\lambda\left\lparen\sqrt{\log(1/\lambda)}+\frac{\sqrt{\pi}}{2}\right\rparen$

###### Proof.

We calculate

$\displaystyle\int_{0}^{\lambda}\sqrt{\log\frac{1}{t}}~{}dt$
$\displaystyle=2\int_{\sqrt{\log(1/\lambda)}}^{\infty}x^{2}\exp(-x^{2})~{}dx$
$x=\sqrt{\log(1/t)}$
$\displaystyle=-\int_{\sqrt{\log(1/\lambda)}}^{\infty}x\cdot-2x\exp(-x^{2})~{}dx$
$\displaystyle=-\left\lparen
x\exp(-x^{2})\Big{|}^{\infty}_{\sqrt{\log(1/\lambda)}}-\int_{\sqrt{\log(1/\lambda)}}^{\infty}\exp(-x^{2})~{}dx\right\rparen$
integration by parts
$\displaystyle=\lambda\sqrt{\log\frac{1}{\lambda}}+\frac{\sqrt{\pi}}{2}\operatorname{erfc}\left\lparen\sqrt{\log\frac{1}{\lambda}}\right\rparen$

∎

######  Lemma 6.6 (Entropy integral bound for $p<2$).

Let $1\leq p<2$ and let $\mathbf{A}\in\mathbb{R}^{n\times d}$ be orthonormal.
Let
$\tau\geq\max_{i=1}^{n}\left\lVert\mathbf{e}_{i}^{\top}\mathbf{A}\right\rVert_{2}^{2}$
and let $\sigma\geq\max_{i=1}^{n}\boldsymbol{\sigma}_{i}^{p}(\mathbf{A})$.
Then,

$\int_{0}^{\infty}\sqrt{\log E(B^{p},d_{X},t)}~{}dt\leq
O(\tau^{1/2})\left\lparen\frac{\log d}{2-p}+\log
n\right\rparen^{1/2}\log\frac{d\sigma}{\tau}$

###### Proof.

Note that it suffices to integrate the entropy integral to
$\operatorname{diam}(B^{p}(\mathbf{A}))$ rather than $\infty$, which is at
most $4\sigma^{1/2}$ for $p<2$ and $4p\sigma^{1/2}$ for $p>2$ by Lemma 6.4.

By Lemma 6.3, we have that

$\log E(B^{p},d_{X},t)\leq\log
E(B^{p},2\left\lVert\cdot\right\rVert_{\infty}^{p/2},t)=\log
E(B^{p},B^{\infty},(t/2)^{2/p})$

For small radii less than $\lambda$ for a parameter $\lambda$ to be chosen, we
use a standard volume argument, which shows that

$\log E(B^{p},B^{\infty},t)\leq O(d)\log\frac{n}{t}$

so

$\displaystyle\int_{0}^{\lambda}\sqrt{\log
E(B^{p},B^{\infty},t)}~{}dt=\int_{0}^{\lambda}\sqrt{d\log\frac{n}{t}}~{}dt$
$\displaystyle\leq\lambda\sqrt{d\log
n}+\sqrt{d}\int_{0}^{\lambda}\sqrt{\log\frac{1}{t}}~{}dt$
$\displaystyle\leq\lambda\sqrt{d\log
n}+\sqrt{d}\left\lparen\lambda\sqrt{\log\frac{1}{\lambda}}+\frac{\sqrt{\pi}}{2}\lambda\right\rparen$
$\displaystyle\leq O(\lambda)\sqrt{d\log\frac{n}{\lambda}}$

On the other hand, for large radii larger than $\lambda$, we use the bounds of
Lemma 5.10, which gives

$\log E(B^{p},B^{\infty},(t/2)^{2/p})\leq
O(1)\frac{1}{t^{2}}\left\lparen\frac{\log d}{2-p}+\log n\right\rparen\tau$

so the entropy integral gives a bound of

$O(1)\left[\left\lparen\frac{\log d}{2-p}+\log
n\right\rparen\tau\right]^{1/2}\int_{\lambda}^{4p\sigma^{1/2}}\frac{1}{t}~{}dt=O(1)\left[\left\lparen\frac{\log
d}{2-p}+\log
n\right\rparen\tau\right]^{1/2}\log\frac{4p\sigma^{1/2}}{\lambda}.$

We choose $\lambda=\sqrt{\tau/d}$, which yields the claimed conclusion. ∎

An analogous result and proof holds for $p>2$.

######  Lemma 6.7 (Entropy integral bound for $p>2$).

Let $2<p<\infty$ and let $\mathbf{A}\in\mathbb{R}^{n\times d}$ be orthonormal.
Let
$\tau\geq\max_{i=1}^{n}\left\lVert\mathbf{e}_{i}^{\top}\mathbf{A}\right\rVert_{2}^{2}$
and let $\sigma\geq\max_{i=1}^{n}\boldsymbol{\sigma}_{i}^{p}(\mathbf{A})$.
Then,

$\int_{0}^{\infty}\sqrt{\log E(B^{p},d_{X},t)}~{}dt\leq
O(p\tau^{1/2})\cdot(\sigma n)^{1/2-1/p}(\log
n)^{1/2}\cdot\log\frac{p^{2}d\sigma}{\tau}$

###### Proof.

The proof is similar to the case of $p<2$. We again introduce a parameter
$\lambda$. For radii below $\lambda$, the bound is the same as Lemma 6.6. For
radii above $\lambda$, we use Lemma 6.3 to bound

$\log E(B^{p},d_{X},t)\leq\log
E(B^{p},2p\cdot\sigma^{1/2-1/p}\cdot\left\lVert\cdot\right\rVert_{\infty},t)\leq\log
E(B^{p},B^{\infty},t/2p\cdot\sigma^{1/2-1/p})$

Then by Corollary 5.8,

$\displaystyle\log E(B^{p},B^{\infty},t/2p\cdot\sigma^{1/2-1/p})$
$\displaystyle\leq\log E(B^{2},B^{\infty},t/2p\cdot(\sigma n)^{1/2-1/p})$
$\displaystyle\leq O(p^{2})\frac{(\log n)\cdot\tau}{t^{2}}\cdot(\sigma
n)^{1-2/p}$

so the entropy integral gives a bound of

$O(p\tau^{1/2})\cdot(\sigma n)^{1/2-1/p}(\log
n)^{1/2}\cdot\int_{\lambda}^{\operatorname{diam}(B^{p}(\mathbf{A}))}\frac{1}{t}~{}dt\leq
O(p\tau^{1/2})\cdot(\sigma n)^{1/2-1/p}(\log
n)^{1/2}\cdot\log\frac{p\sigma^{1/2}}{\lambda}$

Choosing $\lambda=\sqrt{\tau/d}$ yields the claimed conclusion. ∎

###  6.3 Moment Bounds

Finally, using our tail bound from combining Theorem 6.1 with the entropy
bounds of Section 6.2 and Lemma 6.4, we obtain the following moment bounds:

######  Lemma 6.8.

Let $\mathbf{A}\in\mathbb{R}^{n\times d}$ and $1\leq p<\infty$. Let
$\tau\geq\max_{i=1}^{n}\boldsymbol{\tau}_{i}(\mathbf{A})$ and let
$\sigma\geq\max_{i=1}^{n}\boldsymbol{\sigma}_{i}^{p}(\mathbf{A})$. Let

$\Lambda\coloneqq\sup_{\left\lVert\mathbf{A}\mathbf{x}\right\rVert_{p}\leq
1}\left\lvert\sum_{i=1}^{n}\mathbf{g}_{i}\lvert[\mathbf{A}\mathbf{x}](i)\rvert^{p}\right\rvert$

Let $\mathcal{E}\coloneqq\int_{0}^{\infty}\sqrt{\log
E(B^{p}(\mathbf{A}),d_{X},u)}~{}du$ and
$\mathcal{D}=\operatorname{diam}(B^{p}(\mathbf{A}))$. Then,

$\operatorname*{\mathbf{E}}_{\mathbf{g}\sim\mathcal{N}(0,\mathbf{I}_{n})}[\lvert\Lambda\rvert^{l}]\leq(2\mathcal{E})^{l}(\mathcal{E}/\mathcal{D})+O(\sqrt{l}\mathcal{D})^{l}$

###### Proof.

By Theorem 6.1, we have for $T=B^{p}(\mathbf{A})$ that

$\operatorname*{\mathbf{Pr}}\left\\{\Lambda\geq
C\left[\int_{0}^{\infty}\sqrt{\log
E(T,d_{X},u)}~{}du+z\cdot\operatorname{diam}(T)\right]\right\\}\leq
2\exp(-z^{2})$

for a constant $C=O(1)$. Then,

$\displaystyle\operatorname*{\mathbf{E}}[(\Lambda/\mathcal{D})^{l}]$
$\displaystyle=l\int_{0}^{\infty}z^{l}\operatorname*{\mathbf{Pr}}\\{\Lambda\geq
z\mathcal{D}\\}~{}dz$
$\displaystyle\leq(2\mathcal{E}/\mathcal{D})^{l+1}+l\int_{2\mathcal{E}/\mathcal{D}}^{\infty}z^{l}\operatorname*{\mathbf{Pr}}\\{\Lambda\geq
z\mathcal{D}\\}~{}dz$
$\displaystyle\leq(2\mathcal{E}/\mathcal{D})^{l+1}+l\int_{2\mathcal{E}/\mathcal{D}}^{\infty}z^{l}\operatorname*{\mathbf{Pr}}\\{\Lambda\geq\mathcal{E}+(z/2)\mathcal{D}\\}~{}dz$
$\displaystyle\leq(2\mathcal{E}/\mathcal{D})^{l+1}+2l\int_{0}^{\infty}z^{l}\exp(-z^{2}/4)~{}dz$
$\displaystyle\leq(2\mathcal{E}/\mathcal{D})^{l+1}+O(l)^{l/2}$

so

$\operatorname*{\mathbf{E}}[\Lambda^{l}]\leq(2\mathcal{E})^{l}(\mathcal{E}/\mathcal{D})+O(\sqrt{l}\mathcal{D})^{l}.$

∎

##  7 Sampling Guarantees

We first reduce our proof of sampling guarantees to the problem of bounding a
Gaussian process:

######  Lemma 7.1 (Reduction to Gaussian processes).

Let $\mathbf{A}\in\mathbb{R}^{n\times d}$ and $1\leq p<\infty$. Let
$\mathbf{S}$ be a random $\ell_{p}$ sampling matrix (Definition 1.1). Then,

$\operatorname*{\mathbf{E}}_{\mathbf{S}}\sup_{\left\lVert\mathbf{A}\mathbf{x}\right\rVert_{p}=1}\left\lvert\left\lVert\mathbf{S}\mathbf{A}\mathbf{x}\right\rVert_{p}^{p}-1\right\rvert^{l}\leq(2\pi)^{l/2}\operatorname*{\mathbf{E}}_{\mathbf{S}}\operatorname*{\mathbf{E}}_{\mathbf{g}\sim\mathcal{N}(0,\mathbf{I}_{n})}\sup_{\left\lVert\mathbf{A}\mathbf{x}\right\rVert_{p}=1}\left\lvert\sum_{i\in
S}\mathbf{g}_{i}\left\lvert[\mathbf{S}\mathbf{A}\mathbf{x}](i)\right\rvert^{p}\right\rvert^{l},$

where $S\subseteq[n]$ is the set of rows with sampling probability $q_{i}<1$.

###### Proof.

By a standard symmetrization argument [CP15, CD21], we have that

$\operatorname*{\mathbf{E}}_{\mathbf{S}}\sup_{\left\lVert\mathbf{A}\mathbf{x}\right\rVert_{p}=1}\left\lvert\left\lVert\mathbf{S}\mathbf{A}\mathbf{x}\right\rVert_{p}^{p}-1\right\rvert^{l}\leq
2^{l}\operatorname*{\mathbf{E}}_{\mathbf{S},\boldsymbol{\varepsilon}}\sup_{\left\lVert\mathbf{A}\mathbf{x}\right\rVert_{p}\leq
1}\left\lvert\sum_{i\in
S}\boldsymbol{\varepsilon}_{i}\left\lvert[\mathbf{S}\mathbf{A}\mathbf{x}](i)\right\rvert^{p}\right\rvert^{l},$

where $\boldsymbol{\varepsilon}\sim\\{\pm 1\\}^{n}$ are independent Rademacher
variables. In turn, the right hand side is bounded by

$2^{l}(\pi/2)^{l/2}\operatorname*{\mathbf{E}}_{\mathbf{S},\mathbf{g}}\sup_{\left\lVert\mathbf{A}\mathbf{x}\right\rVert_{p}\leq
1}\left\lvert\sum_{i\in
S}\mathbf{g}_{i}\left\lvert[\mathbf{S}\mathbf{A}\mathbf{x}](i)\right\rvert^{p}\right\rvert^{l}$

via a Rademacher-Gaussian comparison theorem (see, e.g., Equation 4.8 of
[LT91]). ∎

###  7.1 Sensitivity Sampling, $p<2$

Our first result is a sensitivity sampling guarantee for $p<2$.

######  Theorem 7.2 (Sensitivity Sampling for $p<2$).

Let $\mathbf{A}\in\mathbb{R}^{n\times d}$ and $1\leq p<2$. Let $\mathbf{S}$ be
a random $\ell_{p}$ sampling matrix with sampling probabilities
$q_{i}=\min\\{1,1/n+\boldsymbol{\sigma}_{i}^{p}(\mathbf{A})/\alpha\\}$ for an
oversampling parameter $\alpha$ set to

$\displaystyle\frac{1}{\alpha}$
$\displaystyle=\frac{\mathfrak{S}^{p}(\mathbf{A})^{2/p-1}}{\varepsilon^{2}}\left[O(l\log
n)^{2/p-1}\left\lparen\frac{\log d}{2-p}+\log\frac{l\log
n}{\varepsilon}\right\rparen(\log d)^{2}+l\right]$
$\displaystyle=\frac{\mathfrak{S}^{p}(\mathbf{A})^{2/p-1}}{\varepsilon^{2}}\operatorname{poly}\left\lparen\log
n,\log\frac{1}{\delta},\frac{1}{2-p}\right\rparen$

for

$l=O\left\lparen\log\frac{1}{\delta}+\log\log
n+\log\frac{1}{2-p}+\log\frac{d}{\varepsilon}\right\rparen.$

Then, with probability at least $1-\delta$, simultaneously for all
$\mathbf{x}\in\mathbb{R}^{d}$,

$\left\lVert\mathbf{S}\mathbf{A}\mathbf{x}\right\rVert_{p}^{p}=(1\pm\varepsilon)\left\lVert\mathbf{A}\mathbf{x}\right\rVert_{p}^{p}.$

Furthermore, with probability at least $1-\delta$, $\mathbf{S}$ samples

$\frac{\mathfrak{S}^{p}(\mathbf{A})^{2/p}}{\varepsilon^{2}}\operatorname{poly}\left\lparen\log
n,\log\frac{1}{\delta},\log\frac{1}{2-p}\right\rparen$

rows.

###### Proof.

Our approach is to bound

$\operatorname*{\mathbf{E}}_{\mathbf{S}}\sup_{\left\lVert\mathbf{A}\mathbf{x}\right\rVert_{p}=1}\left\lvert\left\lVert\mathbf{S}\mathbf{A}\mathbf{x}\right\rVert_{p}^{p}-1\right\rvert^{l}$

for a large even integer $l$. Using Lemma 7.1, we first bound

$\operatorname*{\mathbf{E}}_{\mathbf{S}}\sup_{\left\lVert\mathbf{A}\mathbf{x}\right\rVert_{p}=1}\left\lvert\left\lVert\mathbf{S}\mathbf{A}\mathbf{x}\right\rVert_{p}^{p}-1\right\rvert^{l}\leq(2\pi)^{l/2}\operatorname*{\mathbf{E}}_{\mathbf{S}}\operatorname*{\mathbf{E}}_{\mathbf{g}\sim\mathcal{N}(0,\mathbf{I}_{n})}\sup_{\left\lVert\mathbf{A}\mathbf{x}\right\rVert_{p}=1}\left\lvert\sum_{i\in
S}\mathbf{g}_{i}\left\lvert[\mathbf{S}\mathbf{A}\mathbf{x}](i)\right\rvert^{p}\right\rvert^{l}$

where $S=\\{i\in[n]:q_{i}<1\\}$. For simplicity of presentation, we assume
$S=[n]$, which will not affect our proof.

By Theorem 1.8, there exists a matrix
$\mathbf{A}^{\prime}\in\mathbb{R}^{m_{1}\times d}$ with $m_{1}=O(d(\log
d)^{3})$ such that

$\lVert\mathbf{A}^{\prime}\mathbf{x}\rVert_{p}^{p}=(1\pm
1/2)\lVert\mathbf{A}\mathbf{x}\rVert_{p}^{p}$

for all $\mathbf{x}\in\mathbb{R}^{d}$. Furthermore, because
$\mathbf{A}^{\prime}$ in Theorem 1.8 is constructed by random sampling, Lemma
4.1 shows that $\mathfrak{S}^{p}(\mathbf{A}^{\prime})\leq
8\mathfrak{S}^{p}(\mathbf{A})$ (note that we only need existence of this
matrix). We then construct a matrix
$\mathbf{A}^{\prime\prime}\in\mathbb{R}^{m_{2}\times d}$ with
$m_{2}=O(\alpha^{-1}\mathfrak{S}^{p}(\mathbf{A})+d(\log
d)^{3})=O(\alpha^{-1}\mathfrak{S}^{p}(\mathbf{A}))$ such that

$\sigma\coloneqq\max_{i=1}^{n}\boldsymbol{\sigma}_{i}^{p}(\mathbf{A}^{\prime\prime})\leq\alpha,$

$\mathfrak{S}^{p}(\mathbf{A}^{\prime})=\mathfrak{S}^{p}(\mathbf{A}^{\prime\prime})$,
and
$\lVert\mathbf{A}^{\prime}\mathbf{x}\rVert_{p}=\lVert\mathbf{A}^{\prime\prime}\mathbf{x}\rVert_{p}$
for all $\mathbf{x}\in\mathbb{R}^{d}$ by viewing $\mathbf{A}^{\prime}$ as an
$(m_{1}+\alpha^{-1}\mathfrak{S}^{p}(\mathbf{A}))\times d$ matrix with all
zeros except for the first $m_{1}$ rows and then applying Lemma 4.4.

Now let

$\mathbf{A}^{\prime\prime\prime}\coloneqq\begin{pmatrix}\mathbf{A}^{\prime\prime}\\\
\mathbf{S}\mathbf{A}\end{pmatrix}$

be the $(m_{2}+n_{\mathbf{S}})\times d$ matrix formed by the vertical
concatenation of $\mathbf{A}^{\prime\prime}$ with $\mathbf{S}\mathbf{A}$,
where $n_{\mathbf{S}}$ is the number of rows sampled by $\mathbf{S}$.

##### Sensitivity Bounds for $\mathbf{A}^{\prime\prime\prime}$.

We will first bound the $\ell_{p}$ sensitivities of
$\mathbf{A}^{\prime\prime\prime}$. For any row $i$ corresponding to a row of
$\mathbf{A}^{\prime\prime}$, the $\ell_{p}$ sensitivities are already bounded
by $\alpha$, and furthermore, $\ell_{p}$ sensitivities can clearly only
decrease with row additions. For any row $i$ corresponding to a row of
$\mathbf{S}\mathbf{A}$ that is sampled with probability $q_{i}<1$, we have
that

$\frac{\left\lvert[\mathbf{S}\mathbf{A}\mathbf{x}](i)\right\rvert^{p}}{\left\lVert\mathbf{A}^{\prime\prime\prime}\mathbf{x}\right\rVert_{p}^{p}}\leq
2\frac{\left\lvert[\mathbf{S}\mathbf{A}\mathbf{x}](i)\right\rvert^{p}}{\left\lVert\mathbf{A}\mathbf{x}\right\rVert_{p}^{p}}\leq
2\frac{1}{q_{i}}\frac{\left\lvert[\mathbf{A}\mathbf{x}](i)\right\rvert^{p}}{\left\lVert\mathbf{A}\mathbf{x}\right\rVert_{p}^{p}}\leq
2\frac{\boldsymbol{\sigma}_{i}^{p}(\mathbf{A})}{q_{i}}=2\alpha.$

Thus, we have that
$\boldsymbol{\sigma}_{i}^{p}(\mathbf{A}^{\prime\prime\prime})\leq 2\alpha$ for
every row $i$ of $\mathbf{A}^{\prime\prime\prime}$.

With a bound on the $\ell_{p}$ sensitivities of
$\mathbf{A}^{\prime\prime\prime}$ in hand, we may then convert this into a
bound on the leverage scores of $\mathbf{A}^{\prime\prime\prime}$ using Lemma
2.3, which gives

$\tau\coloneqq\max_{i=1}^{n}\boldsymbol{\tau}_{i}(\mathbf{A}^{\prime\prime\prime})\leq(2\alpha)^{2/p}(m_{2}+n_{\mathbf{S}})^{2/p-1}$

where $n_{\mathbf{S}}$ is the number of nonzero entries of $\mathbf{S}$.

##### Moment Bounds on the Sampling Error.

We now fix a choice of $\mathbf{S}$, and define

$F_{\mathbf{S}}\coloneqq\sup_{\left\lVert\mathbf{A}\mathbf{x}\right\rVert_{p}=1}\left\lvert\left\lVert\mathbf{S}\mathbf{A}\mathbf{x}\right\rVert_{p}^{p}-1\right\rvert.$

Note that the event that $n_{\mathbf{S}}$ is at least

$n_{\mathrm{thresh}}\coloneqq O(l\log
n)\operatorname*{\mathbf{E}}[n_{S}]=O(l\log
n)\alpha^{-1}\mathfrak{S}^{p}(\mathbf{A}),$

occurs with probability at most $\operatorname{poly}(n)^{-l}$ by Chernoff
bounds over the randomness of $\mathbf{S}$, and

$F_{\mathbf{S}}^{l}\leq\left[1+\sum_{i=1}^{n}\frac{1}{q_{i}}\right]^{l}\leq(n+1)^{2l},$

and thus this event contributes at most $\operatorname{poly}(n)^{-l}$ to the
moment bound $\operatorname*{\mathbf{E}}F_{\mathbf{S}}^{l}$. Thus, we focus on
bounding $\operatorname*{\mathbf{E}}F_{\mathbf{S}}^{l}$ conditioned on
$n_{\mathbf{S}}\leq n_{\mathrm{thresh}}$. Define

$G_{\mathbf{S}}\coloneqq\sup_{\left\lVert\mathbf{A}^{\prime\prime\prime}\mathbf{x}\right\rVert_{p}=1}\left\lvert\sum_{i=1}^{m_{2}+n_{\mathbf{S}}}\mathbf{g}_{i}\left\lvert[\mathbf{A}^{\prime\prime\prime}\mathbf{x}](i)\right\rvert^{p}\right\rvert$

for $\mathbf{g}\sim\mathcal{N}(0,\mathbf{I}_{m_{2}+n_{\mathbf{S}}})$. Then,

$\left\lVert\mathbf{A}^{\prime\prime\prime}\mathbf{x}\right\rVert_{p}^{p}\leq(1+2+F_{\mathbf{S}})\left\lVert\mathbf{A}\mathbf{x}\right\rVert_{p}^{p}$

so

$\displaystyle F_{\mathbf{S}}^{l}$ $\displaystyle\leq
2^{l}\sup_{\left\lVert\mathbf{A}\mathbf{x}\right\rVert_{p}=1}\left\lvert\sum_{i=1}^{m_{2}+n_{\mathbf{S}}}\mathbf{g}_{i}\left\lvert[\mathbf{A}^{\prime\prime\prime}\mathbf{x}](i)\right\rvert^{p}\right\rvert^{l}$
(8) $\displaystyle\leq
2^{l}(1+2+F_{\mathbf{S}})^{l}\sup_{\left\lVert\mathbf{A}^{\prime\prime\prime}\mathbf{x}\right\rVert_{p}=1}\left\lvert\sum_{i=1}^{m_{2}+n_{\mathbf{S}}}\mathbf{g}_{i}\left\lvert[\mathbf{A}^{\prime\prime\prime}\mathbf{x}](i)\right\rvert^{p}\right\rvert^{l}$
$\displaystyle\leq 2^{2l-1}(3^{l}+F_{\mathbf{S}}^{l})G_{\mathbf{S}}^{l}.$

We then take expectations on both sides with respect to
$\mathbf{g}\sim\mathcal{N}(0,\mathbf{I}_{m_{2}+n_{\mathbf{S}}})$, and bound
the right hand side using Lemma 6.8, which gives

$\operatorname*{\mathbf{E}}_{\mathbf{g}\sim\mathcal{N}(0,\mathbf{I}_{m_{2}+n_{\mathbf{S}}})}G_{\mathbf{S}}^{l}\leq\left\lparen
2\mathcal{E}\right\rparen^{l}\frac{\mathcal{E}}{\mathcal{D}}+O(\sqrt{l}\mathcal{D})^{l}$

where $\mathcal{E}$ is the entropy integral and $\mathcal{D}=4\sigma^{1/2}$ is
the diameter by Lemma 6.4. We have by Lemma 6.6 that

$\displaystyle\mathcal{E}$ $\displaystyle\leq
O(\tau^{1/2})\left\lparen\frac{\log
d}{2-p}+\log(m_{2}+n_{\mathbf{S}})\right\rparen^{1/2}\log\frac{d\sigma}{\tau}$
$\displaystyle\leq
O(\alpha^{1/p}(m_{2}+n_{\mathbf{S}})^{1/p-1/2})\left\lparen\frac{\log
d}{2-p}+\log(m_{2}+n_{\mathbf{S}})\right\rparen^{1/2}\log\frac{d\sigma}{\tau}$

Thus, conditioned on $n_{\mathbf{S}}\leq n_{\mathrm{thresh}}$, we have that

$\operatorname*{\mathbf{E}}_{\mathbf{g}\sim\mathcal{N}(0,\mathbf{I}_{m_{2}+n_{\mathbf{S}}})}G_{\mathbf{S}}^{l}\leq\left[O(\alpha^{1/p}n_{\mathrm{thresh}}^{1/p-1/2})\left\lparen\frac{\log
d}{2-p}+\log n_{\mathrm{thresh}}\right\rparen^{1/2}\log
d\right]^{l}+O(\sqrt{l}\sqrt{\alpha})^{l}.$

Note that

$\alpha^{1/p}n_{\mathrm{thresh}}^{1/p-1/2}=O(l\log
n)^{1/p-1/2}\alpha^{1/p}(\alpha^{-1}\mathfrak{S}^{p}(\mathbf{A}))^{1/p-1/2}=O(l\log
n)^{1/p-1/2}\alpha^{1/2}\mathfrak{S}^{p}(\mathbf{A})^{1/p-1/2},$

which shows that

$\operatorname*{\mathbf{E}}_{\mathbf{g}\sim\mathcal{N}(0,\mathbf{I}_{m_{2}+n_{\mathbf{S}}})}G_{\mathbf{S}}^{l}\leq\varepsilon^{l}\delta$

due to our choice of $\alpha$ and $l$.

Now if we take conditional expectations on both sides of (8) conditioned on
the event $\mathcal{F}$ that $n_{\mathbf{S}}\leq n_{\mathrm{thresh}}$, then we
have

$\operatorname*{\mathbf{E}}[F_{\mathbf{S}}^{l}\mid\mathcal{F}]\leq
2^{2l-1}(3^{l}+\operatorname*{\mathbf{E}}[F_{\mathbf{S}}^{l}\mid\mathcal{F}])\varepsilon^{l}\delta\leq(3^{l}+\operatorname*{\mathbf{E}}[F_{\mathbf{S}}^{l}\mid\mathcal{F}])(4\varepsilon)^{l}\delta$

which means

$\operatorname*{\mathbf{E}}[F_{\mathbf{S}}^{l}\mid\mathcal{F}]\leq\frac{(12\varepsilon)^{l}\delta}{1-(4\varepsilon)^{l}\delta}\leq
2(12\varepsilon)^{l}\delta$

for $(4\varepsilon)^{l}\delta\leq 1/2$. We thus have

$\operatorname*{\mathbf{E}}[F_{\mathbf{S}}^{l}]\leq\frac{(12\varepsilon)^{l}\delta}{1-(4\varepsilon)^{l}\delta}\leq
2(12\varepsilon)^{l}\delta+\operatorname{poly}(n)^{-l}$

altogether. Finally, we have by a Markov bound that

$F_{\mathbf{S}}^{l}\leq
2(12\varepsilon)^{l}+\frac{1}{\delta}\operatorname{poly}(n)^{l}\leq
3(12\varepsilon)^{l}$

with probability at least $1-\delta$, which means that

$F_{\mathbf{S}}\leq 3\cdot 12\varepsilon=36\varepsilon$

with probability at least $1-\delta$. Rescaling $\varepsilon$ by constant
factors yields the claimed result. ∎

###  7.2 Sensitivity Sampling, $p>2$

For $p>2$, we first need a construction of a matrix with a small number of
rows and small sensitivity. While this construction can be made to be a
randomized algorithm succeeding with high probability, it uses a sophisticated
recursive sampling strategy. While this is necessary for our results later in
Theorem 7.10, such a complicated algorithm may be undesirable. In Theorem 7.4,
we use this result to show that a more direct one-shot sensitivity sampling
can in fact achieve a similar guarantee.

######  Lemma 7.3 (Recursive Sensitivity Sampling).

Let $\mathbf{A}\in\mathbb{R}^{n\times d}$ and $2<p<\infty$. Let
$0<\varepsilon<1$. Then, there exists a matrix
$\mathbf{A}^{\prime}\in\mathbb{R}^{m\times d}$ for

$m=O(p^{2})\frac{\mathfrak{S}^{p}(\mathbf{A})^{2-2/p}}{\varepsilon^{2}}\log(pd)^{2}\log\frac{pd}{\varepsilon}$

such that

$\left\lVert\mathbf{A}^{\prime}\mathbf{x}\right\rVert_{p}^{p}=(1\pm\varepsilon)\left\lVert\mathbf{A}\mathbf{x}\right\rVert_{p}^{p}$

for every $\mathbf{x}\in\mathbb{R}^{d}$ and
$\mathfrak{S}^{p}(\mathbf{A}^{\prime})\leq(1+O(\varepsilon))\mathfrak{S}^{p}(\mathbf{A})$.

###### Proof.

Let $\mathbf{A}^{\prime}\in\mathbb{R}^{m\times d}$ be the flattened isometric
matrix given by Lemma 4.4 with $C=4$, where $m\leq(5/4)n$. Then for all
$i\in[m]$, we have that

$\boldsymbol{\sigma}_{i}^{p}(\mathbf{A}^{\prime})\leq
4\frac{\mathfrak{S}^{p}(\mathbf{A})}{n}\leq
5\frac{\mathfrak{S}^{p}(\mathbf{A}^{\prime})}{m}.$

Now consider the random sampling matrix $\mathbf{S}$ with sampling
probabilities $q_{i}=1/2$. Note then that sampling with probability
$q_{i}=1/2$ and scaling by $1/q_{i}=2$ corresponds to muliplying by the random
variable $\boldsymbol{\varepsilon}_{i}+1$, where
$\boldsymbol{\varepsilon}_{i}$ is a Rademacher variable. Thus,

$\operatorname*{\mathbf{E}}_{\mathbf{S}}\sup_{\left\lVert\mathbf{A}^{\prime}\mathbf{x}\right\rVert_{p}=1}\left\lvert\left\lVert\mathbf{S}\mathbf{A}^{\prime}\mathbf{x}\right\rVert_{p}^{p}-1\right\rvert=\operatorname*{\mathbf{E}}_{\boldsymbol{\varepsilon}}\sup_{\left\lVert\mathbf{A}^{\prime}\mathbf{x}\right\rVert_{p}=1}\left\lvert\sum_{i=1}^{n}(\boldsymbol{\varepsilon}_{i}+1)\left\lvert[\mathbf{A}^{\prime}\mathbf{x}](i)\right\rvert^{p}-\left\lvert[\mathbf{A}^{\prime}\mathbf{x}](i)\right\rvert^{p}\right\rvert=\operatorname*{\mathbf{E}}_{\boldsymbol{\varepsilon}}\sup_{\left\lVert\mathbf{A}^{\prime}\mathbf{x}\right\rVert_{p}=1}\left\lvert\sum_{i=1}^{n}\boldsymbol{\varepsilon}_{i}\left\lvert[\mathbf{A}^{\prime}\mathbf{x}](i)\right\rvert^{p}\right\rvert.$

By Lemma 7.1 and Theorem 6.2, this is bounded by

$O(1)\int_{0}^{\infty}\sqrt{\log E(T,d_{X},u)}~{}du\leq
O(p\tau^{1/2})\cdot(\sigma n)^{1/2-1/p}(\log
n)^{1/2}\cdot\log\frac{p^{2}d\sigma}{\tau}$

where $\tau$ is an upper bound on the leverage scores of $\mathbf{A}^{\prime}$
and $\sigma$ is an upper bound on the $\ell_{p}$ sensitivities of
$\mathbf{A}^{\prime}$. By Lemma 2.2, we have that $\tau\leq\sigma$, and
furthermore, we can take $\sigma=5\mathfrak{S}^{p}(\mathbf{A}^{\prime})/m$.
Thus, the resulting bound on the expected sampling error is at most

$\varepsilon_{\mathbf{A}}\coloneqq
O(p)\frac{\mathfrak{S}^{p}(\mathbf{A})^{1-1/p}}{\sqrt{n}}(\log
n)^{1/2}\log(pd)$

so with probability at least $99/100$, the same bound holds up to a factor of
$100$. Furthermore, $\mathbf{S}$ samples $m/2\leq(5/8)n$ rows in expectation,
so by Markov’s inequality, it samples at most $(3/2)m/2\leq(15/16)n$ rows with
probability at least $1/3$. We also have that

$\frac{\boldsymbol{\sigma}_{i}^{p}(\mathbf{A})}{q_{i}}=2\boldsymbol{\sigma}_{i}^{p}(\mathbf{A}^{\prime})\leq
10\frac{\mathfrak{S}^{p}(\mathbf{A}^{\prime})}{m}$

so by Lemma 4.2, we have that

$\operatorname*{\mathbf{Pr}}\left\\{\mathfrak{S}^{p}(\mathbf{S}\mathbf{A}^{\prime})=(1\pm
O(\varepsilon_{\mathbf{A}}))\mathfrak{S}^{p}(\mathbf{A})\right\\}\geq\frac{99}{100}.$

By a union bound, $\mathbf{S}\mathbf{A}^{\prime}$ samples at most $(15/16)n$
rows, has sampling error at most $\varepsilon_{n}$, and has $\ell_{p}$ total
sensitivity at most
$(1+O(\varepsilon_{\mathbf{A}}))\mathfrak{S}^{p}(\mathbf{A})$ with probability
at least $1/3-1/100-1/100>0$. Thus, such an instantiation of
$\mathbf{S}\mathbf{A}^{\prime}$ exists.

We now recursively apply our reasoning, by repeatedly applying the flattening
and sampling operation. Note that each time we repeat this procedure, the
number of rows goes down by a factor of $15/16$, while the total sensitivity
and total sampling error accumulates. Let $\mathbf{A}_{l}$ denote the matrix
obtained after $l$ recursive applications of this procedure and let $n_{l}$
denote the number of rows of $\mathbf{A}_{l}$. Then,

$\displaystyle\varepsilon_{\mathbf{A}_{l+1}}$
$\displaystyle=O(p)\frac{\mathfrak{S}^{p}(\mathbf{A}_{l+1})^{1-1/p}}{\sqrt{n}_{l+1}}(\log
n_{l+1})^{1/2}\log(pd)$
$\displaystyle\geq(1-O(\varepsilon_{\mathbf{A}_{l}}))O(p)\frac{\mathfrak{S}^{p}(\mathbf{A}_{l})^{1-1/p}}{\sqrt{n}_{l+1}}(\log
n_{l+1})^{1/2}\log(pd)$
$\displaystyle\geq\sqrt{\frac{16}{15}}(1-O(\varepsilon_{\mathbf{A}_{l}}))O(p)\frac{\mathfrak{S}^{p}(\mathbf{A}_{l})^{1-1/p}}{\sqrt{n}_{l}}(\log
n_{l})^{1/2}\log(pd)$
$\displaystyle\geq\frac{101}{100}\cdot\varepsilon_{\mathbf{A}_{l}}$

as long as $\varepsilon_{\mathbf{A}_{l}}$ is less than some absolute constant.
Thus, the sum of the $\varepsilon_{\mathbf{A}_{l}}$ are dominated by the last
$\varepsilon_{\mathbf{A}_{l}}$, up to a constant factor. Now let $L$ be the
smallest integer $l$ such that $\varepsilon_{\mathbf{A}_{l}}\leq\varepsilon$.
Then, we have that

$\mathfrak{S}^{p}(\mathbf{A}_{L})\leq(1+O(\varepsilon))\mathfrak{S}^{p}(\mathbf{A})$

and thus

$\left\lVert\mathbf{A}_{L}\mathbf{x}\right\rVert_{p}^{p}=(1\pm
O(\varepsilon))\left\lVert\mathbf{A}\mathbf{x}\right\rVert_{p}^{p}$

for every $\mathbf{x}\in\mathbb{R}^{d}$. Furthermore, $n_{L}$ satisfies

$\varepsilon=O(p)\frac{\mathfrak{S}^{p}(\mathbf{A})^{1-1/p}}{\sqrt{n}_{L}}(\log
n_{L})^{1/2}\log(pd)$

or

$n_{L}=O(p^{2})\frac{\mathfrak{S}^{p}(\mathbf{A})^{2-2/p}}{\varepsilon^{2}}\log(pd)^{2}\log\frac{pd}{\varepsilon}.$

∎

######  Theorem 7.4 (Sensitivity Sampling for $p>2$).

Let $\mathbf{A}\in\mathbb{R}^{n\times d}$ and $2<p<\infty$. Let $\mathbf{S}$
be a random $\ell_{p}$ sampling matrix with sampling probabilities
$q_{i}=\min\\{1,1/n+\boldsymbol{\sigma}_{i}^{p}(\mathbf{A})/\alpha\\}$ for an
oversampling parameter $\alpha$ set to

$\displaystyle\frac{1}{\alpha}$
$\displaystyle=O(p^{2})\mathfrak{S}^{p}(\mathbf{A})^{1-2/p}(l\log
n)^{1-2/p}\log(pd)\log\frac{l\log n}{\varepsilon}+O(p^{2})l$

for

$l=O\left\lparen\log\frac{1}{\delta}+\log\log n+\log
p+\log\frac{\mathfrak{S}^{p}(\mathbf{A})}{\varepsilon}\right\rparen.$

Then, with probability at least $1-\delta$, simultaneously for all
$\mathbf{x}\in\mathbb{R}^{d}$,

$\left\lVert\mathbf{S}\mathbf{A}\mathbf{x}\right\rVert_{p}^{p}=(1\pm\varepsilon)\left\lVert\mathbf{A}\mathbf{x}\right\rVert_{p}^{p}.$

Furthermore, with probability at least $1-\delta$, $\mathbf{S}$ samples

$\frac{\mathfrak{S}^{p}(\mathbf{A})^{2-2/p}}{\varepsilon^{2}}\operatorname{poly}\left\lparen\log
n,\log\frac{1}{\delta},p\right\rparen$

rows.

###### Proof.

Our approach is to bound

$\operatorname*{\mathbf{E}}_{\mathbf{S}}\sup_{\left\lVert\mathbf{A}\mathbf{x}\right\rVert_{p}=1}\left\lvert\left\lVert\mathbf{S}\mathbf{A}\mathbf{x}\right\rVert_{p}^{p}-1\right\rvert^{l}$

for a large even integer $l$. Using Lemma 7.1, we first bound

$\operatorname*{\mathbf{E}}_{\mathbf{S}}\sup_{\left\lVert\mathbf{A}\mathbf{x}\right\rVert_{p}=1}\left\lvert\left\lVert\mathbf{S}\mathbf{A}\mathbf{x}\right\rVert_{p}^{p}-1\right\rvert^{l}\leq(2\pi)^{l/2}\operatorname*{\mathbf{E}}_{\mathbf{S}}\operatorname*{\mathbf{E}}_{\mathbf{g}\sim\mathcal{N}(0,\mathbf{I}_{n})}\sup_{\left\lVert\mathbf{A}\mathbf{x}\right\rVert_{p}=1}\left\lvert\sum_{i\in
S}\mathbf{g}_{i}\left\lvert[\mathbf{S}\mathbf{A}\mathbf{x}](i)\right\rvert^{p}\right\rvert^{l}$

where $S=\\{i\in[n]:q_{i}<1\\}$. For simplicity of presentation, we assume
$S=[n]$, which will not affect our proof.

By Lemma 7.3, there exists a matrix
$\mathbf{A}^{\prime}\in\mathbb{R}^{m_{1}\times d}$ with
$m_{1}=O(\mathfrak{S}^{2-2/p}\log(pd)^{3})$ such that

$\left\lVert\mathbf{A}^{\prime}\mathbf{x}\right\rVert_{p}^{p}=(1\pm
1/2)\left\lVert\mathbf{A}\mathbf{x}\right\rVert_{p}^{p}$

for all $\mathbf{x}\in\mathbb{R}^{d}$, and
$\mathfrak{S}^{p}(\mathbf{A}^{\prime})\leq O(1)\mathfrak{S}^{p}(\mathbf{A})$.
Then for $m_{2}=O(m_{1}+\mathfrak{S}^{p}(\mathbf{A})\alpha^{-1})$, let
$\mathbf{A}^{\prime\prime}\in\mathbb{R}^{m_{2}\times d}$ be the matrix given
by Lemma 4.4 such that
$\boldsymbol{\sigma}_{i}^{p}(\mathbf{A}^{\prime\prime})\leq\alpha$ for every
$i\in[m_{2}]$ and
$\left\lVert\mathbf{A}^{\prime\prime}\mathbf{x}\right\rVert_{p}=\left\lVert\mathbf{A}^{\prime}\mathbf{x}\right\rVert_{p}$
for every $\mathbf{x}\in\mathbb{R}^{d}$. Now let

$\mathbf{A}^{\prime\prime\prime}\coloneqq\begin{pmatrix}\mathbf{A}^{\prime\prime}\\\
\mathbf{S}\mathbf{A}\end{pmatrix}$

be the $(m_{2}+n_{\mathbf{S}})\times d$ matrix formed by the vertical
concatenation of $\mathbf{A}^{\prime\prime}$ with $\mathbf{S}\mathbf{A}$,
where $n_{\mathbf{S}}$ is the number of rows sampled by $\mathbf{S}$.

##### Sensitivity Bounds for $\mathbf{A}^{\prime\prime\prime}$.

We will first bound the $\ell_{p}$ sensitivities of
$\mathbf{A}^{\prime\prime\prime}$. For any row $i$ corresponding to a row of
$\mathbf{A}^{\prime\prime}$, the $\ell_{p}$ sensitivities are already bounded
by $\alpha$, and furthermore, $\ell_{p}$ sensitivities can only decrease with
row additions. For any row $i$ corresponding to a row of
$\mathbf{S}\mathbf{A}$ that is sampled with probability $q_{i}<1$, we have
that

$\frac{\lvert[\mathbf{S}\mathbf{A}\mathbf{x}](i)\rvert^{p}}{\left\lVert\mathbf{A}^{\prime\prime\prime}\mathbf{x}\right\rVert_{p}^{p}}\leq\frac{\lvert[\mathbf{S}\mathbf{A}\mathbf{x}](i)\rvert^{p}}{\left\lVert\mathbf{A}^{\prime\prime}\mathbf{x}\right\rVert_{p}^{p}}\leq
2\frac{\lvert[\mathbf{S}\mathbf{A}\mathbf{x}](i)\rvert^{p}}{\left\lVert\mathbf{A}\mathbf{x}\right\rVert_{p}^{p}}\leq
2\alpha.$

By Lemma 2.2, this immediately implies that the $\ell_{2}$ sensitivities, or
the leverage scores, are also bounded by $2\alpha$.

##### Moment Bounds on Sampling Error.

We now fix a choice of $\mathbf{S}$, and define

$F_{\mathbf{S}}\coloneqq\sup_{\left\lVert\mathbf{A}\mathbf{x}\right\rVert_{p}=1}\left\lvert\left\lVert\mathbf{S}\mathbf{A}\mathbf{x}\right\rVert_{p}^{p}-1\right\rvert$

Note that the event that $n_{\mathbf{S}}$ is at least

$n_{\mathrm{thresh}}\coloneqq O(l\log
n)\operatorname*{\mathbf{E}}[n_{S}]=O(l\log
n)\alpha^{-1}\mathfrak{S}^{p}(\mathbf{A}),$

occurs with probability at most $\operatorname{poly}(n)^{-l}$ by Chernoff
bounds over the randomness of $\mathbf{S}$, and

$F_{\mathbf{S}}^{l}\leq\left[1+\sum_{i=1}^{n}\frac{1}{q_{i}}\right]^{l}\leq(n+1)^{2l},$

and thus this event contributes at most $\operatorname{poly}(n)^{-l}$ to the
moment bound $\operatorname*{\mathbf{E}}F_{\mathbf{S}}^{l}$. Thus, we focus on
bounding $\operatorname*{\mathbf{E}}F_{\mathbf{S}}^{l}$ conditioned on
$n_{\mathbf{S}}\leq n_{\mathrm{thresh}}$. Now define

$G_{\mathbf{S}}\coloneqq\sup_{\left\lVert\mathbf{A}^{\prime\prime\prime}\mathbf{x}\right\rVert_{p}=1}\left\lvert\sum_{i=1}^{m_{2}+n_{\mathbf{S}}}\mathbf{g}_{i}\left\lvert[\mathbf{A}^{\prime\prime\prime}\mathbf{x}](i)\right\rvert^{p}\right\rvert$

for $\mathbf{g}\sim\mathcal{N}(0,\mathbf{I}_{m_{2}+n_{\mathbf{S}}})$. Then,

$\left\lVert\mathbf{A}^{\prime\prime\prime}\mathbf{x}\right\rVert_{p}^{p}\leq(1+2+F_{\mathbf{S}})\left\lVert\mathbf{A}\mathbf{x}\right\rVert_{p}^{p}$

so

$\displaystyle F_{\mathbf{S}}^{l}$ $\displaystyle\leq
2^{l}\sup_{\left\lVert\mathbf{A}\mathbf{x}\right\rVert_{p}=1}\left\lvert\sum_{i=1}^{m_{2}+n_{\mathbf{S}}}\mathbf{g}_{i}\left\lvert[\mathbf{A}^{\prime\prime\prime}\mathbf{x}](i)\right\rvert^{p}\right\rvert^{l}$
(9) $\displaystyle\leq
2^{l}(1+2+F_{\mathbf{S}})^{l}\sup_{\left\lVert\mathbf{A}^{\prime\prime\prime}\mathbf{x}\right\rVert_{p}=1}\left\lvert\sum_{i=1}^{m_{2}+n_{\mathbf{S}}}\mathbf{g}_{i}\left\lvert[\mathbf{A}^{\prime\prime\prime}\mathbf{x}](i)\right\rvert^{p}\right\rvert^{l}$
$\displaystyle\leq 2^{2l-1}(3^{l}+F_{\mathbf{S}}^{l})G_{\mathbf{S}}^{l}.$

We then take expectations on both sides with respect to
$\mathbf{g}\sim\mathcal{N}(0,\mathbf{I}_{m_{2}+n_{\mathbf{S}}})$, and bound
the right hand side using Lemma 6.8, which gives

$\operatorname*{\mathbf{E}}_{\mathbf{g}\sim\mathcal{N}(0,\mathbf{I}_{m_{2}+n_{\mathbf{S}}})}G_{\mathbf{S}}^{l}\leq\left\lparen
2\mathcal{E}\right\rparen^{l}\frac{\mathcal{E}}{\mathcal{D}}+O(\sqrt{l}\mathcal{D})^{l}$