An Accuracy Obstruction for ℓₚ Row Sparsification

For every fixed real $p > 2$, the manuscript constructs full-column-rank
matrices with total $\ell_p$ sensitivity $\mathcal S = \Theta_p(d)$ for which
every nonnegative reweighted row subset preserving all $\|Ax\|_p^p$ within
$1 \pm \varepsilon$ needs $\Omega_p((\mathcal S + d)\varepsilon^{-p})$ rows,
in an explicit large-dimension regime. The matrices are grounded incidence
matrices of complete graphs, all of whose rows have the same sensitivity, and
an elementary support-dependent test potential proves the lower bound. For
the ordinary-sensitivity sampler with probabilities
$\min\{1, 1/n + s_i/\alpha\}$, even one successful realization forces the
same order of expected row count. This disproves the quadratic-accuracy
sensitivity-sampling bound $\widetilde O(\varepsilon^{-2}(\mathcal S + d))$
for $p > 2$: no fixed polylogarithmic factor can absorb the gap between
$\varepsilon^{-p}$ and $\varepsilon^{-2}$. The obstruction concerns the
dependence on $\varepsilon$; it does not rule out nearly linear dependence on
$\mathcal S + d$ at fixed accuracy.