A new theoretical analysis takes aim at a basic question in matrix algorithms: how much can the dependence on the requested accuracy ε be reduced when a single row coreset must work for every low-dimensional subspace? The paper studies dimension-independent strong row coresets for ℓp subspace approximation. Here, a coreset is a reweighted subset of the input rows whose cost is meant to stay within a stated error for a whole family of queries. The mathematical input is a matrix A with n rows and d columns, and the target guarantee is simultaneous over every subspace F of dimension at most k.
The headline result is a change in how the required row count scales with accuracy. For 1 ≤ p < 2, the reported coreset-size dependence is kε⁻², apart from logarithmic and p-dependent factors. For p > 2, it is k^(p/2)ε⁻², again up to logarithmic and p-dependent factors; the paper describes this as an improvement over an earlier ε⁻p dependence. In plain language, both ranges carry an inverse-accuracy term with exponent 2, while the rank term is different above p=2.
A split approach to sampling
The paper handles the two ranges with different constructions. For 1 ≤ p < 2, its analysis combines a bicriteria low-rank split, Lewis-weight sampling and empirical-process bounds that are independent of the output dimension. The row-selection primitives include independent Bernoulli inclusion sampling and independent sampling with replacement.
For p > 2, the proposed analysis keeps the Woodruff–Yasuda truncation inside a recursive row-count analysis. That arrangement is used to obtain the ε⁻² accuracy dependence in the reported bound.
A guarantee over every query
For 1 ≤ p < 2, the first theorem states that a randomized reweighted row subset preserves the cost for every rank-at-most-k subspace within 1 ± ε, with success probability at least 2/3. The guarantee is uniform across the entire query family, not limited to a single subspace.
For p > 2, the recursive reduction preserves every rank-at-most-k subspace cost within 1 ± ρ with probability at least 1 − η. The notation changes, but the structure is the same: a multiplicative guarantee applied simultaneously across the specified subspaces.
The comparison is strongest below p=2
The p < 2 result also comes with a conditional optimality statement. The upper bound is optimal up to logarithmic factors when k + 1 ≥ C log(1/ε), while the upper bound itself is stated without that extra condition. The near-optimality claim therefore applies in the stated parameter range, rather than to every possible relationship between k and ε.
For p > 2, the paper is more cautious. It states that the known lower bound does not match the new upper bound jointly in k and ε. The reported ε⁻² dependence is therefore an improvement, but it does not settle the full rank-accuracy trade-off in that regime.
The size expressions suppress logarithmic factors and p-dependent constants. Readers should consequently treat the displayed exponents as the main comparison, with the omitted factors still part of the stated bounds.
The algorithmic record
The stated running times include nnz(A), d^ω, and kε⁻² for 1 ≤ p < 2, and nnz(A) and d^ω for p > 2.
The supplied document identifies itself as arXiv:2608.26047v2 [cs.DS], dated 27 Aug 2026.
The supplied text does not report a funding source.
Its acknowledgements disclose automated-system involvement in proof generation and say the authors verified and edited the proofs and take responsibility for the final version.
Paper data and sources
Original title: Nearly Optimal Strong Coresets for $\ell_p$ Subspace Approximation
Authors: Honghao Lin, Vahab Mirrokni, David P. Woodruff
Journal/Repository: arXiv
Status: Preprint, not yet peer-reviewed
First online: 2026-08-26
DOI: Not available
Original paper · Full text