Nearly Optimal Strong Coresets for ${\mathrm{\ell }}_p$ Subspace Approximation

We study strong coresets for ${\mathrm{\ell }}_p$ subspace approximation. Given $\text{A}\in {\mathbb{R}}^{n\times d}$, the goal is to sample and rescale a small number of its rows to form $\text{Smat}\text{A}$ such that $$\text{norm}{\text{Smat}\text{A}(\text{I}-{\text{Pmat}}_F)}_{p,2}^p=(1\pm \text{eps})\text{norm}{\text{A}(\text{I}-{\text{Pmat}}_F)}_{p,2}^p$$ simultaneously for every subspace $F\subseteq {\mathbb{R}}^d$ of dimension at most $k$, where ${\text{Pmat}}_F$ is the orthogonal projector onto $F$. Woodruff and Yasuda (FOCS 2025)~\cite{WY25} obtained coreset sizes ${\text{wtO}}_p(k{\text{eps}}^{-4\mathrm{/}p})$ for $1\le p<2$ and ${\text{wtO}}_p(k^{p\mathrm{/}2}{\text{eps}}^{-p})$ for $p>2$. We improve these bounds to ${\text{wtO}}_p(k{\text{eps}}^{-2})$ and ${\text{wtO}}_p(k^{p\mathrm{/}2}{\text{eps}}^{-2})$, respectively. For $1\le p<2$, our algorithm runs in ${\text{wtO}}_p(\text{nnz}(\text{A})+d^{\omega }+k{\text{eps}}^{-2})$ time. The resulting coreset size matches the known sampling lower bound~\cite{LWW21} up to logarithmic factors when $k+1\ge C\log (1\mathrm{/}\text{eps})$ for an absolute constant $C$. For $p>2$, our algorithm runs in ${\text{wtO}}_p(\text{nnz}(\text{A})+d^{\omega })$ time, matching the running time of the Woodruff–Yasuda framework. We use different techniques in the two regimes. For $1\le p<2$, we combine a bicriteria low-rank split with Lewis-weight sampling and empirical-process bounds independent of the output dimension. For $p>2$, we give a sharper analysis of the Woodruff–Yasuda construction. By retaining the truncation in its sampling probabilities throughout the row-count recurrence, we show that it achieves the improved ${\text{eps}}^{-2}$ dependence.