MathDB

Nelson–Nguyen conjecture on sparse oblivious subspace embeddings

Fix a subspace dimension dd and distortion parameters α=β∈(0,1)\alpha = \beta \in (0,1). A random sparse matrix Φ:Rn→Rk\bm{\Phi}: \mathbb{R}^n \to \mathbb{R}^k has at most ζ\zeta nonzero entries per column and embedding dimension kk. Nelson–Nguyen conjecture. There exists a construction satisfying

ζ≤Const⁡⋅α−1log⁡dandk≤Const⁡⋅α−2log⁡d.\zeta \leq \operatorname{Const} \cdot \alpha^{-1} \log d \quad\text{and}\quad k \leq \operatorname{Const} \cdot \alpha^{-2} \log d.

For any fixed subspace of dimension dd, with probability at least 1−d−11-d^{-1}, this matrix is a subspace embedding with distortion parameters α,β\alpha,\beta, where the constants are universal. The conjecture concerns achieving near-logarithmic column sparsity and embedding dimension for oblivious subspace embeddings; its resolution is not established in the supplied source.

Progress summary

Solved

A March 2026 preprint claims the conjecture is solved, while a separate posted proof-checking claim remains unverified.

Nelson and Nguyen posed the conjecture at FOCS 2013. It asks for sparse oblivious subspace embeddings simultaneously achieving near-logarithmic column sparsity and near-optimal embedding dimension.

Known results

  • Nelson and Nguyen (2013): O(log⁡3(d)/ε)O(\log^3(d)/\varepsilon) sparsity and O(dlog⁡8(d)/ε2)O(d\log^8(d)/\varepsilon^2) rows.
  • Cohen (2016): O(log⁡(d)/ε)O(\log(d)/\varepsilon) sparsity and O(dlog⁡(d)/ε2)O(d\log(d)/\varepsilon^2) rows.
  • Nelson and Nguyen (2022): lower bounds restricting very sparse, low-dimensional embeddings.
  • Later work (2023–2024): optimal dimension with larger or near-optimal sparsity.

March 2026 claimed proof; posted attempt

Joel A. Tropp's preprint, first posted March 4, 2026, claims the first complete proof of the injectivity properties conjectured by Nelson and Nguyen, which appears to be an exact resolution. Independent verification is not present in the retrieved material. A separate posted attempt claims checking by named automated systems, but it has not been independently verified.

Current status (as of August 2026): Tropp's March 2026 preprint claims an exact solution, but the conjecture remains unconfirmed pending independent verification.

Sources
Sources & referencesView supporting material

Primary source

Joel A. Tropp, “Comparison theorems for the extreme eigenvalues of a random symmetric matrix”, arXiv:2603.04365 (2026).

dimension-reductionrandom-matricessubspace-embeddings

Solutions 1

Proof

Candidate proof checked by 5.6 Sol and Fable 5: https://github.com/DiarHaidary/nelson-nguyen-sparse-fock

0 endorsements
Diar Haidary ·