PreprintCC BY 4.0arXiv
A Near-Optimal Lower Bound for ℓp-Subspace Embeddings, 1≤ p<2
Abstract
For d ≥ 2, p ≥ 1 and ε> 0, let Np(d,ε) be the smallest integer N such that for every integer n and every A∈ℝn× d, there exists a matrix Φ∈ℝN× n satisfying (1−ε)lVert AxrVertp≤ lVertΦA xrVertp≤ (1+ε)lVert AxrVertp for all x∈ℝd. For every constant p≥ 1 with pnot∈ 2ℤ, when d≳p log(1/ε), the bound Np(d,ε) ≳p d/(ε2 polylog(d/ε)) is established. This improves the previous lower bound Ω(1/(ε2polylog(1/ε))) due to Li et al. (SICOMP 2021) and is optimal up to logarithmic factors for 1≤ p<2. The central technical idea originated from ChatGPT 6 Pro.
Related
- Information Lower Bound for Regime Boundary Estimation — Optimal Precision Limit at the n² Scale and Universal Constant c=1/8 in the Fixed-Breakpoint Model
- A near-quadratic lower bound for the Brown--Erdős--Sós (9,6)-problem
- A near-quadratic lower bound for sets with no unique sums
- A $π/ 4$ lower bound for random access in symmetric linear ensembles under optimal decoding
- Near-Optimal Quantum Lower Bounds for Convex Optimization via Fourier Rank
BibTeX
@misc{li2026nearoptimal,
title = {{A Near-Optimal Lower Bound for $\ell_p$-Subspace Embeddings, $1\leq p<2$}},
author = {Yi Li},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2608.14201},
eprint = {2608.14201},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2608.14201},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - A Near-Optimal Lower Bound for ℓ_p-Subspace Embeddings, 1≤ p<2
AU - Yi Li
PY - 2026
DA - 2026/10/25
PB - arXiv
DO - 10.48550/arxiv.2608.14201
UR - https://arxiv.org/abs/2608.14201
AB - For d ≥ 2, p ≥ 1 and ε> 0, let N_p(d,ε) be the smallest integer N such that for every integer n and every A∈ℝ^n× d, there exists a matrix Φ∈ℝ^N× n satisfying (1−ε)lVert AxrVert_p≤ lVertΦA xrVert_p≤ (1+ε)lVert AxrVert_p for all x∈ℝ^d. For every constant p≥ 1 with pnot∈ 2ℤ, when d≳_p log(1/ε), the bound N_p(d,ε) ≳_p d/(ε^2 polylog(d/ε)) is established. This improves the previous lower bound Ω(1/(ε^2polylog(1/ε))) due to Li et al. (SICOMP 2021) and is optimal up to logarithmic factors for 1≤ p<2. The central technical idea originated from ChatGPT 6 Pro.
ER -