Strong Coresets for $\ell_p$ Subspace Approximation with Improved $\varepsilon$-Dependence for $p>2$
Abstract
We study strong coresets for $\ell_p$ subspace approximation in the regime
$p>2$.
The best previous dimension-independent construction, due to Woodruff and
Yasuda~\cite{WY25}, has size $\widetilde{O}_p(k^{p/2}\epsilon^{-p})$ and runs in nearly
input-sparsity time.
We give a refined analysis of root ridge leverage score sampling that improves
the coreset size to $\widetilde{O}_p(k^{p/2}\epsilon^{-2})$.
The analysis uses a threshold-aware aggregation of the truncated sampling
probabilities to obtain a sharper recursive row-count bound.
The resulting construction retains the running time
$\widetilde{O}(\mathrm{nnz}(A)+d^\omega)$ of the underlying sampling framework.
$p>2$.
The best previous dimension-independent construction, due to Woodruff and
Yasuda~\cite{WY25}, has size $\widetilde{O}_p(k^{p/2}\epsilon^{-p})$ and runs in nearly
input-sparsity time.
We give a refined analysis of root ridge leverage score sampling that improves
the coreset size to $\widetilde{O}_p(k^{p/2}\epsilon^{-2})$.
The analysis uses a threshold-aware aggregation of the truncated sampling
probabilities to obtain a sharper recursive row-count bound.
The resulting construction retains the running time
$\widetilde{O}(\mathrm{nnz}(A)+d^\omega)$ of the underlying sampling framework.
