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

Abstract

We study strong coresets for ${\ell }_p$ subspace approximation. Given a matrix $A\in {\mathbb{R}}^{n\times d}$, the goal is to sample and rescale a small number of its rows to obtain $SA$ such that ${\Vert SA(I-P_F)\Vert }_{p,2}^p=(1\pm \epsilon ){\Vert A(I-P_F)\Vert }_{p,2}^p$ simultaneously for every subspace $F\subseteq {\mathbb{R}}^d$ of dimension at most $k$, where $P_F$ is the orthogonal projector onto $F$. Woodruff and Yasuda [WY25] (FOCS 2025) obtained coreset sizes ${\tilde{O}}_p(k{\epsilon }^{-4/p})$ for $1\le p<2$ and ${\tilde{O}}_p(k^{p/2}{\epsilon }^{-p})$ for $p>2$. We improve these bounds to ${\tilde{O}}_p(k{\epsilon }^{-2})$ and ${\tilde{O}}_p(k^{p/2}{\epsilon }^{-2})$, respectively. For $1\le p<2$, our algorithm runs in ${\tilde{O}}_p(\mathrm{nnz}(A)+d^{\omega }+k{\epsilon }^{-2})$ time. The resulting coreset size matches the sampling lower bound [LWW21] up to logarithmic factors when $k+1\ge C\log (1/\epsilon )$ for an absolute constant $C$. For $p>2$, our algorithm runs in ${\tilde{O}}_p(\mathrm{nnz}(A)+d^{\omega })$ time, matching the running time of the framework of Woodruff and Yasuda. 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 ${\epsilon }^{-2}$ dependence.