Metraipolis › archive › dc_fa4f727362de

A Near-Optimal Lower Bound for $\ell_p$-Subspace Embeddings, $1\leq p<2$ — arXiv:2608.14201

Source: arXiv (en)
Original: https://arxiv.org/abs/2608.14201
License (as archived): CC0-1.0
Archived: 2026-10-19T04:07:56.539Z
SHA-256 of the archived text: 06d7d6e27552a69a328eeab5a78a3424817d0f8cf48d5645f4af6d23e6be9e0a
Stable URL of this page: https://metraipolis.com/documento/dc_fa4f727362de

How to cite

A Near-Optimal Lower Bound for $\ell_p$-Subspace Embeddings, $1\leq p<2$ — arXiv:2608.14201 — arXiv (en), https://arxiv.org/abs/2608.14201 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_fa4f727362de (Metraipolis archive dc_fa4f727362de, sha256 06d7d6e27552a69a328eeab5a78a3424817d0f8cf48d5645f4af6d23e6be9e0a)

BibTeX

@misc{dcfa4f727362de,
  title = {A Near-Optimal Lower Bound for $ell_p$-Subspace Embeddings, $1leq p<2$ — arXiv:2608.14201},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2608.14201},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_fa4f727362de; sha256 06d7d6e27552a69a328eeab5a78a3424817d0f8cf48d5645f4af6d23e6be9e0a},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2608.14201. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

For $d \geq 2$, $p \geq 1$ and $\epsilon > 0$, let $N_p(d,\epsilon)$ be the smallest integer $N$ such that for every integer $n$ and every $A\in\mathbb{R}^{n\times d}$, there exists a matrix $\Phi\in\mathbb{R}^{N\times n}$ satisfying $(1-\epsilon)\lVert Ax\rVert_p\leq \lVert\Phi A x\rVert_p\leq (1+\epsilon)\lVert Ax\rVert_p$ for all $x\in\mathbb{R}^d$. For every constant $p\geq 1$ with $p\not\in 2\mathbb{Z}$, when $d\gtrsim_p \log(1/\epsilon)$, the bound \[ N_p(d,\epsilon) \gtrsim_{p} \frac{d}{\epsilon^2 \operatorname{polylog}(d/\epsilon)} \] is established. This improves the previous lower bound $\Omega(1/(\epsilon^2\operatorname{polylog}(1/\epsilon)))$ due to Li et al. (SICOMP 2021) and is optimal up to logarithmic factors for $1\leq p<2$. The central technical idea originated from ChatGPT 5.6 Sol.

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-08-17 in cs.DS).
Categorie arXiv: Data Structures and Algorithms (cs.DS) ; Functional Analysis (math.FA).
Pagina del lavoro: https://arxiv.org/abs/2608.14201 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-19T03:59:09.442Z dalla pagina https://arxiv.org/catchup/cs.DS/2026-08-17?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).