Nearly Optimal Strong Coresets for $\ell_p$ Subspace Approximation
2026-08-26 • Data Structures and Algorithms
Data Structures and Algorithms
AI summaryⓘ
The authors study how to create strong coresets—small representative subsets—for approximating distances to low-dimensional subspaces under the 9p9 norm. They improve previous results by reducing the number of sampled rows needed, especially in how the approximation error depends on 9epsilon9 (the allowed error). For p between 1 and 2, their method runs efficiently and matches known lower bounds, while for p greater than 2, they refine existing techniques to achieve better error dependence. Their work uses different mathematical strategies depending on the value of p to achieve these improvements.
coresetssubspace approximationlp normLewis-weight samplingorthogonal projectorbicriteria low-rank approximationempirical process boundsrow samplingapproximation erroralgorithmic complexity
Authors
Honghao Lin, Vahab Mirrokni, David P. Woodruff
Abstract
We study strong coresets for $\ell_p$ subspace approximation. Given $\A\in\R^{n\times d}$, the goal is to sample and rescale a small number of its rows to form $\Smat\A$ such that \[ \norm{\Smat\A(\I-\Pmat_F)}_{p,2}^p =(1\pm\eps)\norm{\A(\I-\Pmat_F)}_{p,2}^p \] simultaneously for every subspace $F\subseteq\R^d$ of dimension at most $k$, where $\Pmat_F$ is the orthogonal projector onto $F$. Woodruff and Yasuda (FOCS 2025)~\cite{WY25} obtained coreset sizes $\wtO_p(k\eps^{-4/p})$ for $1\leq p<2$ and $\wtO_p(k^{p/2}\eps^{-p})$ for $p>2$. We improve these bounds to $\wtO_p(k\eps^{-2})$ and $\wtO_p(k^{p/2}\eps^{-2})$, respectively. For $1\leq p<2$, our algorithm runs in $\wtO_p(\nnz(\A)+d^ω+k\eps^{-2})$ time. The resulting coreset size matches the known sampling lower bound~\cite{LWW21} up to logarithmic factors when $k+1\geq C\log(1/\eps)$ for an absolute constant $C$. For $p>2$, our algorithm runs in $\wtO_p(\nnz(\A)+d^ω)$ time, matching the running time of the Woodruff--Yasuda framework. We use different techniques in the two regimes. For $1\leq 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 $\eps^{-2}$ dependence.