Sharp joint rank and accuracy dependence for strong ℓₚ subspace coresets
Fix a real $p > 2$. For $A \in \mathbb{R}^{n \times d}$ with rows $a_1^{\mathsf T}, \dots, a_n^{\mathsf T}$ and a linear subspace $F \subseteq \mathbb{R}^d$, let $$\operatorname{cost}_A(F) = \sum_{i=1}^n \|a_i^{\mathsf T}(I - P_F)\|_2^p,$$ where $P_F$ is the orthogonal projector onto $F$. A strong row coreset for $A$ is a vector of nonnegative weights $w = (w_1, \dots, w_n)$ with $$(1 - \varepsilon)\operatorname{cost}_A(F) \le \sum_{i=1}^n w_i\|a_i^{\mathsf T}(I - P_F)\|_2^p \le (1 + \varepsilon)\operatorname{cost}_A(F)$$ for every subspace $F$ of dimension at most $k$; its size is $|\operatorname{supp}(w)|$. Woodruff and Yasuda constructed such coresets of size $\widetilde O_p(k^{p/2}\varepsilon^{-p})$; Lin, Mirrokni and Woodruff improved this to $\widetilde O_p(k^{p/2}\varepsilon^{-2})$ and record the lower bound $\widetilde\Omega(k^{p/2}/\varepsilon + k/\varepsilon^2)$ for strong coresets, obtained from lower bounds for $\ell_p$ subspace embeddings.
Problem. Determine the optimal worst-case size of such coresets as a joint function of $k$ and $\varepsilon$, up to logarithmic factors. In particular, are there constants $C_p, c_p > 0$, depending only on $p$, such that for all $n$ and $d$, every integer $1 \le k < d$, every $A \in \mathbb{R}^{n \times d}$ and every $0 < \varepsilon < 1/2$ there is such a coreset of size at most $$C_p\left(\frac{k^{p/2}}{\varepsilon} + \frac{k}{\varepsilon^2}\right)\log^{c_p}\!\left(\frac{2k}{\varepsilon}\right)?$$
Source: Lin, Mirrokni and Woodruff (2026), §1.4, who ask whether their upper bound for p > 2 can be improved to match the known lower bound Ω̃(k^{p/2}/ε + k/ε²) up to logarithmic factors, or a stronger lower bound holds; in this form (constants C_p, c_p, the factor log^{c_p}(2k/ε), 1 ≤ k < d, 0 < ε < 1/2), OpenProblemsInNLA.
Imported from github.com/ajt60gaibb/OpenProblemsInNLA.
Classification
- Primary
- NA — Numerical Analysis
- Secondary
- PR
- Keywords
- coresets, low-rank approximations, OpenProblemsInNLA, subspace approximation
- Literature checked
- Oct. 8, 2026 by clemens-admin
References
@misc{lin2026,
author = {Lin, Honghao and Mirrokni, Vahab and Woodruff, David P.},
title = {Nearly Optimal Strong Coresets for $\ell_p$ Subspace Approximation},
year = {2026},
eprint = {2608.26047},
archivePrefix = {arXiv},
}
@inproceedings{woodruff2025,
author = {Woodruff, David P. and Yasuda, Taisuke},
title = {Root Ridge Leverage Score Sampling for $\ell_p$ Subspace Approximation},
booktitle = {2025 IEEE 66th Annual Symposium on Foundations of Computer Science (FOCS)},
publisher = {IEEE},
year = {2025},
pages = {2266--2291},
doi = {10.1109/FOCS63196.2025.00119},
eprint = {2407.03262},
archivePrefix = {arXiv},
}
@misc{openproblemsinnla-ra05,
author = {Townsend, Alex},
title = {{RA-05}: Sharp joint rank and accuracy dependence for strong $\ell_p$ subspace coresets},
howpublished = {Open Problems in Numerical Linear Algebra, GitHub repository},
year = {2026},
url = {https://github.com/ajt60gaibb/OpenProblemsInNLA/blob/main/randomized-and-low-rank-approximation/RA-05/README.md},
note = {Read at commit eb7c9d6, 2026-10-07},
}
Resolution claims
Let $S_p(k, \varepsilon)$ be the worst-case minimum support of a nonnegative strong coreset on original rows for Euclidean subspace costs of power $p$, with no restriction on input rank. For every fixed real $p > 2$ that is not an even integer, the manuscript proves $c_p k^{p/2}\varepsilon^{-2}\log^{-(5p/2+3)}(2k/\varepsilon) \le S_p(k, \varepsilon) \le C_p k^{p/2}\varepsilon^{-2}\log^{p+5}(2k/\varepsilon)$ for all $k \ge 1$ and $0 …
Status history
| When | Change | By | Reason |
|---|---|---|---|
| 2026-10-08 | Needs verification → Solution claimed | clemens-admin | Listed with the record of its solution, unreviewed. |
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-00238, "Sharp joint rank and accuracy dependence for strong ℓₚ subspace coresets", clopen.solutions.